[轉]C程序設計的常用算法

　　算法（Algorithm）：計算機解題的基本思想方法和步驟。算法的描述：是對要解決一個問題或要
完成一項任務所采取的方法和步驟的描述，包括需要什么數據（輸入什么數據、輸出什么結果）、采
用什么結構、使用什么語句以及如何安排這些語句等。通常使用自然語言、結構化流程圖、偽代碼等來描述算法。

　　一、計數、求和、求階乘等簡單算法

　　此類問題都要使用循環，要注意根據問題確定循環變量的初值、終值或結束條件，更要注意用來
表示計數、和、階乘的變量的初值。

　　例：用隨機函數產生100個[0，99]范圍內的隨機整數，統計個位上的數字分別為1，2，3，4，5，
6，7，8，9，0的數的個數并打印出來。

　　本題使用數組來處理，用數組a[100]存放產生的確100個隨機整數，數組x[10]來存放個位上的數字
分別為1，2，3，4，5，6，7，8，9，0的數的個數。即個位是1的個數存放在x[1]中，個位是2的個數存
放在x[2]中，……個位是0的個數存放在x[10]。

void main()
{
??? int a[101],x[11],i,p;

??? for(i=0;i<=11;i++)
??????? x[i]=0;
??? for(i=1;i<=100;i++)
??? {
??????? a[i]=rand() % 100;
??????? printf("%4d",a[i]);
??????? if(i%10==0)printf("\n");
??? }

??? for(i=1;i<=100;i++)
??? {
??????? p=a[i]%10;
??????? if(p==0) p=10;
??????????? x[p]=x[p]+1;
??? }

??? for(i=1;i<=10;i++)
??? {
??????? p=i;
??????? if(i==10) p=0;
??????????? printf("%d,%d\n",p,x[i]);
??? }

??? printf("\n");
}

　　二、求兩個整數的最大公約數、最小公倍數

　　分析：求最大公約數的算法思想：(最小公倍數=兩個整數之積/最大公約數)
(1) 對于已知兩數m，n，使得m>n；
(2) m除以n得余數r；
(3) 若r=0，則n為求得的最大公約數，算法結束；否則執行(4)；
(4) m←n，n←r，再重復執行(2)。
例如: 求 m=14 ,n=6 的最大公約數. m n r
14 6 2
6 2 0

void main()
{
??? int nm,r,n,m,t;
??? printf("please input two numbers:\n");
??? scanf("%d,%d",&m,&n);
??? nm=n*m;

??? if (m<n)
??? {
??????? t=n; n=m; m=t; }
??????? r=m%n;

??? while (r!=0)
??? {
??????? m=n; n=r; r=m%n;
??? }

??? printf("最大公約數:%d\n",n);
??? printf("最小公倍數:%d\n",nm/n);
}

　　三、判斷素數

　　只能被1或本身整除的數稱為素數 基本思想：把m作為被除數，將2—INT（ ）作為除數，如果都
除不盡，m就是素數，否則就不是。（可用以下程序段實現）

void main()
{
??? int m,i,k;
??? printf("please input a number:\n");
??? scanf("%d",&m);
??? k=sqrt(m);

??? for(i=2;i<k;i++)
??????? if(m%i==0)
??????????? break;

??? if(i>=k)
??????? printf("該數是素數");
??? else
??????? printf("該數不是素數");
}

將其寫成一函數,若為素數返回1，不是則返回0
int prime( m%)
{
??? int i,k;
??? k=sqrt(m);

??? for(i=2;i<k;i++)
??????? if(m%i==0)
??????????? return 0;

??? return 1;
}

　　四、驗證哥德巴赫猜想

　　（任意一個大于等于6的偶數都可以分解為兩個素數之和）
基本思想：n為大于等于6的任一偶數，可分解為n1和n2兩個數，分別檢查n1和n2是否為素數，如都是，
則為一組解。如n1不是素數，就不必再檢查n2是否素數。先從n1=3開始，檢驗n1和n2（n2=N-n1）是否
素數。然后使n1+2 再檢驗n1、n2是否素數，… 直到n1=n/2為止。

　　利用上面的prime函數，驗證哥德巴赫猜想的程序代碼如下：
#include "math.h"
int prime(int m)
{ int i,k;
k=sqrt(m);
for(i=2;i<k;i++)
if(m%i==0) break;
if(i>=k)
return 1;
else
return 0;
}

main()
{ int x,i;
printf("please input a even number(>=6):\n");
scanf("%d",&x);
if (x<6||x%2!=0)
printf("data error!\n");
else
for(i=2;i<=x/2;i++)
if (prime(i)&&prime(x-i))
{
printf("%d+%d\n",i,x-i);
printf("驗證成功!");
break;
}
}

　　五、排序問題

　　1．選擇法排序（升序）

　　基本思想：
1）對有n個數的序列（存放在數組a(n)中），從中選出最小的數，與第1個數交換位置；
2）除第1 個數外，其余n-1個數中選最小的數，與第2個數交換位置；
3）依次類推，選擇了n-1次后，這個數列已按升序排列。

程序代碼如下：
void main()
{
??? int i,j,imin,s,a[10];
??? printf("\n input 10 numbers:\n");

??? for(i=0;i<10;i++)
??????? scanf("%d",&a[i]);
??? for(i=0;i<9;i++)
??? {
??????? imin=i;
??????? for(j=i+1;j<10;j++)
??????????? if(a[imin]>a[j])
??????????????? imin=j;

??????? if(i!=imin)
??????? {
??????????? s=a[i];
??????????? a[i]=a[imin];
??????????? a[imin]=s;
??????? }

??????? printf("%d\n",a[i]);
??? }
}

　　2．冒泡法排序（升序）

　　基本思想：(將相鄰兩個數比較，小的調到前頭)
1）有n個數（存放在數組a(n)中），第一趟將每相鄰兩個數比較，小的調到前頭，經n-1次兩兩相鄰比
??? 較后，最大的數已“沉底”，放在最后一個位置，小數上升“浮起”；
2）第二趟對余下的n-1個數（最大的數已“沉底”）按上法比較，經n-2次兩兩相鄰比較后得次大的數；
3）依次類推，n個數共進行n-1趟比較，在第j趟中要進行n-j次兩兩比較。
程序段如下
void main()
{
??? int a[10];
??? int i,j,t;
??? printf("input 10 numbers\n");

??? for(i=0;i<10;i++)
??????? scanf("%d",&a[i]);
??? printf("\n");

??? for(j=0;j<=8;j++)
??? for(i=0;i<9-j;i++)
??????? if(a[i]>a[i+1])
??????? {
??????????? t=a[i];
??????????? a[i]=a[i+1];
??????????? a[i+1]=t;
??????? }

??? printf("the sorted numbers:\n");
??? for(i=0;i<10;i++)
??????? printf("%d\n",a[i]);
}

　　3．合并法排序（將兩個有序數組A、B合并成另一個有序的數組C，升序）

　　基本思想：
1）先在A、B數組中各取第一個元素進行比較，將小的元素放入C數組；
2）取小的元素所在數組的下一個元素與另一數組中上次比較后較大的元素比較，重復上述比較過程，
??? 直到某個數組被先排完；
3）將另一個數組剩余元素抄入C數組，合并排序完成。
程序段如下：
void main()
{
??? int a[10],b[10],c[20],i,ia,ib,ic;
??? printf("please input the first array:\n");

??? for(i=0;i<10;i++)
??????? scanf("%d",&a[i]);
??? for(i=0;i<10;i++)
??????? scanf("%d",&b[i]);

??? printf("\n");
??? ia=0;ib=0;ic=0;

??? while(ia<10&&ib<10)
??? {
??????? if(a[ia]<b[ib])
??????? {
??????????? c[ic]=a[ia];
??????????? ia++;
??????? }
??????? else
??????? {
??????????? c[ic]=b[ib];
??????????? ib++;
??????? }
??????? ic++;
??? }

??? while(ia<=9)
??? {
??????? c[ic]=a[ia];
??????? ia++;
??????? ic++;
??? }

??? while(ib<=9)
??? {
??????? c[ic]=b[ib];
??????? b++;
??????? ic++;
??? }

??? for(i=0;i<20;i++)
??????? printf("%d\n",c[i]);
}

　　六、查找問題

　　1．①順序查找法（在一列數中查找某數x）

　　基本思想：一列數放在數組a[1]---a[n]中，待查找的數放在x 中，把x與a數組中的元素從頭到尾
??? 一一進行比較查找。用變量p表示a數組元素下標，p初值為1，使x與a[p]比較，如果x不等于a[p]，
??? 則使p=p+1，不斷重復這個過程；一旦x等于a[p]則退出循環；另外，如果p大于數組長度，循環也
??? 應該停止。（這個過程可由下語句實現）
void main()
{
??? int a[10],p,x,i;
??? printf("please input the array:\n");

??? for(i=0;i<10;i++)
??????? scanf("%d",&a[i]);

??? printf("please input the number you want find:\n");
??? scanf("%d",&x);
??? printf("\n");
??? p=0;

??? while(x!=a[p]&&p<10)
??????? p++;

??? if(p>=10)
??????? printf("the number is not found!\n");
??? else
??????? printf("the number is found the no%d!\n",p);
}

思考：將上面程序改寫一查找函數Find，若找到則返回下標值，找不到返回-1
②基本思想：一列數放在數組a[1]---a[n]中，待查找的關鍵值為key，把key與a數組中的元素從頭到尾
一一進行比較查找，若相同，查找成功，若找不到，則查找失敗。(查找子過程如下。index：存放
找到元素的下標。)
void main()
{
??? int a[10],index,x,i;
??? printf("please input the array:\n");

??? for(i=0;i<10;i++)
??????? scanf("%d",&a[i]);

??? printf("please input the number you want find:\n");
??? scanf("%d",&x);
??? printf("\n");

??? index=-1;
??? for(i=0;i<10;i++)
??????? if(x==a[i])
??????? {
??????????? index=i;
??????????? break;
??????? }

??? if(index==-1)
??????? printf("the number is not found!\n");
??? else
??????? printf("the number is found the no%d!\n",index);
}

　　2．折半查找法（只能對有序數列進行查找）

　　基本思想：設n個有序數（從小到大）存放在數組a[1]----a[n]中，要查找的數為x。用變量bot、
??? top、mid 分別表示查找數據范圍的底部（數組下界）、頂部（數組的上界）和中間，
??? mid=(top+bot)/2，折半查找的算法如下：
（1）x=a(mid)，則已找到退出循環，否則進行下面的判斷；
（2）x<a(mid)，x必定落在bot和mid-1的范圍之內，即top=mid-1；
（3）x>a(mid)，x必定落在mid+1和top的范圍之內，即bot=mid+1；
（4）在確定了新的查找范圍后，重復進行以上比較，直到找到或者bot<=top。
將上面的算法寫成如下程序：
void main()
{
??? int a[10],mid,bot,top,x,i,find;
??? printf("please input the array:\n");

??? for(i=0;i<10;i++)
??????? scanf("%d",&a[i]);

??? printf("please input the number you want find:\n");
??? scanf("%d",&x);
??? printf("\n");

??? bot=0;top=9;find=0;
??? while(bot<top&&find==0)
??? {
??????? mid=(top+bot)/2;
??????? if(x==a[mid])
??????? {
??????????? find=1;
??????????? break;
??????? }
??????? else if(x<a[mid])
??????????? top=mid-1;
??????? else
??????????? bot=mid+1;
??? }

??? if (find==1)
??????? printf("the number is found the no%d!\n",mid);
??? else
??????? printf("the number is not found!\n");
}

　　七、插入法

　　把一個數插到有序數列中，插入后數列仍然有序

　　基本思想：n個有序數（從小到大）存放在數組a(1)—a(n)中，要插入的數x。首先確定x插在數組
??? 中的位置P；（可由以下語句實現）
#define N 10

void insert(int a[],int x)
{
??? int p, i;
??? p=0;

??? while(x>a[p]&&p<N)
??????? p++;

??? for(i=N; i>p; i--)
??????? a[i]=a[i-1];

??? a[p]=x;
}

main()
{
??? int a[N+1]={1,3,4,7,8,11,13,18,56,78}, x, i;

??? for(i=0; i<N; i++)
??????? printf("%d,", a[i]);

??? printf("\nInput x:");
??? scanf("%d", &x);
??? insert(a, x);

??? for(i=0; i<=N; i++) printf("%d,", a[i]);
??????? printf("\n");
}

　　八、矩陣（二維數組）運算

（1）矩陣的加、減運算
C(i,j)=a(i,j)+b(i,j) 加法
C(i,j)=a(i,j)-b(i,j) 減法

（2）矩陣相乘
（矩陣A有M*L個元素，矩陣B有L*N個元素，則矩陣C=A*B有M*N個元素）。矩陣C中任一元素
(i=1,2,…,m; j=1,2,…,n)

#define M 2
#define L 4
#define N 3

void mv(int a[M][L], int b[L][N], int c[M][N])
{
??? int i, j, k;
??? for(i=0; i<M; i++)
??? for(j=0; j<N; j++)
??? {
??????? c[i][j]=0;

??????? for(k=0; k<L; k++)
??????????? c[i][j]+=a[i][k]*b[k][j];
??? }
}

main()
{
??? int a[M][L]={{1,2,3,4},{1,1,1,1}};
??? int b[L][N]={{1,1,1},{1,2,1},{2,2,1},{2,3,1}}, c[M][N];
??? int i, j;
??? mv(a,b,c);

??? for(i=0; i<M; i++)
??? {
??????? for(j=0; j<N; j++)
??????????? printf("%4d", c[i][j]);

??????? printf("\n");
??? }
}

（3）矩陣傳置
例:有二維數組a(5,5)，要對它實現轉置，可用下面兩種方式：

#define N 3

void ch1(int a[N][N])
{
??? int i, j, t;
??? for(i=0; i<N; i++)
??? for(j=i+1; j<N; j++)
??? {
??????? t=a[i][j];
??????? a[i][j]=a[j][i];
??????? a[j][i]=t;
??? }
}

void ch2(int a[N][N])
{
??? int i, j, t;
??? for(i=1; i<N; i++)
??? for(j= 0; j<i; j++)
??? {
??????? t=a[i][j];
??????? a[i][j]=a[j][i];
??????? a[j][i]=t;
??? }
}

main()
{
??? int a[N][N]={{1,2,3},{4,5,6},{7,8,9}}, i, j;
??? ch1(a); /*或ch2(a);*/

??? for(i=0; i<N; i++)
??? {
??????? for(j=0; j<N; j++)
??????????? printf("%4d", a[i][j]);

??????? printf("\n");
??? }
}

（4）求二維數組中最小元素及其所在的行和列
基本思路同一維數組，可用下面程序段實現（以二維數組a[3][4]為例）：
‘變量max中存放最大值，row,column存放最大值所在行列號
#define N 4
#define M 3

void min(int a[M][N])
{
??? int min, row, column, i, j;
??? min=a[0][0];
??? row=0;
??? column=0;

??? for(i=0; i<M; i++)
??? for(j=0; j<N; j++)
??????? if(a[i][j]<min)
??????? {
??????????? min=a[i][j];
??????????? row=i;
??????????? column=j;
??????? }

??? printf("Min=%d\nAt Row%d,Column%d\n", min, row, column);
}

main()
{
??? int a[M][N]={{1,23,45,-5},{5,6,-7,6},{0,33,8,15}};
??? min(a);
}

　　九、迭代法

　　算法思想：對于一個問題的求解x，可由給定的一個初值x0，根據某一迭代公式得到一個新的值x1，
這個新值x1比初值x0更接近要求的值x；再以新值作為初值，即：x1→x0,重新按原來的方法求x1,重復
這一過和直到|x1-x0|<ε(某一給定的精度)。此時可將x1作為問題的解。

例：用迭代法求某個數的平方根。 已知求平方根的迭代公式為：
#include<math.h>

float fsqrt(float a)
{
??? float x0, x1;
??? x1=a/2;

??? do
??? {
??????? x0=x1;
??????? x1=0.5*(x0+a/x0);
??? }while(fabs(x1-x0)>0.00001);

??? return(x1);
}

main()
{
??? float a;
??? scanf("%f", &a);
??? printf("genhao =%f\n", fsqrt(a));
}

　　十、數制轉換

　　將一個十進制整數m轉換成 →r(2－16)進制字符串。

　　方法：將m不斷除 r 取余數，直到商為零，以反序得到結果。下面寫出一轉換函數，參數idec為十
進制數，ibase為要轉換成數的基（如二進制的基是2，八進制的基是8等），函數輸出結果是字符串。

char *trdec(int idec, int ibase)
{
??? char strdr[20], t;
??? int i, idr, p=0;

??? while(idec!=0)
??? {
??????? idr=idec % ibase;
??????? if(idr>=10)
??????????? strdr[p++]=idr-10+65;
??????? else
??????????? strdr[p++]=idr+48;

??????? idec/=ibase;
??? }

??? for(i=0; i<p/2; i++)
??? {
??????? t=strdr[i];
??????? strdr[i]=strdr[p-i-1];
??????? strdr[p-i-1]=t;
??? }

??? strdr[p]=’\0’;
??? return(strdr);
}

main()
{
??? int x, d;
??? scanf("%d%d", &x, &d);
??? printf("%s\n", trdec(x,d));
}

　　十一、字符串的一般處理

　　1．簡單加密和解密
加密的思想是： 將每個字母C加（或減）一序數K，即用它后的第K個字母代替，變換式公式：c=c+k
例如序數k為5，這時 A→ F， a→f，B→?G… 當加序數后的字母超過Z或z則 c=c+k -26
例如：You are good→ Dtz fwj ltti
解密為加密的逆過程
將每個字母C減（或加）一序數K，即 c=c-k,
例如序數k為5，這時 Z→U，z→u，Y→T… 當加序數后的字母小于A或a則 c=c-k +26

下段程序是加密處理：
#include<stdio.h>

char *jiami(char stri[])
{
??? int i=0;
??? char strp[50],ia;

??? while(stri[i]!=’\0’)
??? {
??????? if(stri[i]>=’A’&&stri[i]<=’Z’)
??????? {
??????????? ia=stri[i]+5;
??????????? if (ia>’Z’)
??????????????? ia-=26;
??????? }
??????? else if(stri[i]>=’a’&&stri[i]<=’z’)
??????? {
??????????? ia=stri[i]+5;
??????????? if (ia>’z’)
??????????????? ia-=26;
??????? }
??????? else
??????????? ia=stri[i];

??????? strp[i++]=ia;
??? }

??? strp[i]=’\0’;
??? return(strp);
}

main()
{
??? char s[50];
??? gets(s);
??? printf("%s\n", jiami(s));
}
2．統計文本單詞的個數
輸入一行字符，統計其中有多少個單詞，單詞之間用格分隔開。

算法思路：
（1）從文本（字符串）的左邊開始，取出一個字符；設邏輯量word表示所取字符是否是單詞內的字符，
??? 初值設為0
（2）若所取字符不是“空格”，“逗號”，“分號”或“感嘆號”等單詞的分隔符，再判斷word是否為1，若
???? word不為1則表是新單詞的開始，讓單詞數num = num +1，讓word =1;
（3）若所取字符是“空格”，“逗號”，“分號”或“感嘆號”等單詞的分隔符， 則表示字符不是單詞內字符，讓word=0;
(4) 再依次取下一個字符，重得（2）(3)直到文本結束。

下面程序段是字符串string中包含的單詞數
#include "stdio.h"

main()
{
??? char c,string[80];
??? int i,num=0,word=0;
??? gets(string);

??? for(i=0;(c=string[i])!='\0';i++)
??????? if(c==' ') word=0;
??????? else if(word==0)
??????? {
??????????? word=1;
??????????? num++;
??????? }

??? printf("There are %d word in the line.\n",num);
}

　　十二、窮舉法
　　
　　窮舉法（又稱“枚舉法”）的基本思想是：一一列舉各種可能的情況，并判斷哪一種可能是符合要
求的解，這是一種“在沒有其它辦法的情況的方法”，是一種最“笨”的方法，然而對一些無法用解析法
求解的問題往往能奏效，通常采用循環來處理窮舉問題。

例： 將一張面值為100元的人民幣等值換成100張5元、1元和0.5元的零鈔，要求每種零鈔不少于1張，問有哪幾種組合？
main()
{
??? int i, j, k;
??? printf(" 5元 1元 5角\n");

??? for(i=1; i<=20; i++)
??? for(j=1; j<=100-i; j++)
??? {
??????? k=100-i-j;
??????? if(5*i+1*j+0.5*k==100)
??????????? printf(" %3d %3d %3d\n", i, j, k);
??? }
}

　　十三、遞歸算法
　　
　　用自身的結構來描述自身，稱遞歸
　　
　　VB允許在一個Sub子過程和Function過程的定義內部調用自己，即遞歸Sub子過程和遞歸Function
函數。遞歸處理一般用棧來實現，每調用一次自身，把當前參數壓棧，直到遞歸結束條件；然后從棧
中彈出當前參數，直到棧空。
遞歸條件：（1）遞歸結束條件及結束時的值；（2）能用遞歸形式表示，且遞歸向終止條件發展。

例：編fac(n)=n! 的遞歸函數
int fac(int n)
{
??? if(n==1)
??????? return(1);
??? else
??????? return(n*fac(n-1));
}

main()
{
??? int n;
??? scanf("%d", &n);
??? printf("n!=%d\n", fac(n));
}