lesson8计算机算法初步.ppt

Lesson 8 计算机算法初步,学习目标:,1,掌握几个常用的解题算法：穷举、迭代,概述 穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。 根据问题中的部分条件（已知的条件）将所有可能解的情况列举出来，然后通过一一验证是否符合整个问题的求解要求，而得到问题的解。,1、旅行途中发现自己忘记了开锁的密码，怎么办？,2、从某个班中找出所有班干部，需要逐一对每个同学进行查看，判断是否是班干部。,穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进行判断，最终找出正确问题的答案。,穷举解题步骤：,1、问题解的可能搜索的范围： 用循环或循环嵌套结构实现 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 main( ) 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枚钱一只，母鸡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+ ) 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; ,概述 递推是计算机数值计算中的一个重要算法。其基本策略是将复杂的运算划分为可以重复操作的若干个简单的运算，进而充分利用计算机擅长重复计算的特点。 采用递推法进行问题求解的关键在于找出递推公式和边界条件。,例3：等比数列求和 等比数列是指在一组数据中，后项和前项之间存在着一个固定的比例关系。例如：整数序列3、15、75、375的初值是3，后项与前项是5倍的关系，即前项乘以5得到后项。 本题要求给定等比序列的首项和比例，计算这个数列的前10项之和。,问题分析 等比数列的递推公式为： itemi = itemi-1 * ratio 后项等于前项乘以比例值 sumi = sumi-1 + itemi 前i项之和等于前i-1项之和加当前项 由于在重复上述递推计算之前，需要将第1项的值累加到sum中，所以，需要先将item存入sum中。,算法描述,#include int main( ) long item, ratio, sum,i; printf( “nEnter the first item and ratio: ” ); scanf( “%ld%ld”, ,例4：求圆周率 圆周率的计算公式为： = 4 4/3 + 4/5 4/7 +4/9 4/11 + 在程序中，圆周率应该用单精度类型float或双精度类型double来表示。而且有一定的精度要求。,问题分析 圆周率的计算公式为： = 4 4/3 + 4/5 4/7 +4/9 4/11 + 圆周率是通过将数列4、-4/3、4/5求和得到的。在这个数列中，每个数据项的取值与前一项及该项的序号存在着一定的关系。,可以通过迭代，逐个计算出每一个数据项，再将它们累加起来。 为了满足要求的精度，可以通过检查数据项的大小来控制循环的终止。由于数据项的绝对值是递减的，且相邻项的符号不同，如果第n个数据项的绝对值已经小于精度值，则前n项之和一定已经满足精度要求了。,算法描述,#include #include int main( ) int sign = 1; long i = 1; 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; ,例5：按位分解整数。,问题分析 可以利用程序设计语言提供的整除和求余运算实现将整数分解的目的。 例如，对于整数7326，用7326/1000就得到了最高位7，而7326%1000得到了其余的位数326。但是，这种方法要求首先获得整数最高位的权，因此，算法应该先求整数最高位的权，然后从高向低逐个分离出每位数字。,算法描述,#include int main( ) long x, y, n; printf( “Enter an integer: ” ); scanf( “%ld”, ,求数列、8 的前项,#include void 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“); ,参考程序:,标志变量法的基本思想：,为了表示处理对象所处的状态（结果），使用一个变量，给其规定若干个值，并且规定每个值所表示的状态（意义），然后通过判断变量的值来知道程序处理的结果,例6：使用标志变量法判断9是否是素数,flag:0,2 , 3 , 4 , 5 , 6 , 7 , 8,9能否被2 整除,9能否被3 整除,给flag赋1：改变标志变量的值,flag:1,使用标志变量法判断11是否是素数,flag:0,2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10,11能否被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”, ,从键盘输入10个数，判断这10个数里有没有负数,#include int main( ) int x,j=0; printf( “Enter 10 integer :n“); do j+; scanf(“%d“, ,1、一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=123.编程找出1000以内的所有完数。 2、猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。,#include int main( ) int i,j,sum=0; for(i=2;i1000;i+) for(j=1;ji;j+) if ( i%j=0 ) sum+=j; if(sum=i) printf(