標題: 經典算法九例 [打印本頁]
作者: heicad 時間: 2014-10-21 22:14
標題: 經典算法九例
一．冒泡法：
排序過程：
（1）比較第一個數與第二個數，若為逆序a[0]>a[1]，則交換；然
后比較第二個數與第三個數；依次類推，直至第n-1個數和第
n個數比較為止——第一趟冒泡排序，結果最大的數被安置在
最后一個元素位置上
（2）對前n-1個數進行第二趟冒泡排序，結果使次大的數被安置在
第n-1個元素位置
（3）重復上述過程，共經過n-1趟冒泡排序后，排序結束。
例題:#include <stdio.h>
main()
{ int a[11],i,j,t;
printf("Input 10 numbers:\n");
for(i=1;i<11;i++)
scanf("%d",&a);
printf("\n");
for(j=1;j<=9;j++)
for(i=1;i<=10-j;i++)
if(a>a[i+1])
{t=a; a=a[i+1]; a[i+1]=t;}
printf("The sorted numbers:\n");
for(i=1;i<11;i++)
printf("%d ",a);
}
二．選擇法：
排序過程：
（1）首先通過n-1次比較，從n個數中找出最小的， 將它與第一個數
交換—第一趟選擇排序，結果最小的數被安置在第一個元素位置上
（2）再通過n-2次比較，從剩余的n-1個數中找出關鍵字次小的記錄，
將它與第二個數交換—第二趟選擇排序
（3）重復上述過程，共經過n-1趟排序后，排序結束。
例題：傳統方法：#include <stdio.h>
main()
{ int a[11],i,j,k,x;
printf("Input 10 numbers:\n");
for(i=1;i<=10;i++)
scanf("%d",&a);
printf("\n");
for(i=1;i<=10;i++)
{ k=i;
for(j=i+1;j<=10;j++)
if(a[j]<a[k]) k=j;
if(i!=k)
{ x=a; a=a[k]; a[k]=x;}
}
printf("The sorted numbers:\n");
for(i=1;i<=10;i++)
printf("%d ",a);
}
函數法：void sort(int array[],int n)
{ int i,j,k,t;
for(i=0;i<n-1;i++)
{ k=i;
for(j=i+1;j<n;j++)
if(array[j]<array[k]) k=j;
if(k!=i)
{ t=array;
array=array[k];
array[k]=t;
}
}}
main()
{ int a[10],i;
for(i=0;i<10;i++)
scanf("%d",&a);
sort(a,10);/*數組名作函數參數*/
for(i=0;i<10;i++)
printf("%d ",a);
printf("\n");}
三．楊輝三角：（二維數組）
例題：楊輝三角要求打十行：
#include<stdio.h>
#include<time.h>
void main()
{
double start, finish, cost;
int line[100] = {0 };
int i, r, size;
printf( "Please input the SIZE: " );
scanf( "%d", &size );
start = (double)clock()/CLOCKS_PER_SEC;
for( r=0; r<size; r++ )
printf( " " );
line[0] = 1;
printf( " %d\n", line[0] );
for( i=1; i<size; i++ )
{
for( r=i; r>=1; r-- )
line[r] += line[r-1];
for( r=0; r<size-i; r++ )
printf( " " );
for( r=0; r<=i; r++ )
printf( " %d ", line[r] );
printf( "\n" );
finish = (double)clock()/CLOCKS_PER_SEC;
cost = finish - start;
printf( "\nCOST: %.6f s\n", cost );
}
}
四.字符數組：（逆序排列）如：<ABCDE-EDCBA>
例題：把輸入的字符串逆序排列，如輸入ABCDE，輸出為EDCBA
#include<string.h>
main()
{ char c,str[80];
int i,j;
printf("Enter a string:\n");
scanf(“%s”,str); /* 也可以gets(str);puts(str); */
for(i=0,j=strlen(str)-1;i<j;i++,j--)
{
c=str;
str=str[j];
str[j]=c;
}
printf("\nReversed string:\n%s\n",str);
}
五：水仙花數：
例題：打印出所有的水仙花數：
main()
{ int i,j,k,n;
printf(“水仙花數是：”);
for(n=100;n<1000;n++)
{ i=n/100;
j=n/10-i*10;
k=n%10;
if(n==i*i*i+j*j*j+k*k*k) printf(“%4d”,n);
}
printf(“\n”); }
六．素數：
素數是指除了1和它本身外沒有其他因子的大于1的整數。數學上已經證明，要判斷整數m是不是素數，只需判斷m是否能被2、3、4…… 中的某一個數整除即可。在程序中如i>=k+1為真，則說明不存在2～ 之間的因子，所以此整數是素數。
例題：求100—200之間的全部素數之和
#include<math.h>
main( )
{int sum(int m);
int m,s=0;
for(m=101;m<=200;m=m+2)
s=s+sum(m);
printf(“s=%d\n”,s);
}
七．遞歸調用：（求階乘）
例題1：求n的階乘：
#include <stdio.h>
float fac(int n)
{ float f;
if(n<0) printf("n<0,data error!");
else if(n==0||n==1) f=1;
else f=fac(n-1)*n;
return(f);
}
main()
{ int n, i；float y=0;
printf("Input a integer number:");
scanf("%d",&n);
y=fac(n);
printf("%d! =%f",n,y);
}
例題2： 求1!+2!+……n！
#include <stdio.h>
float fac(int n)
{ float f;
if(n<0) printf("n<0,data error!");
else if(n==0||n==1) f=1;
else f=fac(n-1)*n;
return(f);
}
main()
{ int n, i；float y=0;
printf("Input a integer number:");
scanf("%d",&n);
for(i=0;i<=n;i++)
y=y+fac(i);
printf("%d! =%f",n,y);
}
八：求二維數組各行元素之和：
例題：1.運用傳統方法：
#include <stdio.h>
main()
{ int x[5][4],i,j;
for(i=0;i<=3;i++)
for(j=0;j<=2;j++)
scanf("%d",&x[j]);
for(i=0;i<=2;i++)
x[4]=0;
for(j=0;j<=4;j++)
x[j][3]=0;
for(i=0;i<=3;i++)
for(j=0;j<=2;j++)
{ x[3]+=x[j];
x[4][j]+=x[j];
x[4][3]+=x[j];
}
2.運用函數法：
void get_sum_row(int x[][3], int result[] ,int row, int col)
{ int i,j;
for(i=0;i<row;i++)
{ result=0;
for(j=0;j<col;j++)
result+=x[j];
}}
main()
{ int a[2][3]={3,6,9,1,4,7};
int sum_row[2],row=2,col=3,i;
get_sum_row(a,sum_row,row,col);/*數組名a作函數參數*/
for(i=0;i<row;i++)
printf("The sum of row[%d]=%d\n",i+1,sum_row);
}
九．Fibonacci數列：
例題：用數組求Fibonacci數列前20個數
#include <stdio.h>
main()
{ int i;
int f[20]={1,1};
for(i=2;i<20;i++)
f=f[i-2]+f[i-1];
for(i=0;i<20;i++)
{ if(i%5==0)
printf("\n");
printf("%12d",f);
}
}
作者: aaaaabbbbb 時間: 2014-12-16 19:30
不錯不錯
| 歡迎光臨 (http://www.raoushi.com/bbs/) |
Powered by Discuz! X3.1 |