1、2022-11-7电气与信息工程学院计算机系张吴波制作学习目标学习目标:3 1掌握几个常用的解题算法：枚举、迭代掌握几个常用的解题算法：枚举、迭代2022-11-7电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 概述概述l穷举法，又称为枚举法，是人们日常生活中常用穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。的一种求解问题的方法。l根据问题中的部分条件（已知的条件）将所有可根据问题中的部分条件（已知的条件）将所有可能解的情况列举出来，然后通过一一验证是否符能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。合整个问题的求解要求，而得到问题的解
2、。2022-11-7电气与信息工程学院计算机系张吴波制作3穷举法穷举法21、旅行途中发现自己忘记了开锁的密码，怎么办？2、从某个班中找出所有班干部，需要逐一对每个同学进行查看，判断是否是班干部。2022-11-7电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进行判断，最终找出正确问题的答案。穷举解题步骤：穷举解题步骤：1、问题解的可能搜索的范围：问题解的可能搜索的范围：用循环或循环嵌套结构实现用循环或循环嵌套结构实现 2、写出符合问题解的条件。写出符合问题解的条件。2022-11-7电气与信息工程学院计算机系张吴波制作3穷举法
3、穷举法2所谓素数是指仅能被所谓素数是指仅能被1和自身整除，且和自身整除，且大于等于大于等于2的数值。如的数值。如7，11，17，23等等例1：判断给定整数是否是素数。2022-11-7电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 问题分析问题分析l为了检查一个整数是不是素数，可以采用穷举法。为了检查一个整数是不是素数，可以采用穷举法。假设给定的整数用假设给定的整数用x表示，则判断过程就是确认表示，则判断过程就是确认x不能整除以不能整除以2x-1之间的任何整数。这就需要一之间的任何整数。这就需要一一列举出一列举出2x-1之间的每个整数进行排查。之间的每个整数进行排查。2022-11-7电
4、气与信息工程学院计算机系张吴波制作 算法描述 NY开始开始输入输入x2 tt xt 加加1x%t=0结束结束输出输出“不是素数不是素数”输出输出“是素数是素数”YNt=xYN2022-11-7电气与信息工程学院计算机系张吴波制作#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)/*是否通过循环条件出口是否通过循环条件出口*/printf(“%d is primen”,x);els
5、e printf(“%d isnt primen”,x);return 0;注意判断是否是素数的条件与注意判断是否是素数的条件与判断位置判断位置lesson8_01.c2022-11-7电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 例例2：百钱买百鸡：百钱买百鸡l“百钱买百鸡百钱买百鸡”是我国古代数学家张丘建提出的一个著名的数学问题。是我国古代数学家张丘建提出的一个著名的数学问题。假设某人有钱百枚，希望买一百只鸡；不同的鸡价格不同，公鸡假设某人有钱百枚，希望买一百只鸡；不同的鸡价格不同，公鸡5枚钱枚钱一只，母鸡一只，母鸡3枚钱一只，而小鸡枚钱一只，而小鸡3只只1枚钱。试问：如果用百枚钱
6、买百只枚钱。试问：如果用百枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几只小鸡。鸡，可以包含几只公鸡、几只母鸡和几只小鸡。2022-11-7电气与信息工程学院计算机系张吴波制作3穷举法穷举法2 问题分析问题分析l从题目要求可知：公鸡、母鸡和小鸡的数量是有限的，都不会超过从题目要求可知：公鸡、母鸡和小鸡的数量是有限的，都不会超过100100。通过对不同数量的公鸡、母鸡和小鸡进行组合，可以计算出购。通过对不同数量的公鸡、母鸡和小鸡进行组合，可以计算出购买这些鸡所用的花费，但这个题目要求找出那些花费正好买这些鸡所用的花费，但这个题目要求找出那些花费正好100100枚且鸡枚且鸡的总数也为的总数也为100
7、100只的情况。只的情况。l因此，可以采用穷举法，将不同的公鸡、母鸡和小鸡的数量枚举一因此，可以采用穷举法，将不同的公鸡、母鸡和小鸡的数量枚举一遍，找出那些符合题目要求的解。遍，找出那些符合题目要求的解。2022-11-7电气与信息工程学院计算机系张吴波制作 算法描述 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-11-7电气与信息工程学院计算机系张吴波制作#include#include int main()int x,y,z;
8、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-11-7电气与信息工程学院计算机系张吴波制作3课堂练习课堂练习3、求所有的三位水仙花数、求所有的三位水仙花数若一个若一个3位自然数的各位数字的位自然数的各位数字的3次方之和次方之和等于它本身等于它本身,则称这个自然数为水仙花数。则称这个自然数为水仙花数。例如例如:153(153=13+33+53)是水仙花数是水仙花数
9、2022-11-7电气与信息工程学院计算机系张吴波制作3递推与迭代法递推与迭代法4 概述概述l递推是计算机数值计算中的一个重要算法。其基本策略是将复杂的运递推是计算机数值计算中的一个重要算法。其基本策略是将复杂的运算划分为可以重复操作的若干个简单的运算，进而充分利用计算机擅算划分为可以重复操作的若干个简单的运算，进而充分利用计算机擅长重复计算的特点。长重复计算的特点。l采用递推法进行问题求解的关键在于找出递推公式和边界条件。采用递推法进行问题求解的关键在于找出递推公式和边界条件。2022-11-7电气与信息工程学院计算机系张吴波制作3递推与迭代法递推与迭代法4 例例3 3：等比数列求和：等比数
10、列求和 l等比数列是指在一组数据中，后项和前项之前存在着一个固定的比例关等比数列是指在一组数据中，后项和前项之前存在着一个固定的比例关系。例如：整数序列系。例如：整数序列3、15、75、375的初值是的初值是3，后项与前项是，后项与前项是5倍的关倍的关系，即前项乘以系，即前项乘以5得到后项。得到后项。l本题要求给定等比序列的首项和比例，计算这个数列的前本题要求给定等比序列的首项和比例，计算这个数列的前10项之和。项之和。2022-11-7电气与信息工程学院计算机系张吴波制作3递推与迭代法递推与迭代法4 问题分析问题分析l等比数列的递推公式为：等比数列的递推公式为：itemi=itemi-1*r
11、atio后项等于前项乘以比例值后项等于前项乘以比例值sumi=sumi-1+itemi前前i i项之和等于前项之和等于前i-1i-1项之和加当前项项之和加当前项l由于在重复上述递推计算之前，需要将第由于在重复上述递推计算之前，需要将第1 1项的值累加到项的值累加到sumsum中，所以，需要中，所以，需要先将先将itemitem存入存入sumsum中。中。2022-11-7电气与信息工程学院计算机系张吴波制作 算法描述 N Y 开开始始 输输入入 item,ratio item sum 1 i i 10 item*ratio item 加加一一 sum+itemsum i 加加 1 结结束束 输
12、输出出 sum 2022-11-7电气与信息工程学院计算机系张吴波制作#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 结结 束束 输输 出出 P I 2022-11-7电气与信息工程学院计算机系张吴波制作#include#include int main()int sign=1;long i=1
13、;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-11-7电气与信息工程学院计算机系张吴波制作3递推与迭代法递推与迭代法4例5：按位分解整数。问题分析问题分析l可以利用程序设计语言提供的整除和求余运算实现将整数分解的目的。可以利用程序设计语言提供的整除和求余运算实现将整数分解的目的。l例如，对于整数例如，对于整数7326，用，用7
14、326/1000就得到了最高位就得到了最高位7，而，而7326%1000得到得到了其余的位数了其余的位数326。但是，这种方法要求首先获得整数最高位的权，因此，。但是，这种方法要求首先获得整数最高位的权，因此，算法应该先求整数最高位的权，然后从高向低逐个分离出每位数字。算法应该先求整数最高位的权，然后从高向低逐个分离出每位数字。2022-11-7电气与信息工程学院计算机系张吴波制作 算法描述 NY开始开始输入输入x计算整数最高位权计算整数最高位权nn=1x/n的余数的余数xn/10 n结束结束打印打印x/n2022-11-7电气与信息工程学院计算机系张吴波制作#include int main
15、()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-11-7电气与信息工程学院计算机系张吴波制作3课堂练习课堂练习5求数列、求数列、8 8的前项的前项2022-11-7电气与信息工程学院计算机系张吴波制作3标志变量法标志变量法6标志变量法的基本思想：标志变量法的基本思想：为了表示处理对象所处的状态（结果），使为了表示处理对象所处的
16、状态（结果），使用一个变量，给其规定若干个值，并且规定用一个变量，给其规定若干个值，并且规定每个值所表示的状态（意义），然后通过判每个值所表示的状态（意义），然后通过判断变量的值来知道程序处理的结果断变量的值来知道程序处理的结果2022-11-7电气与信息工程学院计算机系张吴波制作3标志变量法标志变量法6例例6：使用标志变量法判断：使用标志变量法判断9是否是素数是否是素数flag:02,3,4,5,6,7,89能否被能否被2 整除整除9能否被能否被3 整除整除给给flag赋赋1：改：改变标志变量的变标志变量的值值flag:12022-11-7电气与信息工程学院计算机系张吴波制作3标志变量法标志
17、变量法6使用标志变量法判断使用标志变量法判断11是否是素数是否是素数flag:02,3,4,5,6,7,8,9,1011能否被能否被2 整除整除11能否被能否被3 整除整除11能否被能否被4 整除整除11能否被能否被5 整除整除11能否被能否被6 整除整除11能否被能否被7 整除整除11能否被能否被8 整除整除11能否被能否被9 整除整除11能否被能否被10 整除整除结束！结束！2022-11-7电气与信息工程学院计算机系张吴波制作#include int main()int n,i,flag;printf(“Enter an integer:”);scanf(“%d”,&n);flag=0;
18、for(i=2;i=n/2;i+)if(n%i=0)flag=1;break;if(flag=1)printf(“%d不是素数不是素数”,n);else printf(“%d是素数是素数”,n);return 0;lesson8_06.c2022-11-7电气与信息工程学院计算机系张吴波制作3课堂练习课堂练习72022-11-7电气与信息工程学院计算机系张吴波制作3课后练习课后练习81、一个数如果恰好等于它的因子之和，这个、一个数如果恰好等于它的因子之和，这个数就称为数就称为“完数完数”。例如。例如6=123.编程找编程找出出1000以内的所有完数。以内的所有完数。2、猴子吃桃问题：猴子第一天摘下若干个桃、猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个子，当即吃了一半，还不瘾，又多吃了一个第二天早上又将剩下的桃子吃掉一半，又多第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第的一半零一个。到第10天早上想再吃时，见天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。只剩下一个桃子了。求第一天共摘了多少。
