2022年C语言常用算法总结 2.pdf

《2022年C语言常用算法总结 2.pdf》由会员分享，可在线阅读，更多相关《2022年C语言常用算法总结 2.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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 中。#include void 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）m n，n r，

3、再重复执行（2） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 2 求最小公倍数的算法思想：最小公倍数=两个整数之积 /最大公约数。例如，求 m=14, n =6 的最大公约数。#include void 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=

4、m%n ；while（r!=0 ）m=n;n=r;r=m%n ； printf( 最大公约数：%dn,n) ；printf ( 最小公倍数： %dn ，nm/n) ；3.判断素数算法。只能被 1 或本身整除的数称为素数，其基本思想是：把m 作为被除数，将2m-1作为除数，如果都除不尽，m 就是素数，否则就不是。#include void main（）int m,i ；printf （ Please Input a number:n） ；scanf（%d,&m ）; for（i=2;i=m ）printf （该数是素数 ） ；else printf （该数不是素数 ） ； 将其写成一个函数，若为

5、素数返回1，不是则返回0。int prime(m) int i；for(i=2;im;i+) if (m%i=0 ）return 0 ；return 1；4排序算法。程序段一：选择法排序（升序）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 3 基本思想：（1)对有 n 个数的序列（存放在数组a n中） ，从中选出最小的数，与第1 个数交换位置；(2）除第 1 个数外，其余n-1 个数中选最小的数，与第2 个数交换位置；（3）

6、依次类推，选择了n-1 次后，这个数列已按升序排列。#include void main（）int i,j,imin,s,a10 ；printf （ n Input 10 numbers:n ） ；for（i=0;i 10;i+ ）scanf（d,&ai ） ；for（i=0;i 9;i+ ）imin=i ；for（j=i+1;jaj ） imin=j ；if（i!=imin ）s=ai;ai=aimin;aimin=s; printf （%dn,ai ） ； 程序段二：冒泡法排序（升序）基本思想：将相邻两个数比较，小的调到前头。(1)有 n 个数（存放在数组an中） ，第一趟将每相邻两个数比

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

8、;ai+1=t； printf(the sorted numbersn) ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 4 for(i=0;i 10;i+) printf(%dn,ai)； 程序段三： 合并法排序 （将两个有序数组A, B 合并成另一个有序的数组C，升序） 。基本思想：（1)先在 A, B 数组中各取第一个元素进行比较，将小的元素放入C 数组；(2）取小的元素所在数组的下一个元素与另一数组中上次比较后较大的

9、元素比较，重复上述比较过程，直到某个数组被先排完；（3)将另一个数组剩余元素插入C 数组，合并排序完成。#include void main（）int a10,b10,c20,i,ia,ib,ic ；printf(Please input the first array:n); for（i=0;i10;i+ ）scanf（%d,&a i ） ；for（i=0;i 10;i+ ）scanf（%d，&bi ） ；printf （ n） ；ia=0；ib=0； ic=0；while（ ia10& ib10 ）if（aiabib ） cic=aia ；ia+;else cic=bib ； ib+； i

10、c+； 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 main（）int aN+1=1,3,4,7,8,11,13,18,56,78 ，x，i ； for（i=0;iN;i+）printf（%d,a i ） ； printf（nInput x： ） ； scanf（%d,&x ） ； insert（a,x ） ； for (i=0;i=N;i+) printf（ d,ai） ； printf（ n ） ； 5. 查找算法。程序段一：顺序查

11、找。基本思想：一列数放在数组a1-a恤中，待查找的数放在x 中，把x 与 a 数组中的元素从头到尾一一进行比较查找。用变量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 arrayn）; for（i=0;i10;i+） scanf（%d,&ai）; printf（Please input the number you want find:n）

12、； scanf（%d, x） ; printf（n ）; p=0; while（x!=ap&p=10) printf(the number is not found！n); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 6 printf(the number is found the no%d！ n,p); 程序段二：折半查找法（只能对有序数列进行查找）。基本思想：设n 个有序数（从小到大）存放在数组a1-an中，

13、要查找的数为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 the array:n） ； for（i=O;i10;i+） sc

14、anf（%d,&ai） ； printf（please input the number you want find：n ） ； scanf（ d ，&x） ； printf（n ） ； bot0;top 9;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 no d！n ，mid) ； else printf（the number

15、 is not found！n ） ； 6.矩阵（二维数组）运算算法。矩阵包括加、减、乘、转置等运算。程序段一：矩阵转置。有二维数组a5,5，要对它实现转置，可用下面两种方式实现：#define N 3 void chl(int aNN) * 方式一 *名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - 7 int i,j,t； for（i=0;iN;i+） for（j=i 1;jN;j+） t=aij;aij=aji;aji=t

16、； 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（）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

17、 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（ aijmin）min=aij;row=i;column=j; printf（Min= dnAt Row%d，Column%d n，min，row，column） ； main（） int aMN 1,23,45,-5, 5,6,-7,6 ， 0,33,8,15 ； min（ a）; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

18、 - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - 8 7. 迭代算法。基本思想：对于一个问题的求解x，可由给定的一个初值x0，根据某一迭代公式得到一个新的值x1，这个新值x1 比初值 x0 更接近要求的值x；再以新值作为初值，即 x1x0, 重新按原来的方法求x1，重复这一过程直到|xl-x0|（某一给定的精度） 。此时可将 x1 作为问题的解。程序段：用迭代法求某个数的平方根。 #include #include float fsqrt（float a）float x0,x1； xl=a2； do x0=xl； x1=0.5*（

19、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 等） ，函数输出结果是字符串。 char *trdec（int idec,int ibase）char strdr20,t; int i,idr,

20、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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 9 strdrp-i-1=t; strdrp= 0; return（strdr）; mai

21、n（）int x,d; scanf（%d%d,&x,&d); printf（ sn,trdec(x,d） ）; 9.字符串处理算法。程序段：统计文本单词的个数。输入一行字符，统计其中有多少个单词，单词之间用空格分隔开。基本思想：（ 1) 从文本（字符串）的左边开始，取出一个字符；设逻辑量word 表示所取字符是否是单词内的字符，初值设为O 。 (2)若所取字符不是“空格”、 “逗号”、 “分号”或“感叹号”等单词的分隔符，再判断 word 是否为 1，若 word 不为 1 则表示是新单词的开始，让单词数num num+l，让word 1。 (3）若所取字符是“空格”、 “逗号”、 “分号”或

22、“感叹号”等单词的分隔符，则表示字符不是单词内字符，让word=0。 (4)再依次取下一个字符，重复(2 ） 、(3 ）直到文本结束。下面程序段是字符串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穷举算法。基本思想：一一列举各种

23、可能的情况，并判断哪一种可能是符合要求的解，这是一种“在没有其他办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。程序段： 将一张面值为100 元的人民币等值换成100 张 5 元、1 元和 0.5 元的零钞，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 10 要求每种零钞不少于1 张，输出所有组合。 void main() int i,j,k； printf（

24、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（ 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） ） ； 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -