算法导论31.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 4.9k 阅读时长 ≈ 4 分钟

31.2-1

令\(\displaystyle{a'=\prod_{i=1}^{r} p_i^{e_i-\min(e_i,f_i)},b'=\prod_{i=1}^{r} p_i^{f_i-\min(e_i,f_i)}},g=\prod_{i=1}^{r} p_i^{\min(e_i,f_i)}\)。

那么有\(a=a'g,b=b'g\)，并且由于\(\forall i\in[1,r],e_i\ge\min(e_i,f_i),f_i\ge \min(e_i,f_i)\)，因此\(a',b'\)的所有指数仍然仍然是非负整数。也就是说，\(a',b'\)仍然是整数，\(g\mid a,g\mid b\)。

接下来说明\(\gcd(a',b')=1\)。由于\(\forall i\in[1,r],e_i-\min(e_i,f_i)=0\)和\(f_i-\min(e_i,f_i)=0\)必定有一个成立，因此要么\(p_i\nmid a\)，要么\(p_i\nmid b\)，这两个条件必须有一个成立。也就是说，\(\nexists p,p\mid a,p\mid b\)同时成立。因此\(\gcd(a',b')=1\)，这说明\(\gcd(a,b)=g\)。

31.2-2

按照图31.1可以列出下表：

\(\begin{array}{cccccc} a&b&\lfloor a/b\rfloor&d&x&y\\\hline 899&493&1&29&-6&11\\ 493&406&1&29&5&-6\\ 406&87&4&29&-1&5\\ 87&58&1&29&1&-1\\ 58&29&2&29&0&-1\\ 29&0&-&29&1&0 \end{array}\)

最终EXTENDED-EUCLID(899, 493)返回\((29,-6,11)\)。

31.2-3

根据定理31.9，有

\(\begin{aligned} \gcd(a+kn,n)&=\gcd(n,(a+kn)\bmod n)\\ &=\gcd(n,a\bmod n)\\ &=\gcd(a,n) \end{aligned}\)

因此当\(a\)满足\(a=1\pmod n\)时，将上面的式子由下往上推，有

\(\begin{aligned} \gcd(a,n)&=\gcd(n,a\bmod n)\\ &=\gcd(n,1)\\ &=1 \end{aligned}\)

31.2-4

这个算法由EUCLID'给出。

1
2
3
4
EUCLID'(a, b)
  while b != 0
    (a, b) = (b, a % b)
  return a

31.2-5

定理33.11给出，当\(b<F_{k+1}\)时，调用次数小于\(k\)次。又因为\(F_{k+1}<\dfrac{\phi^{k+1}}{\sqrt{5}}\)，因此可得\(b<\dfrac{\phi^{k+1}}{\sqrt{5}}\)。令\(k=\log_{\phi}\)

定理33.10给出，当\(b\ge F_{k+1}\)时，EUCLID的调用次数上界才能达到\(k\)。

那么可以知道，\(F_{k+1}\ge\dfrac{\phi^{k+1}}{\sqrt{5}}-\dfrac{\sqrt{5}-1}{2}\)。那么有\(\dfrac{\phi^{k+1}}{\sqrt{5}}\le b+\dfrac{\sqrt{5}-1}{2}\)。两侧对\(\phi\)取对数并且移项，得到

\[k\le\log_{\phi}\sqrt{5}+\log_{\phi}\left(b+\dfrac{\sqrt{5}-1}{2}\right)-1\]

当\(b\ge 4\)时，可以得到\(k\le \log_{\phi}\sqrt{5}+\log_{\phi}\left(b+\dfrac{\sqrt{5}-1}{2}\right)-1<1+\log_{\phi} b\)，从而保证原结论成立。

当\(b=1,2,3\)时，通过代入定理33.10的结论进行验证也可知原结论成立。

使用循环不变量来证明这个界限可以缩紧到\(1+\log_{\phi}\dfrac{b}{\gcd(a,b)}\)。

令\(g=\gcd(a,b),a'=\dfrac{a}{g},b'=\dfrac{b}{g}\)，我们将证明在整个递归过程中，参数值为\((a,b)\)的调用过程产生的参数，永远是参数值为\((a',b')\)的调用过程产生的参数的\(g\)倍。

初始：程序\(A\)调用EUCLID(a, b)，子程序\(B\)调用EUCLID(a', b')，有\(a=a'g,b=b'g\)。

保持：程序\(A\)计算出了\(a\bmod b\)的值，程序\(B\)计算出了\(a'\bmod b'\)的值。可以发现，

\(a\bmod b=(a'g)\mod(b'g)=a'g-b'g\left\lfloor\dfrac{a'g}{b'g}\right\rfloor=g\left(a'-b'\left\lfloor\dfrac{a'}{b'}\right\rfloor\right)=g(a'\bmod b')\)

整个循环保持了这个性质。

终止：最终程序\(A\)的最后一步调用参数为\((g,0)\)，并返回；程序\(B\)的最后一步调用参数为\((1,0)\)，并返回。

这说明了程序\(A\)和程序\(B\)的递归步骤总是一致的。也就是说，上面的调用次数上限可以缩紧到\(1+\log_\phi b'=1+\log_{\phi}\dfrac{b}{\gcd(a,b)}\)。

31.2-6

定理31.11的描述过程给出了求解\(\gcd(F_{k+1},F_k)\)的答案；它实际上是：

\(\gcd(F_{k+1},F_k)=\gcd(F_{k},F_{k-1})=\dots=\gcd(F_{2},F_1)=\gcd(F_{1},F_0)=1\)

也就是说，相邻两项的斐波那契数的最大公因数为\(1\)。

因此接下来我们考虑调用EXTENDED-EUCLID(F[k+1], F[k])的结果，用\((x_k,y_k)\)表示（不需要考虑\(d_k\)，我们刚刚已经知道了\(d_k=1\)）。我们将自底向上地考虑这个过程，那么有：

\(\left \{\begin{aligned} &x_k=y_{k-1}\\ &y_k=x_{k-1}-\lfloor F_{k}/F_{k-1}\rfloor y_{k-1} = x_{k-1}-y_{k-1} \end{aligned}\right.\)

其中，第二个等号是当\(k\ge 3\)时才满足。

对于一些比较小的\(k\)值，有

\(\begin{array}{cccc} k&d_k&x_k&y_k\\ \hline 0&1&1&0\\ 1&1&0&1\\ 2&1&0&1\\ 3&1&1&-1\\ 4&1&-1&2 \end{array}\)

对于较大的\(k\)值，我们考虑计算求解递推式\(a_k=a_{k-2}-a_{k-1},a_0=0,a_1=1\)，不难求出\(a_k=(-1)^{k+1}F_k\)。

因此，将\(a\)回代到\(y\)。不难知道，对于\(k\ge 4\)，算法EXTENDED-EUCLID的返回结果为\((1,(-1)^{k+1}F_{k-2},(-1)^{k}F_{k-1})\)。

31.2-7

等式31.6证明说明了参数的次序不影响最大公因数的值，即满足交换律。

题目31.1-10证明了参数的优先运算顺序不影响最大公因数的值，即满足结合律，哪怕多于两个参数。

因此按照这两个性质，无论是多个参数参与进行运算，最大公因数的值并不会受到影响。

至于求解\(a_1x_1+a_2x_2+\dots+a_nx_n=\gcd(a_1,a_2,\dots,a_n)\)，令\(g_n=\gcd(a_1,a_2,\dots,a_n)\)。我们使用\(\gcd(g_{n-1},a_n)=g_n\)这个等式来考虑：

假设已经计算出了一组整数\(y_1,y_2,\dots,y_{n-1}\)，使得\(\displaystyle{\sum_{i=1}^{n-1} a_iy_i=g_{n-1}}\)，那么将左边的这一些值视为整体，我们就可以得到以\((x,y)\)为未知数的方程\(g_{n-1}x+a_ny=g_n\)。对它使用EXTENDED-EUCLID求出解后，那么对于\(i\in[1,n)\)，令\(x_i=y_i\cdot x\)即可，并令\(x_n=y\)，那么久求出了一组解\((x_1,x_2,\dots.x_n)\)。

只要\(a\)值是从小到大求解的，那么EXTENDED-EUCLID算法使用除法的次数仅仅取决于\(a_i\)的最大值，并且由于每次遍历时，一开始调用EXTENDED-EUCLID的参数\(b\)必定不为\(0\)，因此也需要一次除法操作。因此整个程序的时间复杂度为\(\displaystyle{O\left(n+\max_{i=1}^n\{a_i\}\right)}\)。这个算法由MULTI-EXTENDED-EUCLID给出。

1
2
3
4
5
6
7
8
9
10
11
MULTI-EXTENDED-EUCLID(A, n)
  Sort A monotonically increasing 
  let X[1 : n] be new array
  X[1] = 1
  g = A[1]
  for i = 2 to n
    (g, x, y) = EXTENDED-EUCLID(g, A[i])
    X[i] = y
    for j = 1 to n
      X[j] = X[j] * x
  return X

31.2-8

这个算法由LCM-MULTI给出。其基于的事实是，\(\text{lcm}(a_1,a_2,\dots,a_n)=\text{lcm}(\text{lcm}(a_1,a_2,\dots,a_{n-1}),a_n)\)，以及\(\text{lcm}(a,b)\cdot\gcd(a,b)=ab\)。

1
2
3
4
5
6
LCM-MULTI(A, n)
  l = A[1]
  for i = 2 to n
    g = EUCLID(l, A[i])
    l = l * A[i] / g
  return l

整个算法的时间复杂度为\(O(n\log M)\)，因为计算复杂性主要在于求解最大公因数。

31.2-9

以下证明将围绕定理31.6进行证明：\(\gcd(ab,p)=1\)当且仅当\(\gcd(a,p)=1,\gcd(b,p)=1\)。

由于\(\gcd(n_1n_2,n_3n_4)=1\)，因此\(\gcd(n_1,n_3)=\gcd(n_1,n_4)=\gcd(n_2,n_3)=\gcd(n_2,n_4)=1\)，按照定理31.6，这两个条件是充要的。

由于\(\gcd(n_1n_3,n_2n_4)=1\)，因此\(\gcd(n_1,n_2)=\gcd(n_1,n_4)=\gcd(n_3,n_2)=\gcd(n_3,n_4)=1\)，同样按照定理31.6，这两个条件是充要的。

因此，\(n_1,n_2,n_3,n_4\)两两互质当且仅当\(\gcd(n_1n_2,n_3n_4)=\gcd(n_1n_3,n_2n_4)=1\)。

对于更一般的过程（为了方便，这里我们假设下标从\(0\)开始），令\(m=\lceil \lg k\rceil\)，在第\(i\)轮中，将下标满足第\(i\)位为\(1\)的数（假设这个数集为\(S^i_1\)）乘起来得到\(s^i_1\)，将下标满足第\(i\)位为\(0\)的数（假设这个数集为\(S^i_0\)）乘起来得到\(s^i_0\)，如果\(\gcd(s_0,s_1)=1\)，那么说明\(S_0^i\)中的数和\(S_1^i\)中的都是互质的，因此每一对数总会在某一轮中处在不同的集合。

这个算法由程序IS-PAIRWISE-RELATIVELY-PRIME给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
IS-PAIRWISE-RELATIVELY-PRIME(A, k)
  m = ⌈lg k⌉ 
  for i = 0 to m - 1
    s0 = 1
    s1 = 1
    for j = 0 to k
      // 下标j的第i比特为0。
      if (j >> i & 1) == 0
        s0 = s0 * A[j]
      else
        s1 = s1 * A[j]
    if EUCLID(s0, s1) != 1
      return False
  return True