算法设计与分析-习题4.3

目录1.在你的计算机上实现一个要求生成 25 个元素组成的集合的全部排列的算法是否现实?如果是生成该集合的所有子集呢?2.使用下面的方法生成{1234}的全部排列a.从底向上的最小变化算法。b. Johnson-Trotter算法。​编辑c.字典序算法。3. 把 LexicographicPermute算法应用到多重集{1,2,2,3}上。它是否能正确生成字典序的所有排列?4.请考虑下面这个生成排列算法的实现这个算法是由 B.希普(B. Heap)发明的([Hea63])。a.对于n2,3,4的情况手工跟踪该算法。b.证明 Heap算法的正确性。c. HeapPermute的时间效率如何?5.用本节介绍的两种算法分别对一个4元素的集合A(a₁,a₂,a₃,a₄)生成它的所有子集。6.有什么简单的小窍门可以使得基于位串的算法可以按照挤压序生成子集?7.有一个生成所有2ⁿ个长度为n的位串的递归算法为它编写伪代码。8.写一个生成2ⁿ个长度为n的位串的非递归算法它用数组来实现位串并且不使用二进制加法。9.a.生成4位的二进制反射格雷码。b.跟踪下面生成4位二进制反射格雷码的非递归算法。以全0的n位串开始。而对于 i1,2,…,2ⁿ⁻¹,则通过反转前一位串中的第b位来生成第i个位串在这里b是i的二进制表示中最低位1的位置。10.设计一个减治算法来生成n个元素的k个分量的所有组合也就是说一个给定的n元素集合的所有k元素子集。你设计的算法是最小变化算法吗?11.格雷码和汉诺塔a.为什么汉诺塔的经典递归算法产生的移动盘子动作可以用来生成二进制反射格雷码?b.如何利用二进制反射格雷码来解汉诺塔问题?12.展会彩灯 早些年在展会上可能会看到这样一种彩灯一个被连接到若干开关上的电灯泡只当所有开关都闭合的时候才会发光。每一个开关由一个按钮控制按下按钮就会切换开关状态但是开关的状态是无法知道的。目标就是点亮灯泡。设计一个点亮灯泡的算法使其在有n个开关时在最坏的情况下需要按动按钮的次数最少。1.在你的计算机上实现一个要求生成 25 个元素组成的集合的全部排列的算法是否现实?如果是生成该集合的所有子集呢?由于 25!≈1.5·10^25即使在超级计算机上生成这么多排列也需要不切实际的长时间。另一方面2^25≈3.3·10^7在每秒进行一亿次操作的计算机上生成大约需要 0.3 秒。2.使用下面的方法生成{1234}的全部排列a.从底向上的最小变化算法。b. Johnson-Trotter算法。c.字典序算法。3.把 LexicographicPermute算法应用到多重集{1,2,2,3}上。它是否能正确生成字典序的所有排列?1223,1232,1322,2123,2132,2213,2231,2312,2321,3122,3212,32214.请考虑下面这个生成排列算法的实现这个算法是由 B.希普(B. Heap)发明的([Hea63])。算法 HeapPermute(n) //实现生成排列的 Heap 算法 //输入一个正整数n和一个全局数组A[1..n] //输出 A中元素的全排列 if n1 write A else for i←1 to n do HeapPermute(n-1) if n is odd swap A[1] and A[n] else swap A[i] and A[n]a.对于n2,3,4的情况手工跟踪该算法。n2时HeapPermute(2) i1: HeapPermute(1) → 输出 [1,2] n 偶数 → swap A[1] ↔ A[2] → A[2,1] 循环结束 输出 1 2 2 1n3 时HeapPermute(3) i1: HeapPermute(2) → 输出 123, 213 n 奇数 → swap A[1] ↔ A[3] → A[3,1,2] i2: HeapPermute(2) → 输出 312, 132 n 奇数 → swap A[1] ↔ A[3] → A[2,1,3] i3: HeapPermute(2) → 输出 213, 123 n 奇数 → swap A[1] ↔ A[3] → A[3,1,2]b.证明 Heap算法的正确性。基例 n1直接输出数组唯一排列成立。归纳假设假设HeapPermute(k)能正确生成 k 个元素的全部 k! 个排列。归纳步骤 n k1循环执行 n 次每次调用HeapPermute(n-1)生成前 n-1 个元素的全部排列。n 偶数交换A[i] ↔ A[n]把第 n 个位置换上新元素。n 奇数交换A[1] ↔ A[n]固定轮换最后一位。每次调用都生成完整的 (n-1)! 个排列共 n 次 → 总排列数 n×(n-1)! n!。c. HeapPermute的时间效率如何?时间效率O (n!)5.用本节介绍的两种算法分别对一个4元素的集合A(a₁,a₂,a₃,a₄)生成它的所有子集。自底向上n0: { } n1: { }, {a₁} n2: { }, {a₁}, {a₂}, {a₁,a₂} n3: { }, {a₁}, {a₂}, {a₁,a₂}, {a₃}, {a₁,a₃}, {a₂,a₃}, {a₁,a₂,a₃} n4: 在上面所有子集后面依次添加 a₄二进制0000 → { } 0001 → {a₁} 0010 → {a₂} 0011 → {a₁,a₂} 0100 → {a₃} 0101 → {a₁,a₃} 0110 → {a₂,a₃} 0111 → {a₁,a₂,a₃} 1000 → {a₄} 1001 → {a₁,a₄} 1010 → {a₂,a₄} 1011 → {a₁,a₂,a₄} 1100 → {a₃,a₄} 1101 → {a₁,a₃,a₄} 1110 → {a₂,a₃,a₄} 1111 → {a₁,a₂,a₃,a₄}{ }, {a₁}, {a₂}, {a₁,a₂}, {a₃}, {a₁,a₃}, {a₂,a₃}, {a₁,a₂,a₃}, {a₄}, {a₁,a₄}, {a₂,a₄}, {a₁,a₂,a₄}, {a₃,a₄}, {a₁,a₃,a₄}, {a₂,a₃,a₄}, {a₁,a₂,a₃,a₄}6.有什么简单的小窍门可以使得基于位串的算法可以按照挤压序生成子集?把数字按照二进制格雷码Gray Code的顺序生成而不是普通的 0,1,2,3... 顺序7.有一个生成所有2ⁿ个长度为n的位串的递归算法为它编写伪代码。算法GenerateAllBits(n) 输入正整数 n 输出所有长度为 n 的二进制位串 // 辅助递归函数 过程 Backtrack(pos, current[]) if pos n 输出 current[] // 生成完成打印位串 return // 当前位置放 0 current[pos] 0 Backtrack(pos 1, current) // 当前位置放 1 current[pos] 1 Backtrack(pos 1, current) // 主算法 主函数 定义数组 current[1..n] Backtrack(1, current)8.写一个生成2ⁿ个长度为n的位串的非递归算法它用数组来实现位串并且不使用二进制加法。初始化全 0每次找最右边的 0 变为 1其右侧全部置 0循环直到生成全部 2ⁿ个串。不使用二进制加法。算法BitStringIterative(n) // 非递归生成所有长度为n的二进制位串 // 不使用二进制加法用数组实现 输入正整数 n 输出所有 2ⁿ 个长度为 n 的位串 A[1..n] ← {0} // 初始化全0数组 输出 A for i ← 1 to 2ⁿ − 1 do // 找最右边的0把它变成1 j ← n while j ≥ 1 and A[j] 1 do j ← j − 1 A[j] ← 1 // 最右0 → 1 // j 右边全部变回 0 for k ← j1 to n do A[k] ← 0 输出 A9.a.生成4位的二进制反射格雷码。0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000b.跟踪下面生成4位二进制反射格雷码的非递归算法。以全0的n位串开始。而对于 i1,2,…,2ⁿ⁻¹,则通过反转前一位串中的第b位来生成第i个位串在这里b是i的二进制表示中最低位1的位置。同a一样10.设计一个减治算法来生成n个元素的k个分量的所有组合也就是说一个给定的n元素集合的所有k元素子集。你设计的算法是最小变化算法吗?全局数组A[1..k] // 存放当前组合 主调用Choose(1, k) 过程 Choose(i, k) // 生成 {i, i1, ..., n} 中所有 k 元子集 // 结果存在 A 里按**降序**输出 if k 0 输出 A else for j i to n - k 1 do A[k] j // 把 j 放在第 k 位最后一位 Choose(j 1, k - 1)不是最小变化算法因为相邻组合可能变化多个元素不满足相邻仅变化一个元素的条件11.格雷码和汉诺塔a.为什么汉诺塔的经典递归算法产生的移动盘子动作可以用来生成二进制反射格雷码?因为汉诺塔每次只移动 1 个盘子而格雷码相邻两个数也正好只变 1 位它们的 “最小变化” 结构完全一样b.如何利用二进制反射格雷码来解汉诺塔问题?000 → 001 → 011 → 010 → 110 …… 第1位变 第2位变 第1位变 第3位变……对应的汉诺塔移动1号盘 → 移动2号盘 → 移动1号盘 → 移动3号盘……12.展会彩灯 早些年在展会上可能会看到这样一种彩灯一个被连接到若干开关上的电灯泡只当所有开关都闭合的时候才会发光。每一个开关由一个按钮控制按下按钮就会切换开关状态但是开关的状态是无法知道的。目标就是点亮灯泡。设计一个点亮灯泡的算法使其在有n个开关时在最坏的情况下需要按动按钮的次数最少。按照 n 位二进制反射格雷码的顺序依次切换每一步变化的那一位开关。此时递推式为最坏情况只需要按 2ⁿ − 1 次