《C语言中常用的算法》由会员分享，可在线阅读，更多相关《C语言中常用的算法（11页珍藏版）》请在金锄头文库上搜索。
1、C程序设计的常用算法算法(Algorithm):计算机解题的基本思想方法和步骤。算法的描述：是对要 解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据(输入什么数据、输出什么结果)、采用什么结构、使用什么语句以及如何安排 这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。一、计数、求和、求阶乘等简单算法 此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件， 更要注意用来表示计数、和、阶乘的变量的初值。例：用随机函数产生 100 个0，99范围内的随机整数，统计个位上的数字分别 为 1，2，3，4 ，5，6，7，8，9，0 的数的个数并打印出
2、来。本题使用数组来处理，用数组a100存放产生的确100个随机整数，数组x10 来存放个位上的数字分别为1， 2， 3， 4， 5， 6， 7， 8， 9， 0的数的个数。即个 位是1的个数存放在x1中，个位是2的个数存放在x2中，个位是0的 个数存放在 x10。void main() int a101,x11,i,p;for(i=0;i=11;i+)xi=0;for(i=1;i=100;i+) ai=rand() % 100;printf(%4d,ai); if(i%10=0)printf(n); for(i=1;i=100;i+) p=ai%10;if(p=0) p=10;xp=xp+1;
3、 for(i=1;in；m除以n得余数r；(3) 若r=0,则n为求得的最大公约数，算法结束；否则执行(4)；(4) mn, nr,再重复执行(2)。例如: 求 m=14 ,n=6 的最大公约数. m n r14 6 26 2 0void main() int nm,r,n,m,t;printf(please input two numbers:n);scanf(%d,%d,&m,&n);nm=n*m;if (mn) t=n; n=m; m=t; r=m%n;while (r!=0) m=n; n=r; r=m%n; prin tf(“ 最大公约数:dn,n);prin tf(“ 最小公倍数:
4、dn,nm/n);三、判断素数只能被1或本身整除的数称为素数基本思想：把m作为被除数，将2INT () 作为除数，如果都除不尽，m就是素数，否则就不是。(可用以下程序段实现) void main() int m,i,k;printf(please input a number:n);scanf(%d,&m);k=sqrt(m);for(i=2;i=k)prin tf(该数是素数)；elseprin tf(该数不是素数)；将其写成一函数, 若为素数返回 1，不是则返回0int prime( m%)int i,k;k=sqrt(m);for(i=2;ik;i+)if(m%i=0) return 0
5、;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.hint prime(int m) int i,k; k=sqrt(m);for(i=2;i=k)return 1;
6、elsereturn 0;main() int x,i;printf(please input a even number(=6):n); scanf(%d,&x);if (x6|x%2!=0)printf(data error!n);else for(i=2;i=x/2;i+) if (prime(i)&prime(x-i) printf(%d+%dn,i,x-i);prin tf(“验证成功！)；break;五、排序问题1选择法排序(升序) 基本思想：1) 对有n个数的序列(存放在数组a(n)中)，从中选出最小的数，与第1个数 交换位置；2) 除第 1 个数外，其余 n-1 个数中选最小的
7、数，与第 2个数交换位置；3) 依次类推，选择了 n-1 次后，这个数列已按升序排列。程序代码如下：void main() int i,j,imin,s,a10；printf(n input 10 numbers:n)； for(i=0；i10；i+)scanf(%d,&ai)； for(i=0；i9；i+) imin=i；for(j=i+1；jaj) imin=j；if(i!=imin)s=ai; ai=aimin; aimin=s; printf(%dn,ai);2冒泡法排序(升序) 基本思想：(将相邻两个数比较，小的调到前头)1) 有n个数(存放在数组a(n)中)，第一趟将每相邻两个数比
8、较，小的调到前 头，经 n-1 次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数 上升“浮起”；2) 第二趟对余下的 n-1 个数(最大的数已“沉底”)按上法比较，经 n-2 次两 两相邻比较后得次大的数；3) 依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-j次两两比较。 程序段如下void main() int a10;int i,j,t;printf(input 10 numbersn); for(i=0;i10;i+)scanf(%d,&ai); printf(n);for(j=0;j=8;j+) for(i=0;iai+1) t=ai;ai=ai+1;ai+1=t
9、; printf(the sorted numbers:n);for(i=0;i10;i+) printf(%dn,ai);3合并法排序(将两个有序数组A、B合并成另一个有序的数组C,升序) 基本思想：1) 先在A、B数组中各取第一个元素进行比较，将小的元素放入C数组；2) 取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较， 重复上述比较过程，直到某个数组被先排完；3) 将另一个数组剩余元素抄入C数组，合并排序完成。程序段如下：void main() int a10,b10,c20,i,ia,ib,ic; printf(please input the first array
10、:n);for(i=0;i10;i+) scanf(%d,&ai);for(i=0;i10;i+) scanf(%d,&bi);printf(n);ia=0;ib=0;ic=0;while(ia10&ib10) if(aiabib) cic=aia;ia+;else cic=bib;ib+;ic+;while(ia=9) cic=aia;ia+;ic+;while(ib=9) cic=bib;b+;ic+;for(i=0;i20;i+) printf(%dn,ci);六、查找问题1.顺序查找法(在一列数中查找某数X)基本思想：一列数放在数组a1 an中，待查找的数放在x中，把x与a 数组中的元
11、素从头到尾一一进行比较查找。用变量p表示a数组元素下标，p初 值为1,使x与ap比较，如果x不等于ap，则使p=p+1，不断重复这个过程； 一旦x等于ap则退出循环；另外，如果p大于数组长度，循环也应该停止。(这个过程可由下语句实现)void main() int a10,p,x,i;printf(please input the array:n);for(i=0;i10;i+) scanf(%d,&ai);printf(please input the number you want find:n);scanf(%d,&x);printf(n);p=0;while(x!=ap&p=10)pr
12、intf(the number is not found!n);elseprintf(the number is found the no%d!n,p);思考：将上面程序改写一查找函数Find，若找到则返回下标值，找不到返回-1 基本思想：一列数放在数组a1 an中，待查找的关键值为key,把key 与a数组中的元素从头到尾一一进行比较查找，若相同，查找成功，若找不到， 则查找失败。(查找子过程如下。index:存放找到元素的下标。) void main() int a10,index,x,i; printf(please input the array:n);for(i=0;i10;i+)
13、scanf(%d,&ai); printf(please input the number you want find:n);scanf(%d,&x); printf(n);index=-1;for(i=0;i10;i+)if(x=ai) index=i; break;if(index=-1) printf(the number is not found!n);elseprintf(the number is found the no%d!n,index); 2折半查找法(只能对有序数列进行查找) 基本思想：设n个有序数(从小到大)存放在数组a1an中，要查找的 数为X。用变量bot、top、mid分别表示查找数据范围的底部(数组下界)、顶 部(数组的上界)和中间，mid=(top+bot)/2,折半查找的算法如下：(1) x=a(mid),则已找到退出循环，否则进行下面的判断；(2) xa(mid), x必定落在bot和mid-1的范围之
