lesson8计算机算法初步.ppt

Lesson 8 计算机算法初步计算机算法初步学习目标学习目标:3 1掌握几个常用的解题算法：穷举、迭代掌握几个常用的解题算法：穷举、迭代3穷举法穷举法2概述概述l穷举法，又称为枚举法，是人们日常生活中常用穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。的一种求解问题的方法。l根据问题中的部分条件（根据问题中的部分条件（已知的条件已知的条件）将所有可）将所有可能解的情况列举出来，然后通过一一验证是否符能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。合整个问题的求解要求，而得到问题的解。3穷举法穷举法21、旅行途中发现自己忘记了开锁的密码，怎么办？2、从某个班中找出所有班干部，需要逐一对每个同学进行查看，判断是否是班干部。3穷举法穷举法2穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进行判断，最终找出正确问题的答案。穷举解题步骤：穷举解题步骤：1、问题解的可能搜索的范围：问题解的可能搜索的范围：用循环或循环嵌套结构实现用循环或循环嵌套结构实现 2、写出符合问题解的条件。写出符合问题解的条件。3穷举法穷举法2所谓素数是指仅能被所谓素数是指仅能被1和自身整除，且和自身整除，且大于等于大于等于2的数值。如的数值。如7，11，17，23等等例1：判断给定整数是否是素数。3穷举法穷举法2问题分析问题分析l为为了了检检查查一一个个整整数数是是不不是是素素数数，可可以以采采用用穷穷举举法法。假假设设给给定定的的整整数数用用x表表示示，则则判判断断过过程程就就是是确确认认x不不能能整整除除以以2x-1之之间间的的任任何何整整数数。这这就就需需要要一一一列举出一列举出2x-1之间的每个整数进行排查。之间的每个整数进行排查。算法描述 NY开始开始输入输入x2 tt xt 加加1x%t=0结束结束输出输出“不是素数不是素数”输出输出“是素数是素数”YNt=xYN#includeintmain()intx,t;printf(“Enteraninteger:”);scanf(“%d”,&x);for(t=2;tx;t+)/*列举小于列举小于x大于大于1的所有整数的所有整数*/if(x%t=0)break;if(t=x)/*是否通过循环条件出口是否通过循环条件出口*/printf(“%disprimen”,x);elseprintf(“%disntprimen”,x);return0;注意判断是否是素数的条件与注意判断是否是素数的条件与判断位置判断位置lesson8_01.c如果要找一个范围内那些是素如果要找一个范围内那些是素数怎么改写程序？数怎么改写程序？#includeintmain()inti,x,y,t,j=0;doprintf(Inputnumericalrange(x,y,xy):n);scanf(%d%d,&x,&y);while(x2|yy);for(i=x;i=y;i+)for(t=2;ti;t+)/*列举小于列举小于i大于大于1的所有整数的所有整数*/if(i%t=0)break;if(t=i)/*是否通过循环条件出口是否通过循环条件出口*/j+;printf(%d%c,i,j%8=0?n:t);return0;每行输出8个数3穷举法穷举法2例例2：百钱买百鸡：百钱买百鸡l“百钱买百鸡百钱买百鸡”是我国古代数学家张丘建提出的一个是我国古代数学家张丘建提出的一个著名的数学问题。假设某人有钱百枚，希望买一百只著名的数学问题。假设某人有钱百枚，希望买一百只鸡；不同的鸡价格不同，公鸡鸡；不同的鸡价格不同，公鸡5枚钱一只，母鸡枚钱一只，母鸡3枚钱枚钱一只，而小鸡一只，而小鸡3只只1枚钱。试问：如果用百枚钱买百只枚钱。试问：如果用百枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几只小鸡。鸡，可以包含几只公鸡、几只母鸡和几只小鸡。3穷举法穷举法2问题分析问题分析l从从题题目目要要求求可可知知：公公鸡鸡、母母鸡鸡和和小小鸡鸡的的数数量量是是有有限限的的，都都不不会会超超过过100100。通通过过对对不不同同数数量量的的公公鸡鸡、母母鸡鸡和和小小鸡鸡进进行行组组合合，可可以以计计算算出出购购买买这这些些鸡鸡所所用用的的花花费费，但但这这个个题题目目要要求求找找出出那那些些花花费费正正好好100100枚枚且且鸡的总数也为鸡的总数也为100100只的情况。只的情况。l因因此此，可可以以采采用用穷穷举举法法，将将不不同同的的公公鸡鸡、母母鸡鸡和和小小鸡的数量枚举一遍，找出那些符合题目要求的解。鸡的数量枚举一遍，找出那些符合题目要求的解。算法描述#include#includeintmain()intx,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);return0;3课堂练习课堂练习3、求所有的三位水仙花数、求所有的三位水仙花数若一个若一个3位自然数的各位数字的位自然数的各位数字的3次方之和次方之和等于它本身等于它本身,则称这个自然数为水仙花数。则称这个自然数为水仙花数。例如例如:153(153=13+33+53)是水仙花数是水仙花数#includeintmain()inti,j,k,x;for(x=100;x1000;x+)i=x/100;j=x/10%10;k=x%10;if(i*i*i+j*j*j+k*k*k=x)printf(x=%dn,x);return0;3递推与迭代法递推与迭代法4概述概述l递推是计算机数值计算中的一个重要算法。其基本递推是计算机数值计算中的一个重要算法。其基本策略是将复杂的运算划分为可以重复操作的若干个策略是将复杂的运算划分为可以重复操作的若干个简单的运算，进而充分利用计算机擅长重复计算的简单的运算，进而充分利用计算机擅长重复计算的特点。特点。l采用递推法进行问题求解的关键在于找出递推公式采用递推法进行问题求解的关键在于找出递推公式和边界条件。和边界条件。3递推与迭代法递推与迭代法4例例3 3：等比数列求和：等比数列求和 l等等比比数数列列是是指指在在一一组组数数据据中中，后后项项和和前前项项之之间间存存在在着着一一个个固固定定的的比比例例关关系系。例例如如：整整数数序序列列3、15、75、375的的初初值值是是3，后后项项与与前前项项是是5倍倍的的关关系系，即即前前项项乘乘以以5得到后项。得到后项。l本本题题要要求求给给定定等等比比序序列列的的首首项项和和比比例例，计计算算这这个个数数列列的前的前10项之和。项之和。3递推与迭代法递推与迭代法4问题分析问题分析l等比数列的递推公式为：等比数列的递推公式为：itemi=itemi-1*ratio后项等于前项乘以比例值后项等于前项乘以比例值sumi=sumi-1+itemi前前i i项之和等于前项之和等于前i-1i-1项之和加当前项项之和加当前项l由于在重复上述递推计算之前，需要将第由于在重复上述递推计算之前，需要将第1 1项的值累加到项的值累加到sumsum中，所以，需要先将中，所以，需要先将itemitem存入存入sumsum中。中。算法描述#includeintmain()longitem,ratio,sum,i;printf(“nEnterthefirstitemandratio:”);scanf(“%ld%ld”,&item,&ratio);sum=item;for(i=1;i10;i+)item*=ratio;sum+=item;printf(“Sumof10itemsis%ldn”,sum);return0;3递推与迭代法递推与迭代法4例例4：求圆周率：求圆周率l圆周率圆周率的计算公式为：的计算公式为：=4 4/3+4/5 4/7+4/9 4/11+l在在程程序序中中，圆圆周周率率应应该该用用单单精精度度类类型型float或或双双精精度类型度类型double来表示。而且有一定的精度要求。来表示。而且有一定的精度要求。3递推与迭代法递推与迭代法4问题分析问题分析l圆周率圆周率的计算公式为：的计算公式为：=4 =4 4/3+4/5 4/3+4/5 4/7+4/9 4/7+4/9 4/11+4/11+l圆圆周周率率是是通通过过将将数数列列4 4、-4/3-4/3、4/54/5求求和和得得到到的的。在在这这个个数数列列中中，每每个个数数据据项项的的取取值值与与前前一一项项及及该该项项的的序序号号存存在着一定的关系。在着一定的关系。3递推与迭代法递推与迭代法4l可可以以通通过过迭迭代代，逐逐个个计计算算出出每每一一个个数数据据项项，再再将将它它们们累累加起来。加起来。l为为了了满满足足要要求求的的精精度度，可可以以通通过过检检查查数数据据项项的的大大小小来来控控制制循循环环的的终终止止。由由于于数数据据项项的的绝绝对对值值是是递递减减的的，且且相相邻邻项项的的符符号号不不同同，如如果果第第n n个个数数据据项项的的绝绝对对值值已已经经小小于于精精度度值，则前值，则前n n项之和一定已经满足精度要求了。项之和一定已经满足精度要求了。算法描述#include#includeintmain()intsign=1;longi=1;doublePI=0.0,item;doitem=sign*4.0/(2*i-1);sign=-sign;PI+=item;i+;while(fabs(item)1e-4);/*数据项精度控制循环数据项精度控制循环*/printf(“PI=%lfn”,PI);return0;3递推与迭代法递推与迭代法4例5：按位分解整数。问题分析问题分析l可可以以利利用用程程序序设设计计语语言言提提供供的的整整除除和和求求余余运运算算实实现现将将整整数分解的目的。数分解的目的。l例例如如，对对于于整整数数7326，用用7326/1000就就得得到到了了最最高高位位7，而而7326%1000得得到到了了其其余余的的位位数数326。但但是是，这这种种方方法法要要求求首首先先获获得得整整数数最最高高位位的的权权，因因此此，算算法法应应该该先先求求整整数数最高位的权，然后从高向低逐个分离出每位数字。最高位的权，然后从高向低逐个分离出每位数字。算法描述 NY开始开始输入输入x计算整数最高位权计算整数最高位权nn=1x/n的余数的余数xn/10 n结束结束打印打印x/n#includeintmain()longx,y,n;printf(“Enteraninteger:”);scanf(“%ld”,&x);y=x;n=1;while(y10)n*=10;y=y/10;doprintf(“%ldt”,x/n);x=x%n;n=n/10;while(n=1);return0;3课堂练习课堂练习5求数列、求数列、8 8的前项的前项#includevoid main()int f1=1,f2=1,f3,k;printf(%dt%dt,f1,f2);for(k=3;k=18;k+)f3=f1+f2;printf(%dt,f3);f1=f2;f2=f3;printf(n);参考程序参考程序:3标志变量法标志变量法6标志变量法的基本思想：标志变量法的基本思想：为了表示处理对象所处的状态（结果），使为了表示处理对象所处的状态（结果），使用一个变量，给其规定若干个值，并且规定用一个变量，给其规定若干个值，并且规定每个值所表示的状态（意义），然后通过判每个值所表示的状态（意义），然后通过判断变量的值来知道程序处理的结果断变量的值来知道程序处理的结果3标志变量法标志变量法6例例6：使用标志变量法判断：使用标志变量法判断9是否是素数是否是素数flag:02,3,4,5,6,7,89能否被能否被2整除整除9能否被能否被3整除整除给给flag赋赋1：改：改变标志变量的变标志变量的值值flag:13标志变量法标志变量法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整除整除结束！结束！#include int main()int n,i,flag;printf(“Enter an integer:”);scanf(“%d”,&n);flag=0;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;3课堂练习课堂练习7从键盘输入从键盘输入10个数，判断这个数，判断这10个数个数里有没有负数里有没有负数#includeintmain()intx,j=0;printf(Enter10integer:n);doj+;scanf(%d,&x);if(x0)/*是否为负数是否为负数*/printf(有负数。有负数。n);while(j11);return0;3课后练习课后练习81、一个数如果恰好等于它的因子之和，这个、一个数如果恰好等于它的因子之和，这个数就称为数就称为“完数完数”。例如。例如6=123.编程找编程找出出1000以内的所有完数。以内的所有完数。2、猴子吃桃问题：猴子第一天摘下若干个桃、猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个子，当即吃了一半，还不瘾，又多吃了一个第二天早上又将剩下的桃子吃掉一半，又多第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第的一半零一个。到第10天早上想再吃时，见天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。只剩下一个桃子了。求第一天共摘了多少。#includeintmain()inti,j,sum=0;for(i=2;i1000;i+)for(j=1;ji;j+)if(i%j=0)sum+=j;if(sum=i)printf(Endofafew:%dn,i);sum=0;return0;1000以内的所有完数：以内的所有完数：#includeintmain()inti,sum=1;for(i=10;i0;i-)printf(sum=%d,%dn,sum,i);sum=(sum+1)*2;printf(sum=:%dn,sum);return0;猴子吃桃问题：猴子吃桃问题：