一、计数、求和、求阶乘等简单算法

此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。

例：用随机函数产生 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)&′(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);

}