使用 Claude Sonnet 4.6 的 Knuth 测试，问题 1.1.2
1 分•作者: daly•6 个月前
Knuth 测试，使用 Claude Sonnet 4.6，问题 1.1.2
Knuth 计算机程序设计艺术 V1 第 9 页
-----------------------------------------------------------------------
算法 E（欧几里得算法）。给定两个正整数 m 和 n，
求它们的最大公约数，即能同时整除 m 和 n 的最大正整数。
E1 [求余数] 用 n 除以 m，令 r 为余数。（我们知道 0 ≤ r < n）
E2 [是否为零？] 如果 r = 0，则算法终止，n 即为答案。
E3 [简化] 令 m = n，然后 n = r，再回到步骤 E1。
-----------------------------------------------------------------------
证明在步骤 E1 开始时，m 总是大于 n，除了该步骤可能首次出现的情况。
========================================================================
Claude Sonnet 4.6
========================================================================
证明
我们要证明在 E1 开始时，对于每一次迭代，m > n，除了可能第一次。
E1 的第一次执行
当 E1 第一次执行时，m 和 n 仅仅是作为输入给定的任意正整数。不能保证 m > n，这就是存在例外的原因。例如，当 m = 2166 且 n = 6099 时，在第一次调用时，我们有 m < n。
E1 的所有后续执行
在 E1 第一次执行之后，只有当 r ≠ 0 时（在 E2 中检查）我们才会到达 E3。在 E3 中，替换如下：
m = n
n = r
然后我们返回到 E1。所以在下一次 E1 开始时，新值是：
m_new = n_old 且 n_new = r_old
从 E1，我们知道 r 是 m 除以 n 的余数，所以根据定义：
0 ≤ r < n
由于 E3 只有在 r ≠ 0 时才会到达（否则 E2 就会终止），我们将此条件收紧为：
0 < r < n
因此：
n_new = r_old < n_old = m_new
这给了我们：
m_new > n_new
结论
在第一次迭代之后，新的 m 总是旧的 n，而新的 n 总是余数 r，它严格小于旧的 n。因此，在 E1 的每一次执行开始时，m > n 都成立，除了可能第一次，这正是我们想要证明的。 □
查看原文
Knuth Tests using Claude Sonnet 4.6 problem 1.1.2<p>Knuth Art Of Computer Programming V1 p9
-----------------------------------------------------------------------
Algorithm E (Euclid's algorithm). Given two positive integers m and n,
find their greatest common divisor, that is, the largest positive integer
that evenly divides both m and n.<p>E1 [Find remained] Divide m by n and r be the remainder. (We will
know that 0 <= r < n)<p>E2 [Is it zero?] If r = 0, the algorithm terminates, n is the answer<p>E3 [Reduce] Set m = n, then n = r, then go back to step E1
-----------------------------------------------------------------------<p>Prove that m is always greater than n at the beginning of step E1,
except possibly the first time this step occurs.<p>========================================================================
Claude Sonnet 4.6
========================================================================<p>Proof<p>We want to show that m > n at the start of E1, for every iteration
except possibly the first.<p>First Execution of E1<p>When E1 is executed the first time, m and n are simply whatever
positive integers were given as input. There is no guarantee that
m > n, which is why the exception exists. For example, with m = 2166
and n = 6099, we have m < n on the first call.<p>All Subsequent Executions of E1<p>After the first execution of E1, we reach E3 only if r ≠ 0 (checked at
E2). At E3, the replacements are:<p>m = n
n = r<p>Then we return to E1. So at the start of the next E1, the new values
are:<p>m_new = n_old and n_new = r_old<p>From E1, we know r is the remainder when m is divided by n, so by
definition:<p>0 ≤ r < n<p>Since E3 is only reached when r ≠ 0 (E2 would have terminated
otherwise), we tighten this to:<p>0 < r < n<p>Therefore:<p>n_new = r_old < n_old = m_new<p>Which gives us:<p>m_new > n_new<p>Conclusion<p>After the first iteration, the new m is always the old n, and the new
n is always the remainder r, which is strictly less than the old n.
Therefore m > n holds at the beginning of every execution of E1 except
possibly the first, which is what we wanted to prove. □