lesson8计算机算法初步.ppt
《lesson8计算机算法初步.ppt》由会员分享,可在线阅读,更多相关《lesson8计算机算法初步.ppt(37页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Lesson 8 计算机算法初步计算机算法初步学习目标学习目标:3 1掌握几个常用的解题算法:穷举、迭代掌握几个常用的解题算法:穷举、迭代3穷举法穷举法2概述概述l穷举法,又称为枚举法,是人们日常生活中常用穷举法,又称为枚举法,是人们日常生活中常用的一种求解问题的方法。的一种求解问题的方法。l根据问题中的部分条件(根据问题中的部分条件(已知的条件已知的条件)将所有可)将所有可能解的情况列举出来,然后通过一一验证是否符能解的情况列举出来,然后通过一一验证是否符合整个问题的求解要求,而得到问题的解。合整个问题的求解要求,而得到问题的解。3穷举法穷举法21、旅行途中发现自己忘记了开锁的密码,怎么办?
2、2、从某个班中找出所有班干部,需要逐一对每个同学进行查看,判断是否是班干部。3穷举法穷举法2穷举法的核心在于明确问题的所有可能性,并针对每种可能情况逐个进行判断,最终找出正确问题的答案。穷举解题步骤:穷举解题步骤:1、问题解的可能搜索的范围:问题解的可能搜索的范围:用循环或循环嵌套结构实现用循环或循环嵌套结构实现 2、写出符合问题解的条件。写出符合问题解的条件。3穷举法穷举法2所谓素数是指仅能被所谓素数是指仅能被1和自身整除,且和自身整除,且大于等于大于等于2的数值。如的数值。如7,11,17,23等等例1:判断给定整数是否是素数。3穷举法穷举法2问题分析问题分析l为为了了检检查查一一个个整整
3、数数是是不不是是素素数数,可可以以采采用用穷穷举举法法。假假设设给给定定的的整整数数用用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+)/*列举小于列举
4、小于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,
5、&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“百钱买百鸡百钱买百鸡”是我国古代数学家张丘建提出的一个是我国古代数学家张丘建提出的一个著名的数学问题。假设某人有钱百枚,希望买一百只著名的数学问题。假设某人有钱百枚,希望买一百只鸡;不同的鸡价格不同,公鸡鸡;不同的鸡价格不同
6、,公鸡5枚钱一只,母鸡枚钱一只,母鸡3枚钱枚钱一只,而小鸡一只,而小鸡3只只1枚钱。试问:如果用百枚钱买百只枚钱。试问:如果用百枚钱买百只鸡,可以包含几只公鸡、几只母鸡和几只小鸡。鸡,可以包含几只公鸡、几只母鸡和几只小鸡。3穷举法穷举法2问题分析问题分析l从从题题目目要要求求可可知知:公公鸡鸡、母母鸡鸡和和小小鸡鸡的的数数量量是是有有限限的的,都都不不会会超超过过100100。通通过过对对不不同同数数量量的的公公鸡鸡、母母鸡鸡和和小小鸡鸡进进行行组组合合,可可以以计计算算出出购购买买这这些些鸡鸡所所用用的的花花费费,但但这这个个题题目目要要求求找找出出那那些些花花费费正正好好100100枚枚且
7、且鸡的总数也为鸡的总数也为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、求所有的三位水仙花数、求所
8、有的三位水仙花数若一个若一个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递推是计算机数值计算中的一个重要算法。其基本递推是计算机数值计算中的一个重要算法。其基本策略是将复
9、杂的运算划分为可以重复操作的若干个策略是将复杂的运算划分为可以重复操作的若干个简单的运算,进而充分利用计算机擅长重复计算的简单的运算,进而充分利用计算机擅长重复计算的特点。特点。l采用递推法进行问题求解的关键在于找出递推公式采用递推法进行问题求解的关键在于找出递推公式和边界条件。和边界条件。3递推与迭代法递推与迭代法4例例3 3:等比数列求和:等比数列求和 l等等比比数数列列是是指指在在一一组组数数据据中中,后后项项和和前前项项之之间间存存在在着着一一个个固固定定的的比比例例关关系系。例例如如:整整数数序序列列3、15、75、375的的初初值值是是3,后后项项与与前前项项是是5倍倍的的关关系系
10、,即即前前项项乘乘以以5得到后项。得到后项。l本本题题要要求求给给定定等等比比序序列列的的首首项项和和比比例例,计计算算这这个个数数列列的前的前10项之和。项之和。3递推与迭代法递推与迭代法4问题分析问题分析l等比数列的递推公式为:等比数列的递推公式为:itemi=itemi-1*ratio后项等于前项乘以比例值后项等于前项乘以比例值sumi=sumi-1+itemi前前i i项之和等于前项之和等于前i-1i-1项之和加当前项项之和加当前项l由于在重复上述递推计算之前,需要将第由于在重复上述递推计算之前,需要将第1 1项的值累加到项的值累加到sumsum中,所以,需要先将中,所以,需要先将it
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- lesson8 计算机 算法 初步
限制150内