0 
//Precondition: n > 0
//Postcondition: returns the minimum number of decial digits
//               necessary to write out the number n

 int countDigits(int n){
1.    int d = 0;
2.    int val = n;
3.    while(val != 0){
4.        val = val / 10;     // In C++: 5 / 2 === 2
5.        d++;
6.    }
7.    return d;
}

不变量：就在第 3 行评估循环保护之前，删除了最右边的 d 位的 n 与 val 相同。（假设数字 0 需要 0 位来写出，并且是唯一需要 0 位来写出的数字）。

使用归纳法证明循环不变量成立。

现在我一直认为归纳证明是假设通过用 k 替换方程中的变量将是真的，那么我必须证明 k+1 也将是真的。但是在这个问题中我并没有真正给出方程式，而只是一段代码。这是我的基本情况：

就在第 3 行评估循环保护之前，d 等于 0，在第 2 行，val == n，因此如果 n 删除了最右边的 0 位，则为 val。因此，基本情况成立。

我不确定如何在此之后编写归纳步骤，因为我不确定如何证明 k+1 ..

4

1 回答 1

0

逻辑实际上与方程式相同，只是您通过循环k的迭代替换方程式中的值：n

  1. 基本情况是循环不变量在开始循环之前成立；
  2. 你必须证明如果不变量在迭代之前成立N，它在迭代执行后仍然成立N。

从 1. 和 2. 我们通过归纳得出结论，不变量在循环结束时成立（或者实际上在任何迭代结束时）。

编辑，这很有趣，因为循环以val == 0. 您的不变量（在循环结束时仍然为真）是n ，其最右边的 d 数字被删除与 val 相同n，因此d在这一点上删除数字与 0 相同，因此d正确显示所需的位数也是如此n。

于 2014-04-24T23:40:24.017 回答