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

　　一,、計數(shù)、求和,、求階乘等簡單算法

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

　　例：用隨機函數(shù)產(chǎn)生100個[0,，99]范圍內(nèi)的隨機整數(shù)，統(tǒng)計個位上的數(shù)字分別為1,，2,，3，4,，5,，6，7,，8,，9，0的數(shù)的個數(shù)并打印出來,。

本題使用數(shù)組來處理,，用數(shù)組a[100]存放產(chǎn)生的確100個隨機整數(shù)，數(shù)組x[10]來存放個位上的數(shù)字分別為1,，2,，3，4,，5,，6，7,，8,，9， 0的數(shù)的個數(shù),。即個位是1的個數(shù)存放在x[1]中,，個位是2的個數(shù)存放在x[2]中，……個位是0的個數(shù)存放在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");
}

　　二,、求兩個整數(shù)的最大公約數(shù)、最小公倍數(shù)

　　分析：求最大公約數(shù)的算法思想：(最小公倍數(shù)=兩個整數(shù)之積/最大公約數(shù))
(1) 對于已知兩數(shù)m,，n,，使得m>n；
(2) m除以n得余數(shù)r,；
(3) 若r=0,，則n為求得的最大公約數(shù)，算法結束,；否則執(zhí)行(4),；
(4) m←n,，n←r，再重復執(zhí)行(2),。
例如: 求 m=14 ,n=6 的最大公約數(shù). 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("最大公約數(shù):%d\n",n);
printf("最小公倍數(shù):%d\n",nm/n);
}

　　三,、判斷素數(shù)

　　只能被1或本身整除的數(shù)稱為素數(shù) 基本思想：把m作為被除數(shù)，將2—INT（ ）作為除數(shù),，如果都除不盡,，m就是素數(shù)，否則就不是,。（可用以下程序段實現(xiàn)）
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("該數(shù)是素數(shù)");
else
printf("該數(shù)不是素數(shù)");
}
將其寫成一函數(shù),若為素數(shù)返回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的偶數(shù)都可以分解為兩個素數(shù)之和）
基 本思想：n為大于等于6的任一偶數(shù),，可分解為n1和n2兩個數(shù)，分別檢查n1和n2是否為素數(shù),，如都是,，則為一組解。如n1不是素數(shù),，就不必再檢查n2是 否素數(shù),。先從n1=3開始，檢驗n1和n2（n2=N-n1）是否素數(shù),。然后使n1+2 再檢驗n1,、n2是否素數(shù)，… 直到n1=n/2為止,。

　　利用上面的prime函數(shù),，驗證哥德巴赫猜想的程序代碼如下：
#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個數(shù)的序列（存放在數(shù)組a(n)中）,，從中選出最小的數(shù),，與第1個數(shù)交換位置；
2）除第1 個數(shù)外,，其余n-1個數(shù)中選最小的數(shù),，與第2個數(shù)交換位置；
3）依次類推,，選擇了n-1次后,，這個數(shù)列已按升序排列。

程序代碼如下：
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．冒泡法排序（升序）

　　基本思想：(將相鄰兩個數(shù)比較,，小的調(diào)到前頭)
1）有n個數(shù)（存放在數(shù)組a(n)中）,，第一趟將每相鄰兩個數(shù)比較，小的調(diào)到前頭,，經(jīng)n-1次兩兩相鄰比較后,，最大的數(shù)已“沉底”,，放在最后一個位置，小數(shù)上升“浮起”,；
2）第二趟對余下的n-1個數(shù)（最大的數(shù)已“沉底”）按上法比較，經(jīng)n-2次兩兩相鄰比較后得次大的數(shù),；
3）依次類推,，n個數(shù)共進行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．合并法排序（將兩個有序數(shù)組A,、B合并成另一個有序的數(shù)組C，升序）

　　基本思想：
1）先在A,、B數(shù)組中各取第一個元素進行比較,，將小的元素放入C數(shù)組；
2）取小的元素所在數(shù)組的下一個元素與另一數(shù)組中上次比較后較大的元素比較,，重復上述比較過程,，直到某個數(shù)組被先排完；
3）將另一個數(shù)組剩余元素抄入C數(shù)組,，合并排序完成,。
程序段如下：
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．①順序查找法（在一列數(shù)中查找某數(shù)x）

基本思想：一列數(shù)放在數(shù)組a[1]---a[n]中,，待查找的數(shù)放在x 中,，把x與a數(shù)組中的元素從頭到尾一一進行比較查找。用變量p表示a數(shù)組元素下標,，p初值為1,，使x與a[p]比較，如果x不等于a[p],，則使p=p+ 1,，不斷重復這個過程；一旦x等于a[p]則退出循環(huán),；另外,，如果p大于數(shù)組長度，循環(huán)也應該停止,。（這個過程可由下語句實現(xiàn)）
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);
}
思考：將上面程序改寫一查找函數(shù)Find,，若找到則返回下標值，找不到返回-1
②基本思想：一列數(shù)放在數(shù)組a[1]---a[n]中,，待查找的關鍵值為key,，把key與a數(shù)組中的元素從頭到尾一一進行比較查找，若相同,，查找成功,，若找不到,，則查找失敗。(查找子過程如下,。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．折半查找法（只能對有序數(shù)列進行查找）

　　基本思想：設n個有序數(shù)（從小到大）存放在數(shù)組a[1]----a[n]中，要查找的數(shù)為x,。用變量bot,、top、mid 分別表示查找數(shù)據(jù)范圍的底部（數(shù)組下界）,、頂部（數(shù)組的上界）和中間,，mid=(top+bot)/2，折半查找的算法如下：
（1）x=a(mid),，則已找到退出循環(huán),，否則進行下面的判斷；
（2）x<a(mid),，x必定落在bot和mid-1的范圍之內(nèi),，即top=mid-1；
（3）x>a(mid),，x必定落在mid+1和top的范圍之內(nèi),，即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");
}

　　七,、插入法

　　把一個數(shù)插到有序數(shù)列中,，插入后數(shù)列仍然有序

　　基本思想：n個有序數(shù)（從小到大）存放在數(shù)組a(1)—a(n)中，要插入的數(shù)x,。首先確定x插在數(shù)組中的位置P,；（可由以下語句實現(xiàn)）
#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");
}

　　八、矩陣（二維數(shù)組）運算

（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）矩陣傳置
例:有二維數(shù)組a(5,5),，要對它實現(xiàn)轉置，可用下面兩種方式：
#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）求二維數(shù)組中最小元素及其所在的行和列
基本思路同一維數(shù)組,，可用下面程序段實現(xiàn)（以二維數(shù)組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,，根據(jù)某一迭代公式得到一個新的值x1,，這個新值x1比初值x0更接近要求的值x；再以新值作 為初值,，即：x1→x0,重新按原來的方法求x1,重復這一過和直到|x1-x0|<ε(某一給定的精度),。此時可將x1作為問題的解。
例：用迭代法求某個數(shù)的平方根,。 已知求平方根的迭代公式為：
#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));
}

　　十,、數(shù)制轉換

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

　　方法：將m不斷除 r 取余數(shù),，直到商為零，以反序得到結果,。下面寫出一轉換函數(shù),，參數(shù)idec為十進制數(shù)，ibase為要轉換成數(shù)的基（如二進制的基是2,，八進制的基是8等）,，函數(shù)輸出結果是字符串。
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加（或減）一序數(shù)K,，即用它后的第K個字母代替，變換式公式： c=c+k
例如序數(shù)k為5,，這時 A→ F,， a→f，B→?G… 當加序數(shù)后的字母超過Z或z則 c=c+k -26
例如：You are good→ Dtz fwj ltti
解密為加密的逆過程
將每個字母C減（或加）一序數(shù)K,，即 c=c-k,
例如序數(shù)k為5,，這時 Z→U，z→u,，Y→T… 當加序數(shù)后的字母小于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．統(tǒng)計文本單詞的個數(shù)
輸入一行字符,，統(tǒng)計其中有多少個單詞，單詞之間用格分隔開,。
算法思路：
（1）從文本（字符串）的左邊開始,，取出一個字符；設邏輯量word表示所取字符是否是單詞內(nèi)的字符,，初值設為0
（2）若所取字符不是“空格”,，“逗號”，“分號”或“感嘆號”等單詞的分隔符,，再判斷word是否為1,，若word不為1則表是新單詞的開始，讓單詞數(shù)num = num +1,，讓word =1;
（3）若所取字符是“空格”,，“逗號”,，“分號”或“感嘆號”等單詞的分隔符， 則表示字符不是單詞內(nèi)字符,，讓word=0;
(4) 再依次取下一個字符,，重得（2）(3)直到文本結束。
下面程序段是字符串string中包含的單詞數(shù)
#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);
}