第5讲 计算思维之常用算法设计.pdfVIP

计算思维导论 ——感悟数字化生存的智慧 数计学院 刘光蓉 计算思维之常用算法设计 1 穷举法 5 回溯法 2 递推法 6 分治法 3 递归法 7 贪心法 4 迭代法 8 动态规划 5 计算思维之常用算法设计 1 穷举法 5 回溯法 2 递推法 6 分治法 3 递归法 7 贪心法 4 迭代法 8 动态规划 5 基本思想 采用有哪些信誉好的足球投注网站的方法，根据题目的部分条件确定答案的大致搜 索范围 在此范围内对所有可能的情况逐一验证 若某个情况符合题目的条件，则为本题的一个答案；若全 部情况验证完后均不符合题目的条件，则问题无解。 算法应用举例 【案例一】警察破案 张三在家中遇害，侦查中发现A、B、C、D四人到过现场。 A说：“我没有杀人。” B说：“C是凶手。” C说：“杀人者是D” D说：“C在冤枉好人。” 侦查员经过判断四人中有三人说的是真话，四人中有且只有一 人是凶手，凶手到底是谁？ 算法分析 用0表示不是凶手，1表示凶手，则每个人的取值 范围就是[0，1] 算法描述 在每个人的取值范围 [0，1]的所有可能中进行有哪些信誉好的足球投注网站， 如果表格的组合条件同时满足，即为凶手。 利用伪代码描述算法： For A=0 To 1 For B=0 TO 1 For C=0 To 1 For D=0 To 1 要同时满足 If((A=0)+(C=1)+(D=1)+(D=0))=3 And(A+B+C+D=1) Print A,B,C,D // 输出的值是1的为凶手， 算法应用举例 【案例二】百钱买百鸡问题 百钱买百鸡：鸡翁一，值钱五 鸡母一，值钱三 鸡雏三，值钱一 问翁、母、雏各几何？ 意思是：公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元 钱买100只鸡，求公鸡、母鸡、小鸡的只数。 算法分析 设鸡翁、鸡母、鸡雏的个数分别为x、y、z，根据题意可得如下 方程组： 5x＋3y＋z/3＝100 x＋y＋z＝100 1≤x＜20, 1≤y＜33, 3≤z＜100, z mod 3＝0 测试集合：1≤x＜20, 1≤y＜33，z=3,6,9,...,99 测试条件：5x＋3y＋z/3＝100 x＋y＋z＝100 算法优缺点 穷举法是唯一一种解决所有问题的一般性方法； 即使效率低下，仍可用穷举法求解一些小规模的问题实例； 如果解决的问题实例不多，而穷举法可用一种可接受的速 度对问题求解，那么花时间去设计一个更高效地算法是得 不偿失的。 计算思维之常用算法设计 1 穷举法 5 回溯法 2 递推法 6 分治法 3 递归法