《算法导论》笔记（二）

循环不变式

1.初始化
2.保持
3.终止
（与数学归纳法类似）

练习2.1

Ans：

① j = 2，{31，41，59，26，41}
② j = 3，{31，41，59，26，41}
③ j = 4，{31，41，26，59，41}，{31，26，41，59，41}，{26，31，41，59，41}
④ j = 5，{26，31，41，41，59}

Ans：

#include <bits/stdc++.h>

using namespace std;

int a[105];

int main()
{
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> a[i];
        }
        for (int i = 2; i <= n; i++) {
                int key = a[i], j = i-1;
                while (j > 0 && a[j] >= key) {
                        a[j+1] = a[j];
                        j--;
                }
                a[j+1] = key;
        }
        for (int i = 1; i <= n; i++) {
                cout << a[i] << " ";
        }
        cout << endl;
        return 0;
}

Ans：

① 初始化：时，若，则输出
② 保持：若前项中没有，则无输出值，若第项为，则输出
③ 终止：若将A数组中项循环完，有则输出了，没有则将赋值为

Ans：

① 形式化描述：从两个元数组最后一项开始相加，每次判断进位与否，将从1循环到n即可
② 伪代码：

carry = 0
for i = 1 to n
        sum = a[i] + b[i]
        if sum == 2
                carry = 1
                c[i] = 0
        else
                carry = 0
                c[i] = sum