algorithm - 将十进制转换为二进制 - 归纳法

Question

我阅读了 Mathematical Induction 的第 2 页, 我很难理解

The Induction Hypothesis is “If m is the integer represented by the binary array b[1,2 . . . k], then n = 2 ^ k * t + m”

1) 什么是m？

2) t 为偶数时 m 不变 而 t 为奇数时 m=m+2^k，怎么办？

请解释以上几点。谢谢

Answer 1

m是第k步中二进制数组表示的一个整数，这可能是强调不够清楚的信息。

让我们举个例子。当您将 n = 11 转换为二进制时，最终结果将是 1011。在步骤 k = 2 之后，您转换了两个最低有效位，因此当前二进制数组是 11，这给出了 m = 3。您将 11 除以 2 两次，所以 t = 11/2/2 = 2。显然，2 ^ k * t + m = 2^2 * 2 + 3 = 11 = n。 这也解释了你的第二个问题，因为对于奇数 t 下一个二进制表示中的位将为 1，这会将当前二进制表示增加 2^k。