C语言常用算法总结(共10页).doc

《C语言常用算法总结(共10页).doc》由会员分享，可在线阅读，更多相关《C语言常用算法总结(共10页).doc（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上C语言常用算法归纳 编程题考查学生对一种C语言常用算法的设计能力，以下对二级C语言考试中常用算法进行分类解析。1计数、求和、求阶乘等算法。 这类问题使用循环实现，需注意根据问题确定循环变量的初值、终值及结束条件，以及用于表示计数、和、阶乘的变量的初值。 程序段一：用随机函数产生100个0,99范围内的随机整数，统计个位上的数字分别为1,2,3, 4, 5, 6, 7, 8, 9, 0的数的个数并打印出来。本题使用数组来处理，用数组a100存放产生的100个随机整数，数组x11存放个位上的数字分别为1,2,3,4, 5,6,7,8,9,0的数的个数。即个位是1的个数存放

2、在x1中，个位是2的个数存放在x2中个位是0的个数存放在x10中。 #includevoid main（） int a101,x11,i,p； for(i=0;i11;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； for(i=l;in； （2）除以n得余数r； （3）若r =0，则n为求得的最大公约数，算法结束，否则执行(4)； （4）mn，nr，再重复执行（2）。 求最小公倍数的算

3、法思想：最小公倍数=两个整数之积/最大公约数。 例如，求m=14, n =6的最大公约数。 #includevoid 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； printf(最大公约数：%dn,n)； printf (最小公倍数：%dn，nm/n)； 3.判断素数算法。 只能被1或本身整除的数称为素数，其基本思想是：把m作为被除数，将2m-1作为除数，如果都除

4、不尽，m就是素数，否则就不是。 #includevoid main（） int m,i； printf（Please Input a number:n）； scanf（%d,&m）; for（i=2;i=m） printf（该数是素数）； else printf（该数不是素数）； 将其写成一个函数，若为素数返回1，不是则返回0。 int prime(m) int i； for(i=2;im;i+) if (m%i=0）return 0； return 1； 4排序算法。 程序段一：选择法排序（升序）基本思想：（1)对有n个数的序列（存放在数组a n中），从中选出最小的数，与第1个数交换位置；

5、(2）除第1个数外，其余n-1个数中选最小的数，与第2个数交换位置； （3）依次类推，选择了n-1次后，这个数列已按升序排列。 #includevoid 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）； 程序段二：冒泡法排序（升序） 基本思想：将相邻两个数比较，小的调到前头。 (1)

6、有n个数（存放在数组an中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数己“沉底”，放在最后一个位置，小数上升“浮起”； (2）第二趟对余下的n-1个数（最大的数己“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数； (3)依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-j次两两比较。 #includevoid main() int a10； int i,j,t； printf(Input 10 numbersn）； for(i=0;i10;i+) scanf(%d,& ai)； printf(n)； for(j=0;j9;j+) for(i=0;

7、iai+1) t=ai;ai=ai+1;ai+1=t； printf(the sorted numbersn)； for(i=0;i10;i+) printf(%dn,ai)； 程序段三：合并法排序（将两个有序数组A, B合并成另一个有序的数组C，升序）。 基本思想： （1)先在A, B数组中各取第一个元素进行比较，将小的元素放入C数组； (2）取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完； （3)将另一个数组剩余元素插入C数组，合并排序完成。 #includevoid main（） int a10,b10,c20,i,ia,ib,

8、ic； printf(Please input the first array: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) cis=ais： ia+；ic+； while（ib=9) cic=bib; ib+;ic+; for（i=0;iap&pp;i-） ai=ai-1； ap=x； void mai

9、n（） int aN+1=1,3,4,7,8,11,13,18,56,78，x，i； for（i=0;iN;i+）printf（%d,ai）； printf（nInput x：）； scanf（%d,&x）； insert（a,x）； for (i=0;i=N;i+) printf（d,ai）； printf（n）； 5.查找算法。 程序段一：顺序查找。 基本思想：一列数放在数组a1-a恤中，待查找的数放在x中，把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标，p初值为1，使x与ap比较，如果x不等于ap，则使p=p+1，不断重复这个过程；一旦x等于ap则退出循环。另外

10、，如果P大于数组长度，循环也应该停止。 void main() int a10,p,x,i; printf（Please input the arrayn）; 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) printf(the number is not found！n); else printf(the number is found the no%d！n,p); 程序段二：折半查找法（

11、只能对有序数列进行查找）。 基本思想：设n个有序数（从小到大）存放在数组a1-an中，要查找的数为x.用变量bot, top, mid分别表示查找数据范围的底部（数组下界）、顶部（数组上界）和中间， mid=（top+bot）/2。 折半查找的算法如下： （1) x=amid，则已找到退出循环，否则进行下面的判断； (2）xamid，x必定落在mid+1和top的范围之内，即bot=mid+l； (4)在确定了新的查找范围后，重复进行以上比较，直到找到或者bot=top。 void main() int a10,mid,bot,top,x,i,find； printf（please input

12、 the array:n）； for（i=O;i10;i+） scanf（%d,&ai）； printf（please input the number you want find：n）； scanf（d，&x）； printf（n）； bot0;top9;find=0; while(bottop&find=0) mid=(top+bot)/2； if（x=amid） find=1；break； else if（xamid） top=mid-1； else bot=mid+l； if（find=1） prinf(the number is found the nod！n，mid)； else

13、printf（the number is not found！n）； 6.矩阵（二维数组）运算算法。 矩阵包括加、减、乘、转置等运算。 程序段一：矩阵转置。 有二维数组a5,5，要对它实现转置，可用下面两种方式实现：#define N 3 void chl(int aNN) *方式一* int i,j,t； for（i=0;iN;i+） for（j=i1;jN;j+） t=aij;aij=aji;aji=t； void ch2（int aNN） *方式二* int i,j,t； for（i=1;iN;i+） for（j=0;ji;j+） t=aij;aij=aji;aji=t; main（）

14、int aNN=1,2,3,4,5,6,7,8,9,i,j; chl(a）； *或ch2（a）；* for(i=0;iN;i+) for(j=0;jN;j+) printf（4d，aij）； printf（n）； 程序段二：求二维数组中最小元素及其所在的行和列。 以二维数组a34为例，变量max中存放最大值，row,column分别存放最大值列号。 #define N 4 #define M 3 void min(int aMN） int min,row,column,I,j; min=a00； row=0； column=0； for（i=0;iM;i+） for（j=0;jN;j+） if

15、（aijmin） min=aij;row=i;column=j; printf（Min=dnAt Row%d，Column%dn，min，row，column）； main（） int aMN1,23,45,-5,5,6,-7,6，0,33,8,15； min（a）; 7.迭代算法。 基本思想：对于一个问题的求解x，可由给定的一个初值x0，根据某一迭代公式得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即x1x0,重新按原来的方法求x1，重复这一过程直到|xl-x0|（某一给定的精度）。此时可将x1作为问题的解。 程序段：用迭代法求某个数的平方根。 #includ

16、e #include float fsqrt（float a） float x0,x1； xl=a2； do x0=xl； x1=0.5*（x0+a/x0）； while(fabs(x1-x0)0.00001)； return（x1）； void main() float a； scanf（f,&a）； printf（genhao=fn,fsqrt(a)）； 8数制转换（十进制转换为其他进制）算法。 基本思想：将m不断阶r取余数，直到商为0，以反序得到结果。下而写出一转换函数，参数idec为十进制数，ibase为要转换成数的基数（如二进制的基数是2，八进制的基数为8等），函数输出结果是字符串。

17、 char *trdec（int idec,int ibase） char strdr20,t; int i,idr,p=0; while（idec!0） idr=idecibase； if（idr=10） strdrp+=idr-10+65； else strdrp+=idr+48； idec/=ibase； for（i=0;ip/2;i+） t=strdri; strdri=strdrp-i-1;strdrp-i-1=t; strdrp=0; return（strdr）; main（） int x,d; scanf（%d%d,&x,&d); printf（sn,trdec(x,d）; 9.

18、字符串处理算法。 程序段：统计文本单词的个数。输入一行字符，统计其中有多少个单词，单词之间用空格分隔开。基本思想： （1)从文本（字符串）的左边开始，取出一个字符；设逻辑量word表示所取字符是否是单词内的字符，初值设为O。 (2)若所取字符不是“空格”、“逗号”、“分号”或“感叹号”等单词的分隔符，再判断word是否为1，若word不为1则表示是新单词的开始，让单词数numnum+l，让word1。 (3）若所取字符是“空格”、“逗号”、“分号”或“感叹号”等单词的分隔符，则表示字符不是单词内字符，让word=0。 (4)再依次取下一个字符，重复(2）、(3）直到文本结束。 下面程序段是字符

19、串string中包含的单词数。 #include main（） char c,string80； int i,num=0,word=0； gets(string）； for（i=0；（c=stringi）！0；i+） if（c= ）word=0； else if（word=0） word=1； num+； printf（There are %d word in the linen，num)； 10穷举算法。 基本思想：一一列举各种可能的情况，并判断哪一种可能是符合要求的解，这是一种“在没有其他办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处

20、理穷举问题。程序段：将一张面值为100元的人民币等值换成100张5元、1元和0.5元的零钞，要求每种零钞不少于1张，输出所有组合。 void 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*i1*j0.5*k=100） printf（3d3d3dn，i，j，k）； 11递归算法。 所谓递归是用自身的结构来描述自身。递归处理一般用栈来实现，每调用一次自身，把当前参数压栈，直到递归结束条件，然后从栈中弹出当前参数，直到栈空。 递归条件： （1)递归结束条件及结束时的值；(2)能用递归形式表示，且递归向终止条件发展。 程序段：用递归算法求n!。 int fac(int n） if（n=1) return(1)； else return(n*fac(n-1）； void main() int n； scanf（%d，&n）； printf（n！=%dn，fac（n）； 专心-专注-专业