第六讲循环结构典型算法.pps

第六讲循环结构典型算法主讲教师:马学文 2017 年3月 29 日内容提要 循环程序设计要点 输出 500 以的所有素数 求最小公倍数,最大公约数 输出斐波那契数列前 n项 45 人搬 45 块砖问题 求方程的近似实根 求一元函数定积分的近似值 循环程序设计要点?循环程序的实现要点: ?归纳出哪些操作需要反复执行? 循环体?这些操作在什么情况下重复执行?循环条件?选用合适的循环语句 for while do-while ?循环具体实现时考虑(循环条件): ?事先给定循环次数,首选 for ?通过其他条件控制循环,考虑 while 或 do- while 输出 500 以的所有素数[例 4- 10] 求 500 以内的全部素数,每行输出 10 个 for (m = 2; m <= 500; m++) if ( m是素数) printf ( "%d", m); n = sqrt(m ); for(i = 2; i <= n; i++) if(m % i == 0) break; if(i > n) printf("yes\n ") else printf("no\n ”); for (m = 2; m <= 500; m++){ n= sqrt(m ); for(i = 2; i <= n; i++) if(m % i == 0) break; if(i > n) printf("%d ", m); } 例 4- 10 源程序# include < > #include < > int main(void ) { int count, i, m, n; count = 0; for (m = 2; m <= 500; m++) { n = sqrt(m ); for (i = 2; i <= n; i++) if(m % i == 0) break; if(i > n) / *如果 m是素数*/ { printf("%6d", m); count++; if (count %10 == 0) printf( “\n”); } } } 求最小公倍数,最大公约数最小公倍数,是指能够被两个整数同时整除的最小整数。最大公约数,是指能够整除这两个数的最大整数。可采用穷举法: 求m与n的最小公倍数: for(i = n; ; i++) if(m%i ==0 && n%i ==0) break; printf (“最小公倍数是: %i”,i ); 求m与n的最大公约数: for( i=n; ; i-- ) if(i%m ==0 && i%n ==0) break; printf (“最大公约数是: %i”,i ); [补充例题 1] 求两个整数 m和n的最小公倍数,最大公约数展转相除法: 先用 m除以 n求得余数 r, 当r≠0时,再用除数做被除数、余数做除数再求余数, 如此反复,直至 r=0,除数即为所求的最大公约数。 p(=m * n) 除以最大公约数即为 m和n的最小公倍数 R 0 =m, R 1 =n , R 2 , R 3 , ……, R n =R n-2 /R n-1 , .. …. while(1) { r=m % n; if(r !=0) { m=n; n=r; } else break; }/*这时 n中即为最大公约数*/ while(n !=0) { r= m % n; m =n; n=r; } /*这时 m中即为最大公约数*/ [ [补充例题补充例题 1] 1]源程序源程序/*求 m,n 的最大公约数与最小公倍数*/ #include< > main() { int p, r, n, m; printf (" 请输入两个正整数:\n"); scanf ("% d,%d",&n,&m ); p=n * m; while(n !=0) { r= m%n ; m=n; n=r; } //最大公约数在 m中 printf ("最大公约数是% d\n 最小公倍数是% d\n ", m, p/m ); } 输出斐波那契数列前 n