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

課件封面課件封面實驗教學標題輸入、輸出和選擇結構程序實驗教學標題輸入、輸出和選擇結構程序6常用算法程序常用算法程序【18．】編寫程序求兩個整數的最大公約數和最小公倍數。

6常用算法程序常用算法程序【18．】編寫程序求兩個整數的最#include<stdio.h>voidmain(){ intm,n,t; printf("輸入兩個數（用空格或者回車間隔）\n"); scanf("%d%d",&m,&n);

//設t為m,n的最小數

if(m>n)t=n; elset=m; while(t>0){ if(m%t==0&&n%t==0)break;

//每次檢查m和n能否整除t如果是則找到最大公約數

t--; } printf("%d和%d的最大公約數為%d\n",m,n,t);

//設t為m,n的最大數

if(m>n)t=m; elset=n; while(1){ if(t%m==0&&t%n==0)break;

//每次檢查t能否整除m和n如果是則找到最小公倍數

t++; } printf("%d和%d的最小公倍數為%d\n",m,n,t);}#include<stdio.h>6常用算法程序常用算法程序【19．】編寫一個函數IsP(intn)，函數的功能是檢查n是否為素數，如果是函數返回“真”，否則返回“假”。在主函數中調用該函數，打印100～1000之間的全部素數。

6常用算法程序常用算法程序【19．】編寫一個函數IsP(i#include<stdio.h>intIsP(intn)//函數的功能是檢查n是否為素數{ inti; //分析：從2到n-1逐一檢查能否整除n，只要有一個整除則肯定不是素數，所有均不能整除則肯定是素數

for(i=2;i<n;i++) if(n%i==0)return0;

//只要有一個整除則不是素數

return1;}voidmain(){ inti;

//打印100～1000之間的全部素數

for(i=100;i<1000;i++) if(IsP(i)) printf("%d\n",i);}#include<stdio.h>6常用算法程序常用算法程序【20．】用篩選法求100之內的素數。

6常用算法程序常用算法程序【20．】用篩選法求100之內的#include<stdio.h>voidcal_prime(intA[],intn)//使用篩選法計算素數{inti,j;for(i=2;i<=n;i++)for(j=2;i*j<=n;j++){//如果該數尚未篩選過,則標記該數選中

if(A[i*j]==1)A[i*j]=0;else//如果已經篩選過,則跳出改次篩選,進入下次篩選

continue;}}voidmain(){ intA[100+1];//下標需要從2到100，因此數組長度為100+1 inti;

//將全部數組元素設為1表示未被篩出

for(i=2;i<=100;i++) A[i]=1; cal_prime(A,100); for(i=2;i<=100;i++) if(A[i]==1)//未被篩出的元素必定是素數

printf("%d\n",i);}#include<stdio.h>6常用算法程序常用算法程序【21．】用二分查找法在已排序好的數組中查找輸入的數。如果找到了輸出該數的下標，否則輸出“未找到”。（數組為：1,2,13,24,25,44,57,63,66,78,90,100）。

6常用算法程序常用算法程序【21．】用二分查找法在已排序好#include<stdio.h>#include<math.h>voidmain(){ inta[10]={1,3,5,7,9,11,13,15,17,19}; inth; //查找區(qū)域開始位置

intt; //查找區(qū)域結束位置

intm; //查找區(qū)域中間位置

intsign=0; //為0表示未找到，為表示找到

intf; //要查找的數據

printf("請輸入要查找的數據："); scanf("%d",&f); h=0,t=9; //一開始將整個數組設為查找區(qū)域

if(!(f<a[0]||f>a[9])) {

//如果要查找的數據比開始元素小或者比結束元素大，則肯定不在查找區(qū)域中

#include<stdio.h>while(!sign&&h<=t) {m=(h+t)/2; //計算當前查找區(qū)域的中間位置

if(f==a[m])

//如果要找的數據與中間位置的數據相等表示找到了

{printf("%d找到了，它是：A[%d]\n",f,m); sign=1; } elseif(f>a[m])//否則如果要找的數據比中間位置的數據大

h=m+1;//則下一次的查找區(qū)域在右半部分

else t=m-1;//否則下一次的查找區(qū)域在左半部分

} } if(sign==0) printf("在數組中%d沒有找到\n",f);}while(!sign&&h<=t)6常用算法程序常用算法程序【22．】編寫一個函數sort(intA[],intn)，函數的功能是用冒泡法對數組進行由大到小的排序，其中n為數組A的元素個數。在主函數中輸入10個數據，調用函數排序，然后輸出排序好的10個數據。（輸入數據：6,8,9,1,2,5,4,7,3,18）

6常用算法程序常用算法程序【22．】編寫一個函數sort(#include<stdio.h>voidsort(intA[],intn){ inti,j; intt;

//改進后的冒泡法排序

for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(A[i]<A[j])

//<為由大到小，>為由小到大，A[i]表示前面的數,A[j]表示后面的數

{t=A[i],A[i]=A[j],A[j]=t;}}voidmain(){ intA[10]; inti; printf("連續(xù)輸入10個數據（用空格或者TAB或者回車間隔）\n"); for(i=0;i<10;i++) scanf("%d",&A[i]); sort(A,10);

//輸出排序后的數組

for(i=0;i<10;i++) printf("%d",A[i]);}#include<stdio.h>6常用算法程序常用算法程序【23．】編寫一個函數sort(intA[],intn)，函數的功能是用選擇法對數組進行由小到大的排序，其中n為數組A的元素個數。在主函數中輸入10個數據，調用函數排序，然后輸出排序好的10個數據。（輸入數據：6,8,9,1,2,5,4,7,3,18）

6常用算法程序常用算法程序【23．】編寫一個函數sort(#include<stdio.h>voidsort(intA[],intn){ inti,j,k; intt;

//改進后的選擇法排序

for(i=0;i<n-1;i++){ k=i; for(j=i+1;j<n;j++) if(A[k]>A[j])k=j;

//<為由大到小，>為由小到大，A[k]表示前面的數,A[j]表示后面的數

if(k!=i) {t=A[i],A[i]=A[k],A[k]=t;} }}voidmain(){ intA[10]; inti; printf("連續(xù)輸入10個數據（用空格或者TAB或者回車間隔）\n"); for(i=0;i<10;i++)scanf("%d",&A[i]);

sort(A,10);

//輸出排序后的數組

for(i=0;i<10;i++)printf("%d",A[i]);}#include<stdio.h>演講完畢，謝謝觀看！演講完畢，謝謝觀看！課件封面課件封面實驗教學標題輸入、輸出和選擇結構程序實驗教學標題輸入、輸出和選擇結構程序6常用算法程序常用算法程序【18．】編寫程序求兩個整數的最大公約數和最小公倍數。

6常用算法程序常用算法程序【18．】編寫程序求兩個整數的最#include<stdio.h>voidmain(){ intm,n,t; printf("輸入兩個數（用空格或者回車間隔）\n"); scanf("%d%d",&m,&n);

//設t為m,n的最小數

if(m>n)t=n; elset=m; while(t>0){ if(m%t==0&&n%t==0)break;

//每次檢查m和n能否整除t如果是則找到最大公約數

t--; } printf("%d和%d的最大公約數為%d\n",m,n,t);

//設t為m,n的最大數

if(m>n)t=m; elset=n; while(1){ if(t%m==0&&t%n==0)break;

//每次檢查t能否整除m和n如果是則找到最小公倍數

t++; } printf("%d和%d的最小公倍數為%d\n",m,n,t);}#include<stdio.h>6常用算法程序常用算法程序【19．】編寫一個函數IsP(intn)，函數的功能是檢查n是否為素數，如果是函數返回“真”，否則返回“假”。在主函數中調用該函數，打印100～1000之間的全部素數。

6常用算法程序常用算法程序【19．】編寫一個函數IsP(i#include<stdio.h>intIsP(intn)//函數的功能是檢查n是否為素數{ inti; //分析：從2到n-1逐一檢查能否整除n，只要有一個整除則肯定不是素數，所有均不能整除則肯定是素數

for(i=2;i<n;i++) if(n%i==0)return0;

//只要有一個整除則不是素數

return1;}voidmain(){ inti;

//打印100～1000之間的全部素數

for(i=100;i<1000;i++) if(IsP(i)) printf("%d\n",i);}#include<stdio.h>6常用算法程序常用算法程序【20．】用篩選法求100之內的素數。

6常用算法程序常用算法程序【20．】用篩選法求100之內的#include<stdio.h>voidcal_prime(intA[],intn)//使用篩選法計算素數{inti,j;for(i=2;i<=n;i++)for(j=2;i*j<=n;j++){//如果該數尚未篩選過,則標記該數選中

if(A[i*j]==1)A[i*j]=0;else//如果已經篩選過,則跳出改次篩選,進入下次篩選

continue;}}voidmain(){ intA[100+1];//下標需要從2到100，因此數組長度為100+1 inti;

//將全部數組元素設為1表示未被篩出

for(i=2;i<=100;i++) A[i]=1; cal_prime(A,100); for(i=2;i<=100;i++) if(A[i]==1)//未被篩出的元素必定是素數

printf("%d\n",i);}#include<stdio.h>6常用算法程序常用算法程序【21．】用二分查找法在已排序好的數組中查找輸入的數。如果找到了輸出該數的下標，否則輸出“未找到”。（數組為：1,2,13,24,25,44,57,63,66,78,90,100）。

6常用算法程序常用算法程序【21．】用二分查找法在已排序好#include<stdio.h>#include<math.h>voidmain(){ inta[10]={1,3,5,7,9,11,13,15,17,19}; inth; //查找區(qū)域開始位置

intt; //查找區(qū)域結束位置

intm; //查找區(qū)域中間位置

intsign=0; //為0表示未找到，為表示找到

intf; //要查找的數據

printf("請輸入要查找的數據："); scanf("%d",&f); h=0,t=9; //一開始將整個數組設為查找區(qū)域

if(!(f<a[0]||f>a[9])) {

//如果要查找的數據比開始元素小或者比結束元素大，則肯定不在查找區(qū)域中

#include<stdio.h>while(!sign&&h<=t) {m=(h+t)/2; //計算當前查找區(qū)域的中間位置

if(f==a[m])

//如果要找的數據與中間位置的數據相等表示找到了

{printf("%d找到了，它是：A[%d]\n",f,m); sign=1; } elseif(f>a[m])//否則如果要找的數據比中間位置的數據大

h=m+1;//則下一次的查找區(qū)域在右半部分

else t=m-1;//否則下一次的查找區(qū)域在左半部分

} } if(sign==0) printf("在數組中%d沒有找到\n",f);}while(!sign&&h<=t)6常用算法程序常用算法程序【22．】編寫一個函數sort(intA[],intn)，函數的功能是用冒泡法對數組進行由大到小的排序，其中n為數組A的元素個數。在主函數中輸入10個數據，調用函數排序，然后輸出排序好的10個數據。（輸入數據：6,8,9,1,2,5,4,7,3,18）

6常用算法程序常用算法程序【22．】編寫一個函數sort(#include<stdio.h>voidsort(intA[],intn){ inti,j; intt;

//改進后的冒泡法排序

for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(A[i]<A[j])

//<為由大到小，>為由小到大，A[i]表示前面的數,A[j]表示后面的數

{t=A[i],A[i]=A[j],A[j]=t;}}voidmain(){ intA[10]; inti; printf("連續(xù)輸入10個數據（用空格或者TAB或者回車間隔）\n"); for(i=0;i<10;i++) sca