[其它]lesson 7 计算机算法初步ppt课件

1、2022-5-9电气与信息工程学院计算机系张吴波制作2022-5-9电气与信息工程学院计算机系张吴波制作学习目的学习目的:3 1掌握几个常用的解题算法：枚举、迭代掌握几个常用的解题算法：枚举、迭代2022-5-9电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 概述概述l穷举法，又称为枚举法，是人们日常生活中常用穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。的一种求解问题的方法。l根据问题中的部分条件的条件将所有可能解根据问题中的部分条件的条件将所有可能解的情况列举出来，然后通过一一验证是否符合整的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。

2、个问题的求解要求，而得到问题的解。2022-5-9电气与信息工程学院计算机系张吴波制作3穷举法穷举法21、旅行途中发现自己忘记了开锁的密码，怎么办？2、从某个班中找出所有班干部，需要逐一对每个同学进展查看，判断是否是班干部。2022-5-9电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进展判断，最终找出正确问题的答案。 穷举解题步骤：穷举解题步骤：1、问题解的可能搜索的范围：问题解的可能搜索的范围： 用循环或循环嵌套构造实现用循环或循环嵌套构造实现 2、写出符合问题解的条件。写出符合问题解的条件。 2022-5-9电气与信息工

3、程学院计算机系张吴波制作3穷举法穷举法2所谓素数是指仅能被所谓素数是指仅能被1和自身整除，且和自身整除，且大于等于大于等于2的数值。如的数值。如7，11，17，23等等例1：判断给定整数是否是素数 。 2022-5-9电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 问题分析问题分析l为了检查一个整数是不是素数，可以采用穷举法。为了检查一个整数是不是素数，可以采用穷举法。假设给定的整数用假设给定的整数用x表示，那么判断过程就是确表示，那么判断过程就是确认认x不能整除以不能整除以2x-1之间的任何整数。这就需要之间的任何整数。这就需要一一列举出一一列举出2x-1之间的每个整数进展排查。之间的

4、每个整数进展排查。 2022-5-9电气与信息工程学院计算机系张吴波制作 算法描绘 NY开始开始输入输入x2 tt xt 加加1x%t=0结束结束输出输出“不是素数不是素数”输出输出“是素数是素数”YNt = xYN2022-5-9电气与信息工程学院计算机系张吴波制作#include int main int x, t;printf “Enter an integer: ;scanf “%d, &x ;for t = 2; tx; t+ /* 列举小于列举小于x大于大于1的所有整数的所有整数 */ if x%t = 0 break;if t = x /* 是否通过循环条件出口是否通过循

5、环条件出口 */ printf “%d is primen, x ;else printf “%d isnt primen, x ; return 0;注意判断是否是素数的条件与注意判断是否是素数的条件与判断位置判断位置lesson8_01.c2022-5-9电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 例例2：百钱买百鸡：百钱买百鸡l “百钱买百鸡是我国古代数学家张丘建提出的一个百钱买百鸡是我国古代数学家张丘建提出的一个著名的数学问题。假设某人有钱百枚，希望买一百只著名的数学问题。假设某人有钱百枚，希望买一百只鸡；不同的鸡价格不同，公鸡鸡；不同的鸡价格不同，公鸡5枚钱一只，母鸡枚钱一

6、只，母鸡3枚钱枚钱一只，而小鸡一只，而小鸡3只只1枚钱。试问：假如用百枚钱买百只枚钱。试问：假如用百枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几只小鸡。鸡，可以包含几只公鸡、几只母鸡和几只小鸡。 2022-5-9电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 问题分析问题分析l从题目要求可知：公鸡、母鸡和小鸡的数量是有限从题目要求可知：公鸡、母鸡和小鸡的数量是有限的，都不会超过的，都不会超过100100。通过对不同数量的公鸡、母。通过对不同数量的公鸡、母鸡和小鸡进展组合，可以计算出购置这些鸡所用的鸡和小鸡进展组合，可以计算出购置这些鸡所用的花费，但这个题目要求找出那些花费正好花费，但这个

7、题目要求找出那些花费正好100100枚且枚且鸡的总数也为鸡的总数也为100100只的情况。只的情况。l因此，可以采用穷举法，将不同的公鸡、母鸡和小因此，可以采用穷举法，将不同的公鸡、母鸡和小鸡的数量枚举一遍，找出那些符合题目要求的解。鸡的数量枚举一遍，找出那些符合题目要求的解。 2022-5-9电气与信息工程学院计算机系张吴波制作 算法描绘 N Y 开开始始 条条件件判判断断 x 加加 1 结结束束 z=100 x = 100/5 y = 100/3 y 加加 1 z 加加 1 0 x 0 y 0 z 输输出出 x, y, z N Y Y N N Y 2022-5-9电气与信息工程学院计算机系

8、张吴波制作#include #include int main int x, y, z; for x=0; x=100/5; x+ for y=0; y=100/3; y+ for z=0; z=100; z+ if x+y+z =100 &15*x+9*y+z=300 printf “x=%d, y=%d, z=%dn, x, y, z ; return 0;lesson8_02.c2022-5-9电气与信息工程学院计算机系张吴波制作3课堂练习课堂练习3、求所有的三位水仙花数、求所有的三位水仙花数假设一个假设一个3位自然数的各位数字的位自然数的各位数字的3次方之次方之和等于它本身和等

9、于它本身,那么称这个自然数为水仙花那么称这个自然数为水仙花数。数。例如例如:153153=13+33+53是水仙花是水仙花数数2022-5-9电气与信息工程学院计算机系张吴波制作3递推与迭代法递推与迭代法4 概述概述l递推是计算机数值计算中的一个重要算法。其根本递推是计算机数值计算中的一个重要算法。其根本策略是将复杂的运算划分为可以重复操作的假设干策略是将复杂的运算划分为可以重复操作的假设干个简单的运算，进而充分利用计算机擅长重复计算个简单的运算，进而充分利用计算机擅长重复计算的特点。的特点。l采用递推法进展问题求解的关键在于找出递推公式采用递推法进展问题求解的关键在于找出递推公式和边界条件。

10、和边界条件。2022-5-9电气与信息工程学院计算机系张吴波制作3递推与迭代法递推与迭代法4 例例3 3：等比数列求和：等比数列求和 l等比数列是指在一组数据中，后项和前项之前存在着等比数列是指在一组数据中，后项和前项之前存在着一个固定的比例关系。例如：整数序列一个固定的比例关系。例如：整数序列3、15、75、375的初值是的初值是3，后项与前项是，后项与前项是5倍的关系，即前项乘以倍的关系，即前项乘以5得到后项。得到后项。l此题要求给定等比序列的首项和比例，计算这个数列此题要求给定等比序列的首项和比例，计算这个数列的前的前10项之和。项之和。2022-5-9电气与信息工程学院计算机系张吴波制

11、作3递推与迭代法递推与迭代法4 问题分析问题分析l等比数列的递推公式为：等比数列的递推公式为： itemi= itemi-1 * ratio后项等于前项乘以比例值后项等于前项乘以比例值sumi= sumi-1 + itemi前前i i项之和等于前项之和等于前i-1i-1项之和加当前项项之和加当前项l由于在重复上述递推计算之前，需要将第由于在重复上述递推计算之前，需要将第1 1项的值累加到项的值累加到sumsum中，所以，需要先将中，所以，需要先将itemitem存入存入sumsum中。中。 2022-5-9电气与信息工程学院计算机系张吴波制作 算法描绘 N Y 开开始始 输输入入 item,

12、ratio item sum 1 i i 10 item*ratio item 加加一一 sum+itemsum i 加加 1 结结束束 输输出出 sum 2022-5-9电气与信息工程学院计算机系张吴波制作#include int main long item, ratio, sum,i;printf “nEnter the first item and ratio: ;scanf “%ld%ld, &item, &ratio ; sum=item;for i=1; i 10-4 (-1)i+ 14/(2i-1) item P I+ item P I i 加加 1 结结 束束

13、 输输 出出 P I 2022-5-9电气与信息工程学院计算机系张吴波制作#include #include int main int sign = 1; long i = 1; double PI= 0.0, item;do item= sign * 4.0 / 2 * i-1;sign= -sign;PI+= item; i+; while fabs item 1e-4 ; /* 数据项精度控制循环数据项精度控制循环 */ printf “PI = %lfn, PI ; return 0; lesson8_04.c2022-5-9电气与信息工程学院计算机系张吴波制作3递推与迭代法递推与迭代

14、法4例5：按位分解整数。 问题分析问题分析l可以利用程序设计语言提供的整除和求余运算实现将整可以利用程序设计语言提供的整除和求余运算实现将整数分解的目的。数分解的目的。l例如，对于整数例如，对于整数7326，用，用7326/1000就得到了最高位就得到了最高位7，而而7326%1000得到了其余的位数得到了其余的位数326。但是，这种方法要。但是，这种方法要求首先获得整数最高位的权，因此，算法应该先求整数求首先获得整数最高位的权，因此，算法应该先求整数最高位的权，然后从高向低逐个别离出每位数字。最高位的权，然后从高向低逐个别离出每位数字。 2022-5-9电气与信息工程学院计算机系张吴波制作

15、算法描绘 NY开始开始输入输入x计算整数最高位权计算整数最高位权nn = 1x/n的余数的余数xn/10 n结束结束打印打印x/n2022-5-9电气与信息工程学院计算机系张吴波制作#include int main long x, y, n;printf “Enter an integer: ;scanf “%ld, &x ; y =x; n =1; while y10 n *= 10; y = y/10; do printf “%ldt, x / n ;x=x % n;n=n / 10; while n = 1 ; return 0; lesson8_05.c2022-5-9电气与

16、信息工程学院计算机系张吴波制作3课堂练习课堂练习5求数列、求数列、8 8的前项的前项2022-5-9电气与信息工程学院计算机系张吴波制作3标志变量法标志变量法6标志变量法的根本思想：标志变量法的根本思想：为了表示处理对象所处的状态结果，使为了表示处理对象所处的状态结果，使用一个变量，给其规定假设干个值，并且规用一个变量，给其规定假设干个值，并且规定每个值所表示的状态意义，然后通过定每个值所表示的状态意义，然后通过判断变量的值来知道程序处理的结果判断变量的值来知道程序处理的结果2022-5-9电气与信息工程学院计算机系张吴波制作3标志变量法标志变量法6例例6：使用标志变量法判断：使用标志变量法判

17、断9是否是素数是否是素数flag:02 , 3 , 4 , 5 , 6 , 7 , 89能否被能否被2 整除整除9能否被能否被3 整除整除给给flag赋赋1：改：改变标志变量的变标志变量的值值flag:12022-5-9电气与信息工程学院计算机系张吴波制作3标志变量法标志变量法6使用标志变量法判断使用标志变量法判断11是否是素数是否是素数flag:02 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 1011能否被能否被2 整除整除11能否被能否被3 整除整除11能否被能否被4 整除整除11能否被能否被5 整除整除11能否被能否被6 整除整除11能否被能否被7 整除整除11能否被能

18、否被8 整除整除11能否被能否被9 整除整除11能否被能否被10 整除整除完毕！完毕！2022-5-9电气与信息工程学院计算机系张吴波制作#include int main int n, i,flag; printf “Enter an integer: ; scanf “%d, &n; flag=0; fori=2;i=n/2;i+ ifn%i=0 flag=1; break; ifflag=1 printf“%d不是素数不是素数,n; else printf“%d是素数是素数,n; return 0;lesson8_06.c2022-5-9电气与信息工程学院计算机系张吴波制作3课堂练习课堂练习72022-5-9电气与信息工程学院计算机系张吴波制作3课后练习课后练习81、一个数假如恰好等于它的因子之和，这个、一个数假如恰好等于它的因子之