二级C期末考试重点算法讲解Word格式.docx
《二级C期末考试重点算法讲解Word格式.docx》由会员分享，可在线阅读，更多相关《二级C期末考试重点算法讲解Word格式.docx（27页珍藏版）》请在冰点文库上搜索。
intproduct（intn）
{inti,p=1;
for（i=2;
i++）p=p*i;
returnp;
如果n的值比较大，函数返回值和存放乘积的变量p应定义为long或者double型。
4.排序（主函数参考教材181-182页）
（1）冒泡排序（主函数main参考教材181-182页）
voidBubbleSort（inta[],intn）
{inti,j,tmp;
for（i=0;
n-1;
i++）/*排序趟次*/
{for（j=0;
j<
n-1-i;
j++）/*从前往后比*/
if（a[j]>
a[j+1]）/*从小到大，升序*/
{tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}/*交换a[j]与a[j+1]，大数后移*/
（2）选择排序
voidSelectSort（inta[],intn）
{inti,j,min,tmp;
i<
i++）
{min=i;
/*假设第一个数最小，记录其下标*/
for（j=i+1;
n;
j++）
if（a[j]<
a[min]）min=j;
/*找最小的数，将最小数的下标记录下来*/
if（i!
=min）
{tmp=a[i];
a[i]=a[min];
a[min]=tmp;
}/*将最小的数与第一个数进行交换*/
（3）插入排序
voidInsertSort（inta[],intn）
{inti,j,tmp;
/*空出a[i]单元*/
for（j=i-1;
j>
=0&
&
a[j]>
tmp;
j--）
a[j+1]=a[j];
/*大于tmp的数向后移位*/
/*tmp归位*/
5.归并（合并）
将两个有序数组A、B合并成另一个有序的数组C（升序或降序）。
升序合并步骤如下：
①先在A、B数组中各取第一个元素进行比较，将小的元素放入C中。
②取小的元素所在数组的下一个元素与另一个数组中上次比较后较大的元素进行比较。
③重复上述比较过程，直到某个数组被先排完。
④将另一个数组剩余元素抄入C中，合并排序完成。
voidmerge（inta[],intm,intb[n],intn,intc[]）
{intia=0,ib=0,ic=0;
while（ia<
m&
ib<
n）
{if（a[ia]<
b[ib]）/*小的元素放入C中*/
{c[ic]=a[ia];
ia++;
}
else{c[ic]=b[ib];
ib++;
ic++;
while（ia<
m）{c[ic]=a[ia];
ic++;
}/*a中剩余元素抄入c中*/
while（ib<
n）{c[ic]=b[ib];
}/*b中剩余元素抄入c中*/
6.查找
（1）线性法查找
线性法查找也叫顺序查找，对于没有排序的数组，只能采用线性法查找。
将x与数组中的各个元素从头到尾进行比较，找到后返回数组下标，若找不到，返回-1。
#defineN10
intfind（inta[N],intkey）
{inti;
N;
if（a[i]==key）{return（i）;
break;
}/*返回数组元素下标*/
if（i==N）return（-1）;
如果对一个升序数组进行线性法查找，循环结束条件改为“i<
N&
a[i]<
=key”，返回-1的条件为（i==N||a[i]>
key）。
（2）折半法查找（二分法查找）
{intm,p,q;
p=0;
q=N-1;
/*p为第1个元素的下标，q为最后一个元素的下标*/
while（p<
=q）
{m=（p+q）/2;
/*m为中间元素的下标*/
if（a[m]==key）{return（m）;
elseif（key<
a[m]）q=m-1;
elsep=m+1;
if（p>
q）return（-1）;
7.级数计算（递推法）
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。
简单地说，就是后一项的值利用前面已求得的项的值得到，典型的递推算法如Fibonacci数列（斐波那契数列），后一项为前两项的和。
基本操作中的累加与累乘都可以看作递推法。
递推公式包括两部分：
开始项的值，以及从前面一、两项得到下一项的计算方法。
用递推式比通项公式算得要快，因为计算每一项都充分利用了前一项的计算结果。
例如，有一分数序列：
…求出这个数列的前20项之和。
（见教材）
8.求最大、最小值
（1）查找一维数组a[]中的最大值，n为数组的大小
intfunmax（inta[],intn）
{inti,max=a[0];
i++）
if（max>
a[i]）max=a[i];
returnmax;
（2）查找二维数组a中的最小值
有一个3×
4的矩阵，求所有元素的最小值及该元素的行号列号。
因为函数只能返回一个值，要想得到最小元素的行号和列号，需要用指针作函数的参数。
intfunmin（inta[][4],int*min_i,int*min_j）
{inti,j,min;
min=a[0][0];
3;
for（j=0;
j<
4;
j++）
if（a[i][j]<
min）
{min=a[i][j];
*min_i=i;
*min_j=j;
returnmin;
{inti,j,min,min_i,min_j,a[3][4]={{3,6,9,12},{2,8,4,6},{5,7,9,10}};
min=funmin（a,&
min_i,&
min_j）;
\nmin=%d,min_i=%d,mim_j=%d\n"
min,min_i,min_j）;
运行结果为：
min=2,min_i=1,mim_j=0
二维数组作函数的参数，第一维的长度可以缺省，第二维的长度不能缺省。
9.求和及平均值
求数组的平均值，先用循环将数组的所有元素相加，最后返回所得的和除以数组元素的个数。
floataverage（inta[],intn）
floatavg;
avg=0;
i++）avg=avg+a[i];
/*若avg的初值为a[0],则i从1开始*/
returnavg/n;
/*若求数组的和，则返回avg，最好将avg变量用sum表示*/
若所求的数组的平均值不是从第一个元素开始的，不管从哪个元素开始，只要将开始元素的地址作为实际参数即可。
例如，数组a共有20个元素，求最后5个元素的平均值的调用方式为：
average（&
a[15],5）;
最后5个元素的第一个元素为a[15]。
10.计数
求满足要求的数的个数。
一般在循环中对每一个元素都用if语句进行判断，满足条件时，计数的变量增1。
例如，对数组中的n个学生成绩，求不及格人数的个数。
intcount（inta[],intn）
{intc=0,i;
if（a[i]<
60）c++;
returnc;
11.数组元素逆序
voidinv（inta[],intn）
{inti,j,t;
for（i=0,j=n-1;
j;
i++,j--）
{t=a[i];
a[i]=a[j];
a[j]=t;
教材237页也可，或者238页用指针。
12．在数组中插入一个数、删除一个元素、数组元素移位
（1）在数组的指定位置插入一个数
如果在a[i]后插入一个x，从最后一个元素开始，将a[i+1]以后的元素往后移，空出位置后将x放在a[i+1]位置处。
程序段如下：
for（j=N-1;
i;
j--）a[j+1]=a[j];
/*移位*/
a[i+1]=x;
/*插入x*/
（2）在已排序的数组中插入一个数
有一个已经排好序的数组，现有一个数x，要求按原来的规律将它插入数组中。
首先判断此数是否大于最后一个数，然后再考虑插入中间的情况，找插入点，先将插入点之后的数依次后移一个位置。
voidinsert（inta[N],intnum）
{inti,j;
if（num>
a[N-2]）a[N-1]=num;
/*插在最后*/
else
N-1;
i++）
if（a[i]>
num）/*找插入点，插在a[i]位置*/
{for（j=N-2;
=i;
j--）
/*将a[i]以后的元素从最后一个元素开始后移*/
a[i]=num;
/*将num放在a[i]处*/
（3）删除数组中的一个元素a[i]
删除数组中的元素a[i]，就是将a[i]以后的元素往前移一个位置。
voiddel（inta[],intn,inti）
{intj;
for（j=i;
j++）a[j]=a[j+1];
（4）数组元素移位
将数组中的一个元素a[i]移动到指定的位置上。
例如，将一维数组下标为i的元素移到第j的位置。
实际上先将该元素删除，然后再将其插到指定位置，元素在删除前先存放在临时变量中。
voidmove（inta[],intn,inti,intj）
{intk,t;
t=a[i];
for（k=i;
k<
k++）a[k]=a[k+1];
/*删除，a[i]以后的元素往前移一个位置*/
for（k=n-1;
k>
=j;
k--）a[k+1]=a[k];
/*a[j]后的元素都要往后移位*/
a[j]=t;
/*插入*/
上面函数中的两个for可以合并为一个for，就是将a[i]与a[j]之间的元素往前移一位：
for（k=i;
若需要移动多个元素，则定义一个数组，用来临时存放需移动的元素，移动时在前面加上循环。
例如，移动字符串中的内容。
移动的规则如下：
把第1到第m个字符平移到字符串的最后，把第m+1到最后的字符串移到字符串的前部。
若字符串中原有的内容为：
ABCDEFGHIJK，m的值为3，则移动后，字符串中的内容应该是DEFGHIJKABC。
voidfun（chara[],intm）
{chart[80];
inti,j,n;
n=strlen（a）;
m;
i++）t[i]=a[i];
/*移走*/
for（i=m,j=0;
i++,j++）a[j]=a[i];
/*移位*/
i++）a[n-m+i]=t[i];
/*移入*/
main（）
{chara[80]="
ABCDEFGHIJK"
;
intm=3;
fun（a,m）;
%s"
a）;
13.素数问题
（1）判断m是否是素数的函数
#include<
math.h>
/*用sqrt函数必须包含数学库函数math.h*/
intprime（intm）
{inti,k;
k=sqrt（m）;
/*k是不大于m平方根的最大整数*/
for（i=2;
=k;
if（m%i==0）return0;
/*不是素数，返回0*/
return1;
/*素数返回1*/
（2）把m～n范围内的素数依次存入数组a中，返回素数个数
intprime（inta[N],intm,intn）
{inti,k,j;
j=0;
/*j为数组a的下标，最终结果为素数的个数*/
for（i=m;
{for（k=2;
=sqrt（i）;
k++）/*判断i是否是素数*/
if（i%k==0）break;
/*i不是素数，内循环结束*/
if（k>
sqrt（i））a[j++]=i;
/*i是素数，存入数组a，下标增1*/
returnj;
/*返回素数个数*/
14.求最大公约数和最小公倍数
（1）求最大公约数（欧几里得算法）
intgcd（intm,intn）
{intt,r;
if（m<
n）{t=m;
m=n;
n=t;
}/*若m<
n，则交换两数。
可以缺省*/
while（n）
{r=m%n;
/*求余*/
n=r;
/*窜位，准备下次求余*/
returnm;
/*返回最大公约数*/
（2）求最小公倍数（两数之积除以最大公约数所得的值即为最小公倍数）
intlcd（intm,intn）
{intt,r,p;
p=m*n;
/*保留两数乘积*/
while（n）/*求最大公约数*/
returnp/m;
/*返回最小公倍数*/
如果在同一个程序中，可以直接调用最大公约数的函数：
returnm*n/gcd（m,n）;
15.整数拆分与拼接
（1）拆整数
求一个整数的位数及将各位数字存放在数组中，返回整数的位数。
intcdigit（longn,inta[]）
{inti=0,k;
while（n）
{a[i++]=n%10;
/*将余数放入数组a中，数组下标增1*/
n=n/10;
/*取整，去掉余数后的数*/
return（i）;
}
下面的函数是求整数n的各位数字之和。
intsum（intn）
{ints=0;
while（n）{s=s+n%10;
return（s）;
若求各位数字之积，只要将s的初值“0”改为“1”，“加”改成“乘”即可。
（2）拼整数
①将键盘输入的正整数数字组成一个整数，先输入的数字为最高位。
{longnum=0;
intn;
&
n）;
while（n>
=0）
{num=num*10+n;
%ld"
num）;
②将数组a中的数拼成整数。
longpdigit（inta[],intn）
inti;
i++）num=num*10+a[i];
return（num）;
{inta[5]={3,2,7,6,7};
\nnum=%ld\n"
pdigit（a,5））;
16.求反序数和回文数
（1）求反序数
将一个数的数字排列顺序完全颠倒过来，就变成另一个数，这个数就是该数的反序数，如123的反序数为321。
求反序数的方法是先将一个数从个位开始用取余数拆分开来，再将拆开的数字拼成整数。
即将拆整数和拼整数两个函数结合起来即可，边拆边拼。
longinte（longn）
while（n）
{num=num*10+n%10;
（2）求回文数
一个数与它的反序数相等，这样的数称为回文数。
如12321，6336等就是回文数。
①判断m是否是回文数
判断一个数是否是回文数，先求出它的反序数，再判断两者是否相等。
longpalin（longm）
{longs=0,n;
n=m;
/*将m存入n中*/
while（n）{s=s*10+n%10;
}/*求反序数*/
if（s==m）return
（1）;
elsereturn（0）;
②求指定范围内的回文数
求指定范围内（m1～m2之间）的回文数，保存到指定的数组中，返回回文数的个数。
intpalin（longm1,longm2,longx[]）
{longi,n,s;
/*s是i的回文数*/
intk=0;
/*k为回文数个数，数组下标*/
for（i=m1;
=m2;
{n=i;
s=0;
}/*求反序数*/
if（i==s）{x[k]=i;
k++;
}/*若是回文数，放入数组a中*/
returnk;
/*返回回文数的个数*/
函数调用时，数组a定义为长整型，输入输出格式为“%ld”，常量后面要加字母“l”，例如，求1000000～200000之间的回文数的调用形式为：
n=palin（100000l,120000l,a）;
其中，n为函数返回的回文数的个数。
17.因子、完全数、互满数对
（1）求a的因子并存放在数组中
因子是指能被a整除的数，包含1和该数本身，真因子包含1不包含本身。
例如，6的因子为1，2，3，6，真因子为1，2，3。
intfun（inta,intx[]）
{inti,j=0;
=a;
i++）/*求a的因子，若求真因子将i<
=a改为i<
a*/
if（a%i==0）x[j++]=i;
/*i是a的因子，存入数组x中，下标增1*/
/*返回因子的个数*/
（2）找指定范围内的完全数
完全数是指一个正整数的所有真因子之和等于本身的数，真因子包含1但不包含本身，例如，6=1+2+3，28=1+2+4+7+14，所以6和28是完全数。
intfun（inta[N],intm,intn）
{inti,j,s;
{s=0;
/*对指定范围内的每个数i都要求其因子之和s*/
for（j=1;
if（i%j==0）s=s+j;
if（i==s）a[k++]=i;
/*是完全数，存入数组中*/
/*返回完全数的个数*/
（3）互满数对（亲密数对）
互满数对是指两个数中，其中的一个数的真因子之和都等于另一个数。
即a的真因子之和为b，b的真因子之和为a。
例如，220与184，1184与1210就是互满数对。
intfun（ints[][2],intm1,intm2）/*求m1～m2的互满数对*/
{ints1,s2,count,a,i,j;
count=0;
for（a=m1;
a<
a++）
{s1=1;
s2=1;
/*1也是真因子*/
a;
if（a%i==0）s1=s1+i;
/*a的真因子之和为s1*/
for（j=2;
s1;
j++）
if（s1%j==0）s2=s2+j;
/*s1的真因子之和为s2*/
if（（s2==a）&
（a<
s1））/*互为真因子之和，存入二维数组s中*/
{s[count][0]=a;
s[count][1]=s1;
count++;
returncount;
/*返回数对个数*/
18.求满足条件的数或数对
求满足条件的数或数对经常采用穷举法。
穷举法的基本思想是：
一一列举各种可能的情况，并判断哪一种是符合要求的解。
这是一种在“没有其他办法情况下的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。
穷举法一般包含两类，一是找出符合特定条件的一组数（一组解），二是验证定理或猜想。
（1）同构数
同构数是其值等于其右边数字平方数的整数。
如25,36都是同构数（25=52,36=62）。
下面的程序是求1～99的所有同构数。
100;
i++）
{k=i%10;
/*求未位数*/
if（k*k==i）printf（"
%d,"
i）;
/*输出满足要求的数*/
（2）Armstrong数（水仙花数）
一个ｎ位的正整数，其各位数的ｎ次方之和等于这个数，称这个数为Armstrong数。
例如，153=13+53+33。
1634=14+64+34+44。
下面的程序求所有三3位和4位的Armstrong数。
{inti,j,k,m,t,s,a[5],b[5];
for（m=100;
m<
10000;
m++）
{k=m;
j=0;
/*k为临时变量，j为
升级会员 