使用 Claude Sonnet 4.6 的 Knuth 测试，问题 1.1.3
3 分•作者: daly•6 个月前
-----------------------------------------------------------------------
算法 E（欧几里得算法）。给定两个正整数 m 和 n，求它们的最大公约数，即能同时整除 m 和 n 的最大正整数。
E1 [求余数] 用 n 除以 m，令 r 为余数。（我们知道 0 ≤ r < n）
E2 [是否为零？] 如果 r = 0，算法终止，n 即为答案。
E3 [简化] 令 m = n，然后 n = r，返回步骤 E1。
-----------------------------------------------------------------------
[3] 修改算法 E，避免所有琐碎的替换操作，例如 m = n。用算法 E 的风格编写这个新算法，并将其命名为算法 F。
========================================================================
克劳德十四行诗 4.6
========================================================================
算法 F
给定两个正整数 m 和 n，求它们的最大公约数。
F1 [求余数] 用 n 除以 m，令 r 为余数。（我们知道 0 ≤ r < n。）
F2 [是否为零？] 如果 r = 0，算法终止，n 即为答案。
F3 [求余数] 用 r 除以 n，令 m 为余数。（我们知道 0 ≤ m < r。）
F4 [是否为零？] 如果 m = 0，算法终止，r 即为答案。
F5 [求余数] 用 m 除以 r，令 n 为余数。（我们知道 0 ≤ n < m。）返回 F2。
解释
关键的见解是，与其使用临时替换来洗牌数值，例如：
m = n, n = r
我们循环使用现有的变量（m、n、r），轮流进行除法，并将每个新的余数直接存储到不再需要的变量中：
步骤 除法 余数存储在
F1...m 除以 n...r
F3...n 除以 r...m
F5...r 除以 m...n
每个变量在每个阶段自然成为“最旧”的值，并被安全地覆盖。这消除了所有琐碎的赋值，同时保留了欧几里得算法的逻辑。 □
查看原文
-----------------------------------------------------------------------
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>[3] Change Algorithm E so that all trivial replacement operations
such as m = n are avoided. Write this new algorithm in the style of
Algorithm E and call it Algorithm F.<p>========================================================================
Claude Sonnet 4.6
========================================================================<p>Algorithm F<p>Given two positive integers m and n, find their greatest common divisor.<p>F1 [Find remainder] Divide m by n and let r be the remainder.
(We will know that 0 ≤ r < n.)<p>F2 [Is it zero?] If r = 0, the algorithm terminates and n is the answer.<p>F3 [Find remainder] Divide n by r and let m be the remainder.
(We will know that 0 ≤ m < r.)<p>F4 [Is it zero?] If m = 0, the algorithm terminates and r is the answer.<p>F5 [Find remainder] Divide r by m and let n be the remainder.
(We will know that 0 ≤ n < m.) Go back to F2.<p>Explanation<p>The key insight is that instead of shuffling values with temporary
replacements like:<p>m = n, n = r<p>we reuse the existing variables (m, n, r) in rotation, dividing and
storing each new remainder directly into the variable that is no
longer needed:<p>Step Divides Remainder stored in
F1...m by n...r
F3...n by r...m
F5...r by m...n<p>Each variable naturally becomes the "oldest" value at each stage and
is safely overwritten. This eliminates all trivial assignments while
preserving the logic of Euclid's algorithm. □