HackerNews中文版

----------------------------------------------------------------------- 算法E（欧几里得算法）。给定两个正整数m和n，找到它们的最大公约数，即能够同时整除m和n的最大正整数。E1 [求余数] 用m除以n，r为余数。（我们知道0 ≤ r < n）E2 [是否为零？] 如果r = 0，算法终止，n就是答案。E3 [简化] 设m = n，然后n = r，返回步骤E1。 -----------------------------------------------------------------------[3] 修改算法E，避免所有简单的替换操作，例如m = n。将这个新算法以算法E的风格编写，并称之为算法F。======================================================================== Claude Sonnet 4.6 ========================================================================算法F给定两个正整数m和n，找到它们的最大公约数。F1 [求余数] 用m除以n，设r为余数。（我们知道0 ≤ r < n。）F2 [是否为零？] 如果r = 0，算法终止，n就是答案。F3 [求余数] 用n除以r，设m为余数。（我们知道0 ≤ m < r。）F4 [是否为零？] 如果m = 0，算法终止，r就是答案。F5 [求余数] 用r除以m，设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.E1 [Find remained] Divide m by n and r be the remainder. (We will know that 0 <= r < n)E2 [Is it zero?] If r = 0, the algorithm terminates, n is the answerE3 [Reduce] Set m = n, then n = r, then go back to step E1 -----------------------------------------------------------------------[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.======================================================================== Claude Sonnet 4.6 ========================================================================Algorithm FGiven two positive integers m and n, find their greatest common divisor.F1 [Find remainder] Divide m by n and let r be the remainder. (We will know that 0 ≤ r < n.)F2 [Is it zero?] If r = 0, the algorithm terminates and n is the answer.F3 [Find remainder] Divide n by r and let m be the remainder. (We will know that 0 ≤ m < r.)F4 [Is it zero?] If m = 0, the algorithm terminates and r is the answer.F5 [Find remainder] Divide r by m and let n be the remainder. (We will know that 0 ≤ n < m.) Go back to F2.ExplanationThe key insight is that instead of shuffling values with temporary replacements like:m = n, n = rwe reuse the existing variables (m, n, r) in rotation, dividing and storing each new remainder directly into the variable that is no longer needed:Step Divides Remainder stored in F1...m by n...r F3...n by r...m F5...r by m...nEach 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. □

使用克劳德·索奈特 4.6 问题 1.1.3 的克努斯测试