algorithm - 函数终止的证明

Question

如果 x 是偶数，则 F(x)=x/2 否则 F(x) = F(F(3x+1))。证明 F(x) 对所有整数 x 终止。

谁能帮我解决这个问题。我正在学习“计算机算法基础”。我不明白如何进行。

Answer 1

书中有一个您省略的提示:“考虑 (2i+1)2^k - 1 形式的整数并使用归纳法”。没有提示，这是一个相当困难的问题。

因此，使用提示，请注意对于某些 i 和 k，您可以将任何数字写为 (2i+1)2^k - 1。可以观察到，k 是以 2 为底数的数字底部 1 的个数。

使用它，您可以证明 F 在 k 上通过归纳终止。 k=0 的基本情况是直接的，因为 (2i+1)2^0 - 1 是偶数。

否则，当 k>0 时，(2i+1)2^k - 1 为奇数。然后

  F((2i+1)2^k - 1)
= F(F(3((2i+1)2^k - 1)+1))
= F(F(3(2i+1)2^k-2))
= F((3(2i+1)2^k-2)/2) (since k>0)
= F(((6i+3)2^k-2)/2)
= F((2(3i+1)+1)2^{k-1}-1)

根据归纳假设，F((2(3i+1)+1)2^{k-1}-1) 终止，因为它有一个较小的k，我们就完成了。