算法导论31.2 Exercises 答案

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

31.2-1

令$\displaystyle{a’=\prod{i=1}^{r} p_i^{e_i-\min(e_i,f_i)},b’=\prod{i=1}^{r} pi^{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$取对数并且移项，得到

当$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},F1)=\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}
&xk=y{k-1}\
&yk=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$值，我们考虑计算求解递推式$ak=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证明了参数的优先运算顺序不影响最大公因数的值，即满足结合律，哪怕多于两个参数。

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

至于求解$a1x_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$这个等式来考虑：

假设已经计算出了一组整数$y1,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算法使用除法的次数仅仅取决于$ai$的最大值，并且由于每次遍历时，一开始调用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}(a1,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