algorithm - 证明在循环 even n = n/2 and odd n = n + 1 之后任何 n 等于 1

Question

假设我们有一个整数 n ≥ 1。在循环中，当 n 大于 1 时。如果 n 是偶数，则 n = n/2。如果 n 是奇数，则 n = n + 1。否则，算法将退出循环并返回“成功”。

我如何着手从归纳法证明这个问题。我想用归纳来假设k≥1。但是，在归纳步骤中我不能假设的条件是什么？

Answer 1

拆分问题分3种情况。

1) 如果 n = 1，我们就完成了。

2) 如果 n > 1 并且 n 是偶数。接下来的数字将是 n/2，如果 n 大于 1，则肯定小于 n。

3) 如果 n > 1 并且 n 是奇数。比我们可以写 n = 2 * k + 1。下一次迭代后我们将得到 n = 2 * k + 2。两次迭代后我们将得到 n = k + 1。我们知道 k + 1 < 2 * k + 1.

对于情况 1) 我们已经完成，对于情况 2) 和 3) 我们将问题简化为更小的问题。

你可以从中锻炼归纳法。

如果需要，我可以写完整的归纳法。