C語言教學之常用算法程序

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,章節(jié)目錄,課件封面,實驗教,學,學標題,輸入、,輸,輸出和,選,選擇結(jié),構(gòu),構(gòu)程序,6,常用算,法,法程序,常用算,法,法程序,【,18,】編,寫,寫程序,求,求兩個,整,整數(shù)的,最,最大公,約,約數(shù)和,最,最小公,倍,倍數(shù)。,#include,void main(),intm,n,t;,printf(,輸入兩,個,個數(shù)（,用,用空格,或,或者回,車,車間隔,）,）,n);,scanf(%d%d,/,設(shè),t,為,m,n,的最小,數(shù),數(shù),if(mn)t=n;,elset=m;,while(t0),if(m%t=0,/,每次檢,查,查,m,和,n,能否整,除,除,t,如果是,則,則找到,最,最大公,約,約數(shù),t-;,printf(%d,和,%d,的最大,公,公約數(shù),為,為,%dn,m,n,t);,/,設(shè),t,為,m,n,的最大,數(shù),數(shù),if(mn)t=m;elset=n;,while(1),if(t%m=0,/,每次檢,查,查,t,能否整,除,除,m,和,n,如果是,則,則找到,最,最小公,倍,倍數(shù),t+;,printf(%d,和,%d,的最小,公,公倍數(shù),為,為,%dn,m,n,t);,6,常用算,法,法程序,常用算,法,法程序,【,19,】編,寫,寫一個,函,函數(shù),IsP(int n),，,函數(shù)的,功,功能是,檢,檢查,n,是否為,素,素數(shù)，,如,如果是,函,函數(shù)返,回,回“真,”,”，否,則,則返回,“,“假”,。,。在主,函,函數(shù)中,調(diào),調(diào)用該,函,函數(shù)，,打,打印,100,1000,之間的,全,全部素,數(shù),數(shù)。,#include,int IsP(int n)/,函數(shù)的功能,是,是檢查,n,是否為素數(shù),inti;,/,分析：從,2,到,n-1,逐一檢查能,否,否整除,n,，只要有,一,一個整除,則,則肯定不,是,是素數(shù)，,所,所有均不,能,能整除則,肯,肯定是素,數(shù),數(shù),for(i=2;in;i+),if(n%i=0)return 0;,/,只要有一,個,個整除則,不,不是素數(shù),return 1;,voidmain(),int i;,/,打印,100,1000,之間的全,部,部素數(shù),for(i=100;i1000;i+),if(IsP(i),printf(%dn,i);,6,常用算法,程,程序,常用算法,程,程序,【,20,】用篩選法,求,求,100,之內(nèi)的素數(shù)。,#include,void cal_prime(intA,int n)/,使用篩選法計,算,算素數(shù),int i,j;,for(i=2;i=n;i+),for(j=2;i*j=n;j+),/,如果該數(shù)尚未,篩,篩選過,則標記該數(shù)選,中,中,if(Ai*j=1)Ai*j=0;,else/,如果已經(jīng)篩選,過,過,則跳出改次篩,選,選,進入下次篩選,continue;,void main(),intA100+1;/,下標需要從,2,到,100,，因此數(shù)組長,度,度為,100+1,int i;,/,將全部數(shù)組元,素,素設(shè)為,1,表示未被篩出,for(i=2;i=100;i+)Ai=1;,cal_prime(A,100);,for(i=2;i=100;i+),if(Ai=1)/,未被篩出的元,素,素必定是素數(shù),printf(%dn,i);,6,常用算法程序,常用算法程序,【,21,】用二分查,找,找法在已排序,好,好的數(shù)組中查,找,找輸入的數(shù)。,如,如果找到了輸,出,出該數(shù)的下標,，,，否則輸出“,未,未找到”。（,數(shù),數(shù)組為：,1,2,13,24,25,44,57,63,66,78,90,100,）。,#include,#include,void main(),inta10=1,3,5,7,9,11,13,15,17,19;,int h;/,查找區(qū)域開始,位,位置,int t;/,查找區(qū)域結(jié)束,位,位置,int m;/,查找區(qū)域中間,位,位置,int sign=0;/,為,0,表示未找到，,為,為表示找到,int f;/,要查找的數(shù)據(jù),printf(,請輸入要查找,的,的數(shù)據(jù)：,);,scanf(%d,h=0,t=9;/,一開始將整個,數(shù),數(shù)組設(shè)為查找,區(qū),區(qū)域,if(!(fa9),/,如果要查找的,數(shù),數(shù)據(jù)比開始元,素,素小或者比結(jié),束,束元素大，則,肯,肯定不在查找,區(qū),區(qū)域中,while(!sign&ham)/,否則如果要找,的,的數(shù)據(jù)比中間,位,位置的數(shù)據(jù)大,h=m+1;/,則下一次的查,找,找區(qū)域在右半,部,部分,else,t=m-1;/,否則下一次的,查,查找區(qū)域在左,半,半部分,if(sign=0),printf(,在數(shù)組中,%d,沒有找到,n,f);,6,常用算法程序,常用算法程序,【,22,】編寫一個,函,函數(shù),sort(int A,int n),，,函數(shù)的功能是,用,用冒泡法對數(shù),組,組進行由大到,小,小的排序，其,中,中,n,為數(shù)組,A,的元素個數(shù)。,在,在主函數(shù)中輸,入,入,10,個數(shù)據(jù)，調(diào)用,函,函數(shù)排序，然,后,后輸出排序好,的,的,10,個數(shù)據(jù)。（輸,入,入數(shù)據(jù)：,6,8,9,1,2,5,4,7,3,18,）,#include,void sort(int A,int n),inti,j;intt;,/,改進后的冒泡,法,法排序,for(i=0;in-1;i+),for(j=i+1;jn;j+),if(AiAj),/,為由,小,小到,大,大，,Ai,表示,前,前面,的,的數(shù),Aj,表示,后,后面,的,的數(shù),t=Ai,Ai=Aj,Aj=t;,voidmain(),intA10;inti;,printf(,連續(xù),輸,輸入,10,個數(shù),據(jù),據(jù)（,用,用空,格,格或,者,者,TAB,或者,回,回車,間,間隔,）,）,n);,for(i=0;i10;i+),scanf(%d,sort(A,10);,/,輸出,排,排序,后,后的,數(shù),數(shù)組,for(i=0;i10;i+),printf(%d,Ai);,6,常用,算,算法,程,程序,常用,算,算法,程,程序,【,23,】,編,編寫,一,一個,函,函數(shù),sort(intA,intn),，,函數(shù),的,的功,能,能是,用,用選,擇,擇法,對,對數(shù),組,組進,行,行由,小,小到,大,大的,排,排序,，,，其,中,中,n,為數(shù),組,組,A,的元,素,素個,數(shù),數(shù)。,在,在主,函,函數(shù),中,中輸,入,入,10,個數(shù),據(jù),據(jù)，,調(diào),調(diào)用,函,函數(shù),排,排序,，,，然,后,后輸,出,出排,序,序好,的,的,10,個數(shù),據(jù),據(jù)。,（,（輸,入,入數(shù),據(jù),據(jù)：,6,8,9,1,2,5,4,7,3,18,）,#include,voidsort(intA,intn),inti,j,k;intt;,/,改進,后,后的,選,選擇,法,法排,序,序,for(i=0;in-1;i+),k=i;,for(j=i+1;jAj)k=j;,/,為,由,由,小,小,到,到,大,大,，,，,Ak,表,示,示,前,前,面,面,的,的,數(shù),數(shù),Aj,表,示,示,后,后,面,面,的,的,數(shù),數(shù),if(k!=i)t=Ai,Ai=Ak,Ak=t;,voidmain(),intA10;inti;,printf(,連,續(xù),續(xù),輸,輸,入,入,10,個,數(shù),數(shù),據(jù),據(jù),（,（,用,用,空,空,格,格,或,或,者,者,TAB,或,者,者,回,回,車,車,間,間,隔,隔,）,）,n);,for(i=0;i10;i+)scanf(%d,sort(A,10);,/,輸出排,序,序后的,數(shù),數(shù)組,for(i=0;i10;i+)printf(%d,Ai);,演講,完,完畢,，,，謝,謝,謝觀,看,看！,