曲阜师范大学课堂作业
作业一
2.1.1 For each of the following algorithms, indicate(i)a natural size metric for its inputs,(i) its basic operation, and(ii) whether the basic operation count can be different for inputs of the same size: a. computing the sum of n numbers b. computing n! c. finding the largest element in a list of n numbers d. Euclid's algorithm e. sieve of Eratosthenes f. pen-and-pencil algorithm for multiplying two n-digit decimal integers
答： Question i ii iii a n 相加 不会 b 二进制表中的位数 相乘 不会 c n 两个数字不断比较 不会 d 两个输入数中较大的模除运算 会 数的大小，或两个输入数中较小的数的大小，或两个输入数的大小之和; e 二进制表中的位数 从剩余的主要候选名不会 单中剔除若干 f n 两位数字乘法 不会
2.1.4 a. Glove selection There are 22 gloves in a drawer:5 pairs of red gloves,4 pairs of yellow, and 2 pairs of green. You select the gloves in the dark and can check them only after a selection has been made. What is the smallest number of gloves you need to select to have at least one matching pair in the best case? In the worst case?
b. Missing socks Imagine that after washing 5 distinct pairs of socks, you discover that two socks are missing. Of course, you would like to have the largest number of complete pairs remaining. Thus, you are left with 4 complete pairs in the best-case scenario and with 3 complete pairs in the worst case. Assuming that the probability of disappearance for each of the 10socks is the same, find the probability of the best-case scenario; the probability of the worst-case scenario; the number of pairs you should expect in the average case.
答：
a. 最好的情况是2只，最差的情况是12只 b. 在袜子丢失中，丢失的总情况数为：而丢失的是不同的两双的概率为：种，而假设丢失的恰好是同一双的概率为：，通过求期望值： ，
曲阜师范大学课堂作业
2.1.9 For each of the following pairs of functions, indicate whether the first function of each of the following pairs has a lower, same, or higher order of growth(to within a constant multiple) than the second function.
答：
2.2.3 For each of the following functions, indicate the class(g(n)) the function belongs to.(Use
the simplest g(n) possible in your answers.) Prove your assertions.
答：
曲阜师范大学课堂作业
2.2.4 a. Table 2.1 contains values of several functions that often arise in the analysis of algorithms. These values certainly suggest that the functions
are listed in increasing order of their order of growth. Do these values prove this fact with mathematical certainty?
b. Prove that the functions are indeed listed in increasing order of their order of growth.
答：
a. 随着n的增大这些函数都会趋于正无穷，没有一个确定的函数值能证明他们的顺序。 b.
曲阜师范大学课堂作业
2.2.5 List the following functions according to their order of growth from the lowest to the highest:
答：
由前至后分别属于的类型为：阶乘，对数，指数，幂函数，对数的平方，幂函数，指数函数，具体的优先级为：
2.3.4 Consider the following algorithm.
ALGORITHM ??????????????(??) //Input: ?? nonnegative integer ?? ?? ← 0
for ?? ← 1 to ?? do
?? ← ??+ ????? return ??
a. What does this algorithm compute? b. What is its basic operation?
c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm?
e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.
答：算法求得是n项的平方和，基本操作是乘法，这个操作执行了n次，效率类型为
，
曲阜师范大学课堂作业
假如我们使用二进制表的位数作为度量标准那么效率类型为
，通过：
……
求和得：
由于因此：
即：
2.3.10 Mental arithmetic A 10×10 table is filled with repeating numbers on itsdiagonals as shown below. Calculate the total sum of the table's numbers in your head(after [ Cra07, Question 1.33]).
1 2 3 2 3 9 10 11 3 9 10 11 9 10 11 9 10 11 答：10*10*10=1000
… 9 10 11 … 9 10 11 9 10 11 18 9 10 11 18 19 10 11 … 9 10 18 19 20 …
算法设计与程序分析习题精选含答案(第二章)
