[精选]C语言复习PPT IE06-常用算法程序kmp.pptx

《[精选]C语言复习PPT IE06-常用算法程序kmp.pptx》由会员分享，可在线阅读，更多相关《[精选]C语言复习PPT IE06-常用算法程序kmp.pptx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课件封面实验教学标题输入、输出和选择结构程序6 常用算法程序常用算法程序【18】编写程序求两个整数的最大公约数和最小公倍数。#include void main()int m,n,t;printf(输入两个数（用空格或者回车间隔）n);scanf(%d%d,&m,&n);/设t 为m,n 的最小数if(mn)t=n;else t=m;while(t0)if(m%t=0&n%t=0)break;/每次检查m 和n 能否整除t 如果是则找到最大公约数t-;printf(%d 和%d 的最大公约数为%dn,m,n,t);/设t 为m,n 的最大数if(mn)t=m;else t=n;while(1)

2、if(t%m=0&t%n=0)break;/每次检查t 能否整除m 和n 如果是则找到最小公倍数t+;printf(%d 和%d 的最小公倍数为%dn,m,n,t);6 常用算法程序常用算法程序【19】编写一个函数IsP(int n)，函数的功能是检查n是否为素数，如果是函数返回“真”，否则返回“假”。在主函数中调用该函数，打印1001000之间的全部素数。#include int IsP(int n)/函数的功能是检查n 是否为素数 int i;/分析：从2到n-1 逐一检查能否整除n，只要有一个整除则肯定不是素数，所有均不能整除则肯定是素数for(i=2;in;i+)if(n%i=0)re

3、turn 0;/只要有一个整除则不是素数return 1;void main()int i;/打印1001000之间的全部素数for(i=100;i1000;i+)if(IsP(i)printf(%dn,i);6 常用算法程序常用算法程序【20】用筛选法求100之内的素数。#include void cal_prime(int A,int n)/使用筛选法计算素数int i,j;for(i=2;i=n;i+)for(j=2;i*j=n;j+)/如果该数尚未筛选过,则标记该数选中 if(Ai*j=1)Ai*j=0;else/如果已经筛选过,则跳出改次筛选,进入下次筛选 continue;void main()int A100+1;/下标需要从2到100，因此数组长度为100+1int i;/将全部数组元素设为1表示未被筛出for(i=2;i=100;i+)Ai=1;cal_prime(A,100);for(i=2;i=100;i+)if(Ai=1)/未被筛出的元素必定是素数 printf(%dn,i);6 常用算法程序常用算法程序【21】用二分查找法在已排序好的数组中查找输入的数。如果找到了输出该数的下标，否则输出“未找到”。（数组为：1,2,13,24,25,44,57,63,66,78,90,100）。