算法设计与分析-习题4.4

目录

1.切割木棍 一根n英寸长的木棍需要切割成n段1英寸长的小段。描述以最小切割次数完成该任务的算法。如果一次能切多根木棍，再给出最小切割次数的公式。

2.设计一个减半算法来计算[log₂n]，并确定它的时间效率。

3. 

a.在下面的数组中查找一个键时，折半查找最多需要进行多少次键值比较?

b.请列出所有这样的键，对于它们，折半查找在查找该数组时，需要进行最多次的键值比较。

c.在对该数组折半查找成功的前提下，求键值比较的平均次数(假设查找每一个键的概率都是相同的)。

d.在对该数组折半查找失败的前提下，求键值比较的平均次数(假设查找键位于该数组构成的14个区间内的概率都是相同的)。

4.请估计一下，对于一个包含1000000个元素的有序数组进行成功查找，折半查找比顺序查找平均快多少倍?

5.无论是用数组还是用链表实现一个列表，使用顺序查找的效率都是基本相同的。这对于折半查找来说也成立吗?

6.

a.设计一个只使用两路比较的折半查找的版本，例如只用≤和=。可以任选一种语言来实现，并认真地调试：众所周知，这类程序很容易有错误。

b.对于a中设计的两路比较算法，分析其时间效率。

7. 猜图片 一个非常流行的解题游戏是这样的：给选手出示42张图片，每行6张，共7行。选手可以给大家做一些是非题，来确定他要寻找的图片。然后进一步要求选手用尽可能少的问题来确定目标图片。给出解决该问题的最有效的算法，并指出需要提问的最大次数。

8. 请考虑三重查找(ternary search)————就是下面这个查找有序数组A[0.. n-1]的算法:如果n=1，就把数组中的唯一元素和查找键 K 进行比较。否则，通过比较 K 和A[[n/3]]来进行递归查找。如果 K 较大,把它和A[[2n/3]]进行比较,以确定在数组的三段中的哪一段中继续查找过程。

a.该算法是以哪种算法思想为基础的?

b.为最差情况下的键值比较次数建立一个递推式(我们可以假设n=3*)。

c. 在​编辑 的情况下解该递推式。

d.将该算法的效率和折半查找的进行比较。

9.一个数组A[0..n-2]包含n-1个从1到n的整数(因此在这个范围内缺少一个整数)，元素升序排列。尽你所能设计一个求缺失整数的最有效算法，并说明它的时间效率。

10.

a.为假币问题的三分算法写一段伪代码。请确保该算法会正确处理所有的n值，而不仅仅是那些3的倍数。

b.为假币问题的三分算法的称重次数建立一个递推关系，并在​编辑 的情况下对它求解。

c.当n的值非常大时，该算法要比把硬币分成两堆的算法快多少倍?这个答案应该与n无关。

11.

a. 应用俄式乘法来计算26×47。

b.从时间效率的角度看，我们用俄式乘法算法计算n×m和m×n有区别吗?

12.

a.为俄式乘法算法编写伪代码。

b.说明俄式乘法的时间效率类型。

13. 求J(40)————在n=40的情况下, 约瑟夫斯问题的解。

14.请证明，对于所有为2的乘方的n来说，它的约瑟夫斯问题的解是1。

15.对于约瑟夫斯问题

a. 当n=1,2,…,15, 计算J(n)。

b.通过观察，从前15个n值的解中发现一个模式，然后证明它在一般情况下的正确性。

c.有一种做法是将n的二进制表示向左循环移一位来得到J(n)，证明它的正确性。

1.切割木棍 一根n英寸长的木棍需要切割成n段1英寸长的小段。描述以最小切割次数完成该任务的算法。如果一次能切多根木棍，再给出最小切割次数的公式。

对于第一个要求，最小切割次数 = n − 1

一次切多根时，有以下递推式：

最小切割次数为 ⌈ log₂n ⌉

2.设计一个减半算法来计算[log₂n]，并确定它的时间效率。

我们要算的是：把 n 连续除以 2，直到变成 0，一共能除多少次。这个次数就是 ⌊log₂n⌋。

算法：FloorLog2(n)
// 输入：正整数 n
// 输出：⌊log₂n⌋
count ← 0
while n > 1 do
n ← ⌊n / 2⌋ // 减半操作
count ← count + 1
return count

时间效率：Θ (log n)。

3. 

a.在下面的数组中查找一个键时，折半查找最多需要进行多少次键值比较?

折半查找最大比较次数 = ⌈ log₂(n+1) ⌉

b.请列出所有这样的键，对于它们，折半查找在查找该数组时，需要进行最多次的键值比较。

c.在对该数组折半查找成功的前提下，求键值比较的平均次数(假设查找每一个键的概率都是相同的)。

p=1/13,所以

d.在对该数组折半查找失败的前提下，求键值比较的平均次数(假设查找键位于该数组构成的14个区间内的概率都是相同的)。

p=1/14, 所以

4.请估计一下，对于一个包含1000000个元素的有序数组进行成功查找，折半查找比顺序查找平均快多少倍?

• 顺序查找成功平均比较次数：Cseq​≈n/2
• 折半查找成功平均比较次数：Cbin​≈

• 顺序查找​=500000

• 折半查找≈20

• 快约25000倍

5.无论是用数组还是用链表实现一个列表，使用顺序查找的效率都是基本相同的。这对于折半查找来说也成立吗?

不成立，与数组不同，数组中的任何元素都可以在常数时间内访问，而在链表中访问中间元素是一个 Θ(n) 操作。因此，虽然原则上可以实现，但二分查找对于在（已排序的）链表中搜索将是一个极其低效的算法。

6.

a.设计一个只使用两路比较的折半查找的版本，例如只用≤和=。可以任选一种语言来实现，并认真地调试：众所周知，这类程序很容易有错误。

二路如下：

算法：BinarySearch2Way(A[0..n-1], key)
// 两路比较折半查找，只用 ≤ 和 =
low = 0
high = n – 1
pos = -1

while low ≤ high:
mid = (low + high) // 2
if key ≤ A[mid]:
high = mid – 1
if key == A[mid]:
pos = mid // 记录找到的位置
else:
low = mid + 1

return pos

c版本：

int binarySearch(int A[], int n, int key) {
int low = 0, high = n – 1;
int pos = -1;

while (low <= high) {
int mid = (low + high) / 2;

// 两路比较：只用 ≤ 和 =
if (key <= A[mid]) {
high = mid – 1;
if (key == A[mid])
pos = mid;
} else {
low = mid + 1;
}
}
return pos;
}

b.对于a中设计的两路比较算法，分析其时间效率。

时间效率：O (log n)，因为每次迭代将问题规模减半，循环执行 Θ(log n) 次。

7. 猜图片 一个非常流行的解题游戏是这样的：给选手出示42张图片，每行6张，共7行。选手可以给大家做一些是非题，来确定他要寻找的图片。然后进一步要求选手用尽可能少的问题来确定目标图片。给出解决该问题的最有效的算法，并指出需要提问的最大次数。

先对行二分，再对列二分

最大提问次数：⌈log₂42⌉ = 6 次。

8. 请考虑三重查找(ternary search)————就是下面这个查找有序数组A[0.. n-1]的算法:如果n=1，就把数组中的唯一元素和查找键 K 进行比较。否则，通过比较 K 和A[[n/3]]来进行递归查找。如果 K 较大,把它和A[[2n/3]]进行比较,以确定在数组的三段中的哪一段中继续查找过程。

a.该算法是以哪种算法思想为基础的?

减治（减而治之），减常数因子的算法思想

b.为最差情况下的键值比较次数建立一个递推式(我们可以假设n=3*)。

每次要查三段：

• 先比较 1 次：K 与 A[n/3]
• 若更大，再比较 1 次：K 与 A[2n/3]最坏每次比较 2 次，然后进入规模 n/3 的子问题。

则递推式为：,C(1)=1

c. 在 的情况下解该递推式。

带入n=3^k，则

d.将该算法的效率和折半查找的进行比较。

三重查找的比较次数略多于折半查找，效率比折半查找稍差。两者都是对数级别 Θ(log n)，但折半查找更快。

9.一个数组A[0..n-2]包含n-1个从1到n的整数(因此在这个范围内缺少一个整数)，元素升序排列。尽你所能设计一个求缺失整数的最有效算法，并说明它的时间效率。

算法：FindMissing(A, n)
low = 0
high = n – 2
while low <= high:
mid = (low + high) // 2
// 正常应该满足 A[mid] = mid + 1
if A[mid] > mid + 1:
// 缺失在左边
high = mid – 1
else:
// 缺失在右边
low = mid + 1
return low + 1

10.

a.为假币问题的三分算法写一段伪代码。请确保该算法会正确处理所有的n值，而不仅仅是那些3的倍数。

把硬币分成 三堆，数量尽量相等：

• 堆 1：a 枚
• 堆 2：a 枚
• 堆 3：剩下的（n-2a）枚

称1和2，如果1和2不等，对轻的那一边再进行划分，如果相等，对3进行划分，不断减少规模。

算法：FakeCoin(A[1..n])
// 输入：n 枚硬币，1 枚较轻
// 输出：假币编号

if n == 1:
return 唯一那枚硬币

// 分成三堆（尽可能平均）
a = n // 3
堆1 = A[1 … a]
堆2 = A[a+1 … 2a]
堆3 = A[2a+1 … n]

称 堆1 vs 堆2

if 堆1 < 堆2:
return FakeCoin(堆1)
else if 堆2 < 堆1:
return FakeCoin(堆2)
else:
return FakeCoin(堆3)

b.为假币问题的三分算法的称重次数建立一个递推关系，并在 的情况下对它求解。

n=3^k时，进行递推得：

c.当n的值非常大时，该算法要比把硬币分成两堆的算法快多少倍?这个答案应该与n无关。

约1.58倍

11.

a. 应用俄式乘法来计算26×47。

b.从时间效率的角度看，我们用俄式乘法算法计算n×m和m×n有区别吗?

俄式乘法的循环次数 = 左边那个数不断除以 2 直到 1 的次数

因此较小的数在左边会使得循环次数减少

12.

a.为俄式乘法算法编写伪代码。

算法：RussianMultiplication(n, m)
// 输入：两个正整数 n, m
// 输出：n × m 的结果
// 功能：使用俄式乘法（俄罗斯农民乘法）计算乘积

product ← 0 // 初始化乘积为0

while n ≥ 1 do
if n 是 奇数 then
product ← product + m
n ← ⌊ n / 2 ⌋ // n 除以2，向下取整
m ← m × 2 // m 乘以2

return product

b.说明俄式乘法的时间效率类型。

时间效率为Θ()

13. 求J(40)————在n=40的情况下, 约瑟夫斯问题的解。

• 找不超过 40 的最大 2 的幂：2^5=32

• L=40−32=8

• J(40)=2×8+1=17

14.请证明，对于所有为2的乘方的n来说，它的约瑟夫斯问题的解是1。

• 因为n=2^m
• 所以不超过 n 的最大 2 的幂就是它自己：2^m=n
• 因此L=n−2^m=0
• 代入公式：J(n)=2L+1=2⋅0+1=1

当人数 n=2m 时：

• 第一轮：杀掉所有偶数位的人，剩下全是奇数位：1,3,5,…
• 剩下人数正好是 2^(m-1)，仍然是 2 的乘方。
• 每一轮都如此，每次剩下的都是 2 的乘方，且1 号永远不会被杀。
• 最后只会剩下 1 号。

15.对于约瑟夫斯问题

a. 当n=1,2,…,15, 计算J(n)。

b.通过观察，从前15个n值的解中发现一个模式，然后证明它在一般情况下的正确性。

当 n = 2^m + L 时，先杀掉 L 个人，剩下 2^m 个人，而 2^m 个人的约瑟夫斯解是 1，对应原来的编号就是 2L+1。所以 J (n)=2L+1。

c.有一种做法是将n的二进制表示向左循环移一位来得到J(n)，证明它的正确性。

对于二进制来说：2^m 是 1 后面一串 0L 是 后面那串数

所以 n = 1 + L 的二进制循环左移一位 = L 的二进制后面加个 1= 2L + 1= J(n)