(陈慧南 第3版)算法设计与分析——第1章课后习题答案.pdf

第一章课后习题 姓名 赵文浩 学号 16111204082 班级 2016 级计算机科学与技术 1 4 证明等式 gcd m n gcd n mod m m 对每对正整数 m 和 n m 0 都成立 证明 我们不妨记 x gcd m n y gcd n mod m m 因此有 x m x n y n mod m y m 对于 n 可以用 m 表示为 n k m n mod m 且 y n mod m 因此结合 可知 y n 结合 和 可知 y m y n 因此 y 一定是 m 和 n 的一个公约数 又因为 x 是 m 和 n 的最大公约数 因此有 y x 结合 y x 可知 x y 因此 gcd m n gcd n mod m m 证毕 1 12 试用归纳法证明程序 1 7 的排列产生器算法的正确性 证明 主函数中 程序调用 perm a 0 n 实现排列产生器 当 n 1 时 即数组 a 中仅包含一个元素 函数内 k 0 与 n 1 0 相等 因此函 数内仅执行 if k n 1 下的 for 语句块 且只执行一次 即将 a 数组中的一个元 素输出 实现了对一个元素的全排列 因此当 n 1 时 程序是显然正确的 我们假设程序对于 n k 1 仍能够满足条件 将 k 1 个元素的全排列产生并输出 当 n k 时 程序执行 else 下语句块的内容 首先执行 swap a 0 a 0 然后执 行 Perm a 1 n 根据假设 可知 该语句能够产生以 a 0 为第一个元素 余下 k 1 个元素的全排列 然后再次执行 swap a 0 a 0 并进行下一次循环 此时 i 1 即在本次循环中 先执行 swap a 0 a 1 将第二个元素与第一个元素互换 下面执行 Perm a 1 n 根据假设 可知 该语句产生以 a 1 为第一个元素 余下 k 1 个元素的全排列 以此类推 该循环每一次将各个元素调到首位 通过执行语句 Perm a 1 n 以及 基于假设 能够实现产生 k 个元素的全排列 因此 n k 时 程序仍满足条件 综上所述 该排列器产生算法是正确的 证毕 1 13 写一个递归算法和一个迭代算法计算二项式系数 include int Coef recursive int n int m 递归算法 int Coef iteration int n int m 迭代算法 int Factorial int n 计算 n 的阶乘 int main int n m while n 0 m 0 n m printf 请输入合法的 m 和 n 的值 n 在前 m 在后 n scanf d d 注意 n 和 m 输入次序 printf 采用迭代算法得到的结果为 d n Coef iteration n m printf 采用递归算法得到的结果为 d n Coef recursive n m return 0 int Factorial int n 计算 n 的阶乘 if n 1 n 0 注意基本情况下规定 0 和 1 的阶乘为 1 return 1 return n Factorial n 1 int Coef iteration int n int m 迭代算法 return Factorial n Factorial m Factorial n m int Coef recursive int n int m 递归算法 if n 1 if n 0 return 0 基础情况 return Coef recursive n 1 m Coef recursive n 1 m 1 递归部分 1 14 给定一个字符串 s 和一个字符 x 编写递归算法实现以下功能 1 检查 x 是否出现在 s 中 2 计算 x 在 s 中出现的次数 3 删除 s 中所有 x include int GetNum char s char x void DeleteChar char s char x void DeleteFirstChar char s 辅助函数 用于删除字符串 s 的首位字符元素 int main char s 100 char x int num 0 printf 请输入字符串 s n scanf s s getchar printf 请输入字符 x n scanf c num GetNum s x if num 0 printf 字符 c 未在字符串 s 中出现 n x else printf 字符 c 在字符串 s 中出现 且出现 d 次 n x num DeleteFirstChar s 测试能否实现首位字符元素的删除 DeleteChar s x printf 在字符串 s 中删除字符 c 后为 s n x s return 0 int GetNum char s char x 统计字符 x 在字符串 s 中出现的次数 int count 0 if s if s x count count GetNum s 1 x return count void DeleteChar char s char x 在字符串 s 中删除所有字符 x int flag 0 用于判断首位元素是否被删除的标志 if s if s x flag 1 DeleteFirstChar s if flag 1 若首位元素被删除 那么执行 DeleteChar s x 继续检查第一个 字符是否为 x 并做相应操作 DeleteChar s x else DeleteChar s 1 x 若首位元素未被删除 那么执