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