2-1 作业答案征集令

[hengxin]

现为以下题目征集答案:

• [ ] 5-10: Palindrome Pal1(S)
• [ ] 5-12: Palindrome Pal2(S)
• [ ] Euclid 递归算法的正确性 (未完成, 待补充)

[doowzs]

我的Euclid正确性证明（奇葩递推顺序）：从最后一次递归结束的情况向上递推，证明每次递归中gcd(a, b)都相同

Description:

The input of the algorithm is a and b. Suppose in the k-th iteration, the parameters are a(k) and b(k), and n times of iterations are conducted in total, then we have to prove that gcd(a(0), b(0)) = gcd(a(n), b(n)). In the last iteration, b(n) == 0, thus an is the greatest common divisor of a(n) and b(n). Denote a(n) as g. Now suppose that g is the greatest common divisor of a(k+1) and b(k+1), we know a(k+1) = p g and b(k+1) = q g where p and q are coprime. Since a(k+1) = b(k), b(k+1) = a(k) mod b(k). Thus a(k) = t b(k) + b(k+1) = t a(k+1) + b(k+1) = (t p + q) g, where t is a constant. b(k) = a(k+1) = p g. To prove that g = gcd(a(k), b(k)), we only have to prove that t p+r and p are coprime: suppose, in contrast that they are not coprime, then they must have a common divisor x. Hence, q = (t p + q) - t p also has the divisor x and p, q are not coprime, which is contradictory.

[hengxin]

@doowzs 原则上没有问题。不过对于这道题目来说，我们不提倡这种逆序推。正向更为直观，不易出错（包括对基础步骤 n = 0 的使用）。并且，在证明过程中要注意区分 gcd(m,n) 与 Euclid(m,n)。最后，用数学归纳法作证明时要注意数学归纳法的书写格式。