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

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 的个数存放在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，再重复执行（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=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 （该数不是素数 ） ； 将其写成一个函数，若为素数返回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）依次类推，选择了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中） ，第一趟将每相邻两个数比较，小的调到前头，经 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;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）取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完；（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+； 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 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. 查找算法。程序段一：顺序查找。基本思想：一列数放在数组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） ； 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中，要查找的数为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+） scanf（%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 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； 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 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）; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 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*（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,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）; main（）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）若所取字符是“空格”、 “逗号”、 “分号”或“感叹号”等单词的分隔符，则表示字符不是单词内字符，让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穷举算法。基本思想：一一列举各种可能的情况，并判断哪一种可能是符合要求的解，这是一种“在没有其他办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。程序段： 将一张面值为100 元的人民币等值换成100 张 5 元、1 元和 0.5 元的零钞，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 10 要求每种零钞不少于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*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 页 - - - - - - - - -