算法概论答案(第一章)
2010-09-22 17:58阅读：
第一章
数字的算法(Algorithms with numbers)
上一章：
第0章
1.1
证明对于给定的基数b>=2,任意三个一位数相加，和最多为两位数。
证明： 设任意3个1位数为a,b,c。
基数为b的最大的一位数为b-1。例如十进制为9 ,十六进制为F(15)。
那么：a+b+c <= 3*(b-1)
基数为b的最小的3位数 为
b^2。例如十进制为100
b^2-
3*(b-1)
= (b-3/2)^2 + 3/4 > 0, 恒大于零。
得出三个一位数之和小于3位数。
基数为b的最小的3位数 为
b。例如十进制为10
3*b-3-b = 2*b - 3, 当b>=2时。 大于零。
得出三个一位数之和大于2位数。
综上可得：
三个一位数之和至多两位数长。
1.2 Show that any binary integer is at
most four times as long as corresponding decimal integer. For very
large numbers, what is the ratio of these two lengths,
approximately?
证明任何二进制整数的长度最多是相应的十进制整数4倍长。对于相当大的数字，两个长度的比例大约是多少？
证明： 由书中公式得 log2(10) = 3.321928
向上取整得4.
1.3 A d-ary tree is a rooted tree in which each node has at
most d children. Show that any d-ary tree with N nodes must have a
depth of Ω(logN / logd). Can you give a precise formula for the
minimum depth it could possibly have?
一个d叉树是一个有根树，它的每个节点至多有d个孩子。
证明任何有N个节点的d叉树必定有一个Ω(logN / logd)的深度。
你能给出它可能达到的最小深度的确切公式吗？
证明：
注意这里 是Ω，
表示“大于等于”。 我们先计算第二问
要使得d叉树深度最小，那么它肯定是一个完全d叉树。由数据结构的知识直接得到 depth = ceil(
logd(N+1))
ceil表示向上取整。等价于=ceil( log(N+1) / log(d))
既然是最小深度。一般情况下肯定大于这个值。所以得第一问 Ω(logN / logd)。
1.4 Show that log(n!) = Θ(n*logn).
证明这个...
证明：
这个问题很抽象...
根据提示：
1. 显然 n! = O(n^n) =>
log(n!) = O(log(n^n)) = O(n*logn).
2. 取(n/2)^(n/2)。 得 n! = Ω( (n/2)^(n/2) )
=> log(n!) = Ω(log(n/2)^(n/2) )
= Ω( n/2 * logn - n) = Ω( n*logn )
得 log(n!) = Θ(n*logn)
下面着重证明 n! = Ω( (n/2)^(n/2) )
n 趋向于无穷的情况下
n*(n-1)...(n/2) *
(n/2)*...1
lim n! / (n/2)^(n/2) = lim
--------------------------------—— = lim C
* (n/2) * ... 1 = 无穷
(n/2)*..... (n/2)
所以. n! = Ω( (n/2)^(n/2) )
1.5 (题目省略)
1.6. Prove that the grade-school multiplication algorithm,
when applied to binary numbers, always gives the right
answer.
证明小学乘法中的算法当使用到2进制数字上的时候，依然正确。
证明： 就和1+1为什么等于2一样难证。。。
1.7. How long does the recursive multiplication algorithm
take to multiply an n-bit number by an m-bit number?Justify your
answer.
递归乘法算法计算n位数乘以m位数需要多长时间，证明你的结论。
证明： O(n*m) .
设乘数长度为n.每次递归乘数减半，即位数减一。因此算法递归n次，每次递归需要进行一次长度为m的加法运算。
因此，总时间复杂度为O(n*m)。
1.8. Justify the correctness of
the recursive division algorithm given in page 15, and show that it
takes time O(n^2) on n-bit inputs.
证明15页递归除法算法的正确性，然后证明对于n位输入，他需要O(n^2)的时间。
1.9. Starting from the definition of x = y mod N,
justify the substitution rule
x = x' mod N, y = y'
mod N => x + y = x' + y' mod N,
and also the corresponding
rule for multiplication.
从x = y mod
N的定义出发，证明加法替代法则和乘法替代法则。
证明： x = x' mod N => x = aN + x'
y = y' mod N => y = bN +
y'
x + y = (a+b)N + (x' + y')
xy = abNN + aNy' + bNx' + x'y' =
(abN+ay'+bx')N + x'y'
1.10. Show that if a = b (mod N) and if M divides N then a =
b (mod M).
证明如果a = b (mod N) 并且
N 整除 M， 那么 a = b (mod M)
证明：
M divides N => N = dM
a = b (mod N ) => a = cN
+ b => a = cdM + b => a = b (mod M)
1.11. Is 4^1536 - 9^4824 divisible by
35?
这个数能整除35吗？
解： 4^1536 => 64^512 => 29^512 => 841^256
=> 1^256 (mod 35)
9^4824 =>
81^2412 => 11^2412 => 1331^804 => 1^804 (mod
35)
1-1 =0 (mod
35)
可以。
1.12. What is 2^(2^2006) (mod 3)
解： 2^(2^2006) => 4^(2^2005) => 1^(2^2005) => 1
(mod3)
1.13. Is the difference of 5^30000 and 6^123456 a multiple of
31?
这两个数之差能整除31吗？
解： 5^30000 => 125^10000 => 1^10000 => 1 (mod
31)
6^123456
=> 36^61728 => 5^61728 => 125^20576 => 1^20576 => 1
(mod 31)
1-1 = 0
(mod 31)
可以。
1.14. Suppose you want to compute the nth Fibonacci number
Fn, modulo an integer p. Can you find a efficient way to do this?
(Hint: Recall Exercise 0.4.)
假设你想计算nth
Fibonacci-- Fn mod p. 你能找到一个有效的方法做这个吗？
解： 使用 Exercise 0.4.的方法， 需要O(logn)次矩阵乘法。每次乘法过后将4个 数都mod p,
以减少运算量。
1.15. Determine necessary and sufficient conditions on x and
c so that the following holds: for any a,b, if ax = bx mod c , then
a = b mod c.
决定关于x和c的充分必要条件，使得下面条件成立：...
解：
ax = bx mod c => ax = cN1 + bx =>
a = b mod c => a = cN2 + b =>
对比以上两个式子得到 N2* x = N1 ... ????
1.16. The algoritm for computing a^b mod c by repeated
squaring does not necessarily lead to the minimum number of
multiplications. Given an example of b > 10 where the
exponentiation can be performed using fewer multiplications, by
some other method.
通过不断平方来计算 a^b
mod c
并不一定是最少乘法计算量的算法。找到一个b>10的例子，指数计算能通过另一种计算量更小的方法完成。
解： 例如，81^2412 (mod 35)
先平方取模，得到 11^2412 ,再取立方，得到1331^804
(mod 35) => 1^804 (mod 35)
1.17. Consider the problem of computing x^y for given
integers x and y. we want the whole answer, not modulo a third
integer. We know two algorithms for doing this: the iterative
algoritm which performs y-1 multiplication by x; and the recursive
algorithm based on the binary expansion of y.
Compare the time requirements of these two algorithms,
assuming that the time to multiply an n-bit number by an m-bit
number is O(mn).
考虑计算x的y次方的问题.
我们要完整的结果，而不是模上第三个数。我们知道有两种算法完成计算。一种是迭代算法，乘以y-1次x。另一种算法基于y的二进制表示。
比较两种算法的时间复杂度，
假定n位数与m位数相乘的时间复杂度为O(mn)
解：
简单起见。我们设x,y均为n位数。
方法一： = O(n*n) + O(2n*n) +
... O((2^n-1)*n*n) (每乘一次。结果的长度加n.一共乘2^n-1次)
(没有加法)
= O( (1 + (2^n-1))/ 2 *
(2^n-1) * n * n )
= O(2^2n*n*n)
方法二： = O(n*n) + O(2n*2n) +
O( (2^([logn]-1)*n)^2)(先计算x^1, x^2, x^4....) + 忽略加法
= O(2^(2logn)*n*n)
[logn] 在这里表示向下取整，log为以2为底。
1.18. Compute gcd(210, 588) two different ways: by finding
the factorization of each number, and by using Euclid`s
algorithm.
使用两种不同的方法计算gcd(210, 588)，一种通过分解两个数的质因数，另一种通过欧几里德算法。
解：210 = 2 * 3 * 5 * 7
588 = 2 * 2 * 3 * 7
* 7
gcd(210, 588) = 42
gcd(210, 588) = gcd(168,
210) = gcd(42, 168) = gcd(1,42) = 42
1.19. The Fibonacci numbers F(0), F(1), ... are given by the
recurrence F(n+1) = F(n) + F(n-1), F(0) = 0, F(1)
= 1.Show that for any n>=1, gcd(F(n+1), F(n)) =
1
证明： 数学归纳法
x = 1 时候 显然 gcd(1,1) = 1
假设 x= n 时，gcd(F(n+1), F(n)) = 1成立
对于 x = n+1, gcd(F(n+2), F(n+1)) = gcd(F(n+1)+ F(n), F(n+1))
= gcd(F(n), F(n+1)) = 1;
1.20. Find the inverse of: 20 mod 79, 3 mod 62,
21 mod 91, 5 mod23.
解： 按照P22页硬套公式计算，只算了前面两个: 83, 83.
83*20 - 79*21 =
1
83*3 - 62*4
= 1
1.21.How many integers modulo 11^3 have inverses? (NOTE: 11^3
= 1331)
多少个整数模11^3有逆?(个人觉得整数范围应该[1331,1])
解： 即检查 gcd(x, 1331) = 1
1330 - 1330/11
= 1330 - 120 = 1210
1.22. Prove or disprove: If a has an inverse modulo
b, then b has an inverse modulo a.
证明或反驳： 如果a对于模b有一个逆, 那么b对于模a就一定有一个逆.
证明： a has an inverse modulo b,设c为a的逆
=> a*c+ N*b = 1;
那么对于b来说 => b对于模a就有一个逆:N.
1.23. Show that if a has a multiplicative inverse modulo N,
then this inverse is unique(modulo N)
证明如果a对于模N有多个逆，这些逆模N后的值唯一(即这些数同余)
证明： 首先，a有逆 ,
=> a*b + N*c = 1 (b,c为整数)
既然 结论要求模N后此数唯一
=> a*b mod N + N*c mod N = 1 mod
N
=> a*b mod N + c mod N = 1 mod
N
=> a*b mod N = 1 - c mod N
=> b mod N = (1 - c) / a mod N
b,c一一对应...
1.24. If p is prime, how many elements of {0,1,....,p^n-1}
have an inverse modulo p^n?
证明： p^n -1 - p^(n-1) , 见1.21.
1.25. Calculate 2^125 mod 127 using any method you
choose.(Hint:127 is prime)
解： 2^125 = 2^119 * 2^6 = 128^17 * 2^6 =
1^17 * 2^6 = 64.
1.26. What is the least significant decimal digit of
17^(17^17)?(Hint: For distinct primes p, q, and any a relatively
prime to pq, we proved the formula a^(p-1)(q-1) = 1(mod pq) in
Section 1.4.2)
1.27. Consider an RSA key set with p=17, q=23, N=391, and e =
3. What value of d should be used for the secret key? What is the
encryption of the message M = 41?
解：套公式得： d =235, encryption of M = 105.
1.28. In an RSA cryptosystem, p = 7 and q = 11. Find
appropriate exponts d and e.
解：要求gcd(e,(p-1)(q-1)) = 1 即 gcd(e, 60) = 1. 那么取 e =7
套公式得 d = 43.
1.29.
1.30.
1.31. Consider the problem of computing N! = 1*2*3...N
(a)If N is an n-bit
number, how many bits long is N!, approximately (in Θ()form)?
(b)Give an
algorithm to compute N! and analyze its running time.
考虑计算N的阶乘的问题。
(a)如果N是n位数字, N!有多少位长?
以Θ()的形式估算
(b)给出一个算法计算N!,
分析它的时间复杂度。
解： (a) =
1.32.
1.33. Give an efficient algorithm to compute the least common
multiple of two n-bit number x and y, that is ,the smallest number
divisible by both x and y. What is the running time of your
algorithm as a function of n?
给出一个计算最小公倍数：能同时整除x和y的最小的数。 你的算法的时间复杂度是多少？
解：x*y / gcd(x,y)
O(n^3),与gcd(x,y)相同
1.34. On page 29, we claimed that since about a 1/n fratcion of
n-bit numbers are prime, on average it is sufficient to draw O(n)
random n-bit numbers before hitting a prime.We now justify this
rigorously.
Suppose a particular coin has a probability p of coming up
heads. How many times must you toss it, on average, before it comes
up heads?
在29页,
我们认为，因为n分之一的n位数是质数， 平均下来每数n个n位数就会碰到一个质数。我们现在来严格证明。
假设，一个特殊的硬币头像朝上的概率为p. 你平均需要抛它多少次才会出现一次头像朝上？
证明： 方法一：
均值E = Σ px = Σ p (1-p)^(i-1)
* i ; 拆分，使用高等数学中级数求和的知识。折腾一下得到:
未完待续
