lesson计算机算法初步

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