C算法考点.docx
《C算法考点.docx》由会员分享，可在线阅读，更多相关《C算法考点.docx（38页珍藏版）》请在冰点文库上搜索。
C算法考点
算法考点
非数值计算常用经典算法
基本操作：
交换（*****）
实现变量的值的交换最常用的方法是借助一个临时变量来实现将两个数的值进行交换。
voidswap（intx,inty）
{inttemp;
temp=x;x=y;y=temp;
}
值传递，单向的，如果主函数调用了此函数，尽管形式参数x和y的值交换了，而主函数中的实际参数是不会改变的。
要想实现地址传递，应该用指针实现。
voidswap（int*x,int*y）
{inttemp;
temp=*x;
*x=*y;
*y=temp;
}
函数调用时将实参的地址传递给指针x和y，例如：
swap（&a,&b）;实现x和y指向的地址单元的值的交换，即a和b的值的交换。
1．排序（*****）
排序就是将数组中的元素按从大到小的顺序或者从小到大的顺序重新排列。
1）冒泡排序（*****）
下面的函数是按升序从前往后排。
voidBubbleSort（inta[],intn）
{inti,j,tmp;
for（i=0;i{for（j=0;jif（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_i,tmp;
for（i=0;i{min=i;/*假设第一个数最小，记录其下标*/
for（j=i+1;jif（a[j]/*找最小的，将最小数的下标记录下来*/
if（i!
=min）
{tmp=a[i];a[i]=a[min];a[min]=tmp;}
/*将最小的数与第一个数进行交换*/
}
}
3）插入排序（***）
算法思想：
插入排序的基本操作就是将一个数据插入到已经排好序的有序数组中，从而得到一个新的、个数加1的有序数组。
voidInsertSort（inta[],intn）
{inti,j,tmp;
for（i=1;i{tmp=a[i];/*空出a[i]单元*/
for（j=i-1;j>=0&&a[j]>tmp;j--）
a[j+1]=a[j];/*大于tmp的数向后移位*/
a[j+1]=tmp;/*tmp归位*/
}
}
2．归并（或合并）（****）
归并就是将两个有序数组A、B合并成另一个有序的数组C（升序或降序）。
算法步骤：
1先在A、B数组中各取第一个元素进行比较，将小的元素放入C中。
2取小的元素所在数组的下一个元素与另一个数组中上次比较后较大的元素比较。
3重复上述比较过程，直到某个数组被先排完。
4将另一个数组剩余元素抄入C中，合并排序完成。
voidmerge（inta[m],intb[n],intc[]）
{ia=0;ib=0;ic=0;
while（ia{if（a[ia]else{c[ic]=b[ib];ib++;}
ic++;
}
while（ia/*a中剩余元素抄入c中*/
while（ib}
3．查找（****）
查找，就是判断一个数是否是数组中的某个元素。
最常见最简单的查找方法为线性法查找，对于已经排过序的数组，可以采用折半法查找。
1）线性法查找
没有排序的数组，只能采用线性法查找
基本思想：
将x与数组中的各个元素从头到尾进行比较，找到返回数组下标，找不到，返回-1。
#defineN10
intfind（inta[N],intkey）
{for（i=0;iif（a[i]==key）{return（i）;break;}/*返回数组元素下标*/
if（i==N）return（-1）;
}
2）折半法查找
折半查找法也称为二分查找法，只能对有序数组进行查找。
将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。
如果x如果x>a[n/2]，则我们只要在数组a的右半部分继续搜索x。
#defineN10
intfind（inta[N],intkey）
{intm;
p=0;q=N-1;
/*p为第1个元素的下标，q为最后一个元素的下标*/
while（p<=q）
{m=（p+q）/2;/*m为中间元素的下标*/
if（a[m]==key）{return（m）;break;}
elseif（keyelsep=m+1;
}
if（p>q）return（-1）;
}
4．穷举（***）
穷举法的基本思想是：
一一列举各种可能的情况，并判断哪一种可能是符合要求的解。
这是一种在“没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。
【例题】有1、2、3、4四个数字，能组成多少个互不相同且无重复数字的三位数？
都是多少？
程序分析：
可填在百位、十位、个位的数字都是1、2、3、4。
组成所有的排列后再去掉不满足条件的排列。
main（）
{inti,j,k;
for（i=1;i<5;i++） ／*以下为三重循环*/
for（j=1;j<5;j++）
for（k=1;k<5;k++）
if（i!
=k&&i!
=j&&j!
=k） /*确保i、j、k三位互不相同*/
printf（"%d,%d,%d\n",i,j,k）;
}
数值计算常用经典算法
级数计算（递推法）（*****）
累加（*****）
使用循环时，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示最后结果的初值。
用c语言实现1+2+3+4+5+……+n的累加。
【方法1】for循环实现
intadd（intn）
{inti,sum=0;
for（i=1;i<=n;i++）sum=sum+i;
returnsum;
}
【方法2】while循环实现
intadd（intn）
{inti,sum;
sum=0;i=1;
while（i<=n）
{sum=sum+i;
i=i+1;
}
returnsum;
}
do-while循环也可以实现累加。
累乘
在累乘之前，一定要将用于存放乘积的变量的值初始化为1。
用c语言求n的阶乘：
n!
=1234…n（n>=0）
intproduct（intn）
{inti,p=1;
for（i=2;i<=n;i++）p=p*i;
returnp;
}
如果n的值比较大，考虑累乘的结果可能会超过32767，函数返回值应定义为长整型，确保程序运行的正确。
longfunc（intn）
{inti;
longp=1;
for（i=2;i<=n;i++）p*=i;
returnp;
}
用递推法求n!
的程序段如下：
for（fac=1,i=2;i<=n;i++）fac=fac*i;
【例题】有一分数序列：
求出这个数列的前20项之和。
本题主要要抓住分子与分母的变化规律。
main（）
{intn,t,number=20;
floata=2,b=1,s=0;/*a表示分子，b表示分母*/
for（n=1;n<=number;n++）
{ s=s+a/b;
t=a;
a=a+b;
b=t;
}
printf（"sumis%9.6f\n",s）;
}
【例题】求1+2!
+3!
+...+20!
的和
main（）
{floatn,s=0,t=1;
for（n=1;n<=20;n++）
{ t*=n;
s+=t;
}
printf（"1+2!
+3!
...+20!
=%e\n",s）;
}
运行结果为：
1+2!
+3!
...+20!
=2.561327e+18
本题将变量定义为float，因为long型数据的范围为-21亿～21亿。
无法容纳求得的结果。
int型的就更不用说了，表示范围只有-32768～32767。
【例题】以下程序的功能是：
根据公式和精度计算π的近似值。
#include
#include
doublePI（doubleeps）
{doubles=0,t=1.0;intn;
for（n=1;___________;n++）
{s+=t;t=t*__________;}
return2.0*s;
}
voidmain（）
{doublee=1e-6;
/*e是计算精度要求，这里表示允许运算结果值在小数点后第6位有误差*/
printf（"%f",_________________）;
}
【例题】以下程序通过给出的公式计算π的近似值，计算过程在所加项的值小于10-6时终止。
#include
main（）
{doublesum=0.5,t,t1,t2,t3;
intodd=1,even=2;
t=t1=t2=1.0;t3=0.5;
while（t>1e-10）
{t1=_________;
odd+=2;even+=2;
t2=1.0/odd;
t3=___________;
t=t1*t2*t3;
sum+=t;
}
printf（"\nPI=%.8lf",_____________;
}
解决各类问题的一般算法
整数问题
1．素数问题
素数是指除1和本身外不能被其他任何整数整除的正整数。
1）判断m是否是素数的函数
#include
intprime（intm）
{inti,k;
k=sqrt（m）;/*k是不大于m的平方根的最大整数*/
for（i=2;i<=k;i++）
if（m%i==0）return0;/*不是素数，返回0*/
return1;
}
2）把m～n范围内的素数依次放入数组a中，返回素数个数。
#include
intprime（inta[N],intm,intn）
{inti,k,j；
j=0;/*j为素数的个数*/
for（i=m;i<=n;i++）
{for（k=2;k<=sqrt（i）;k++）
if（i%k==0）break;/*i不是素数，内循环结束*/
if（k>sqrt（i））a[j++]=i;/*i为素数，存入数组*/
}
returnj;
}
2．求最大公约数和最小公倍数
1）求最大公约数（欧几里得算法）
最大公约数的算法也叫欧几里得算法，采用的是辗转相除法求两数m、n最大公约数，其算法步骤如下：
1对于已知两数m和n，；
2将m除以n得余数r；
3若r为0，则n为求得的最大公约数，算法结束，否则执行下一步；
4n赋给m，r赋给n，再重复执行上面的两步。
算法结束时，m中所存放的值即为最大公约数。
gcd（intm,intn）
{intt,r;
if（mwhile（n）
{r=m%n;/*求余*/
m=n;n=r;/*窜位，准备下次求余*/
}
returnm;
}
2）求最小公倍数
算法：
两数之积除以最大公约数所得的值即为最小公倍数
gcd（intm,intn）
{intt,r,p;
p=m*n;
while（n）
{r=m%n;m=n;n=r;}
returnp/m;
}
如果在同一个程序中，可以直接调用最大公约数的函数。
gcd（intm,intn）
{intt,r;
p=m*n;
returnp/gcd（m,n）;
}
3．整数拆分与拼接
1）拆整数
求一个整数的位数及将各位数字放在数组中，返回整数的位数。
intpdigit（longn,inta[]）
{inti=0,k;
while（n）
{a[i++]=n%10;/*取余数*/
n=n/10;/*求整数，去掉余数后的数*/
}
return（i）;
}
下面的函数是求整数n的各位数字之和。
intsum（intn）
{ints=0;
while（n）
{s=s+n%10;n=n/10;}
return（s）;
}
若求各位数字之积，只要将s的初值“0”改为“1”，“加”改成“乘”即可。
2）拼整数
在键盘输入若干个数字，直到输入负数为止，输出这些数字组成的数，先输入的数字作为最高位。
main（）
{longnum=0;
intn;
scanf（"%d",&n）;
while（n>=0）
{num=num*10+n;
scanf（"%d",&n）;
}
printf（"%ld",num）;
}
4．求反序数和回文数
1）求反序数
将一个数的数字排列顺序完全颠倒过来，就变成另一个数，这个数就是该数的反序数，如123的反序数为321。
intinte（intn）
{intnum=0;
while（n）
{num=num*10+n%10;
n=n/10;
}
return（num）;
}
2）求回文数
一个数与它的反序数相等，这样的数称为回文数。
例如12321，6336等就是回文数。
判断一个数是否是回文数，先求出它的反序数，再判断两者是否相等。
①判断m是否是回文数的函数
intpalin（intn）
{ints=0;
m=n;
while（m）
{s=s*10+m%10;
m=m/10;
}
if（s==n）return
（1）;
elsereturn（0）;
}
②求指定范围内的回文数
写一个函数，求指定范围内（m1～m2之间）的回文数，保存到指定的数组中，并返回回文数的个数。
intpalin（longm1,longm2,longx[]）
{longi,n,s;/*s是i的回文数*/
intk=0;/*k回文数个数，数组下标*/
for（i=m1;i<=m2;i++）
{n=i;s=0;
while（n）/*求反序数*/
{s=s*10+n%10;
n=n/10;
}
if（i==s）{x[k]=i;k++;}/*若是回文数，放入数组a中*/
}
returnk;/*返回回文数的个数*/
}
5．因子、完全数、互满数对
1）求a的因子并存放在数组中
因子是指能被a整除的数，包含1和该数本身，真因子包含1不包含本身。
intfun（inta,intx[N]）
{inti,j=0;
for（i=1;i<=a;i++）
if（a%i==0）x[j++]=i;
returnj;/*返回因子的个数*/
}
2）找指定范围内的完全数
完全数是指一个正整数的所有真因子之和等于本身的数，因子包含1但不包含本身，例如：
:
6=1+2+3，28=1+2+4+7+14，所以6和28是完全数。
intfun（inta[N],intm,intn）
{inti,j,s;
intk=0;
for（i=m;i<=n;i++）
{s=0;for（j=1;jif（i%j==0）s=s+j;
if（i==s）a[k++]=i;
}
returnk;
}
3）互满数对（亲密数对）
互满数对是指两个数中，其中的一个数的真因子之和都等于另一个数。
即a的真因子之和为b，b的真因子之和为a。
如：
220与184，1184与1210就是互满数对。
intfun（ints[][2],intm1,intm2）
{ints1,s2,count,a,i,j;
count=0;
for（a=m1;a<=m2;a++）
{s1=1;s2=1;
for（i=2;ifor（j=2;jif（（s2==a）&&（a{s[count][0]=a;
s[count][1]=s1;
count++;
}
}
returncount;
}
6．求满足条件的数或数对
本类型的题目是近年考得比较多的类型，其变化也比较多，需要分析，灵活运用。
比较简单的如同构数，还有典型的Armstrong数。
实际上，素数、回文数、完全数等都是属于满足要求的数。
很多问题都是由基本的算法变化来的。
1）同构数
同构数是其值等于其右边数字平方数的整数。
如25,36都是同构数（25=52,36=62）。
下面的程序是求1～99之间的所有同构数。
main（）
{inti,k;
for（i=1;i<100;i++）
{k=i%10;/*求未位数*/
if（k*k==i）printf（“%d,“,i）;/*输出满足要求的数*/
}
2）Armstrong数
一个ｎ位的正整数，其各位数的ｎ次方之和等于这个数，称这个数为Armstrong数。
例如，153＝13＋53＋33。
1634＝14＋64＋34＋44。
下面的程序求所有三位和四位数的Armstrong数。
main（）
{inti,j,k,m,t,s,a[5],b[5];
for（m=100;m<10000;m++）
{k=m;j=0;/*k为临时变量，j为位数*/
while（k）{a[j++]=k%10;k=k/10;}/*a中存放各位数字*/
for（i=0;i{b[i]=1;/*b中存放各位数字之乘积*/
for（t=0;t}
for（s=0,t=0;tif（s==m）printf（"%d",m）;/*输出满足条件的数*/
}
}
3）求满足条件的数或数对
例题：
找出所有满足下列条件的正整数对a，b：
（1）a+b=99;
（2）a编写函数intfind（intm,intn），其功能是找出两个正整数的最小公倍数返回。
编写main函数，找出所有满足条件的正整数对。
分析：
正整数对要求满足a+b=99，表示a和b都在1到98的范围内，循环变量的变化从1到98就可以了。
第二个要求是a第三个条件，先写一个求最小公倍数的函数，再用if语句调用并判断最小公倍数是否是3的倍数。
#include
main（）
{inta,b;
for（a=1;a<99;a++）
for（b=a;b<99;b++）/*b从a开始，确保aif（a+b==99）/*第一个条件a+b=99*/
if（find（a,b）%3==0）/*a,b的最小公倍数是3的倍数*/
printf（"%d+%d=99,mingps:
%d\n",a,b,find（a,b））;}
intfind（intm,intn）/*求两个整数的最小公倍数*/
{intp,r;
p=m*n;
while（n）{r=m%n;m=n;n=r;}
return（p/m）;
}
（2）找出指定范围内（如500～800），本身及其平方数均由不同数字组成的整数。
要求：
编写功能函数intfine（longn），用来判断某数是否是由不同数字组成的整数，若是则返回1，否则返回0。
在main函数中输出满足条件的该数本身及它的平方，如：
504*504=254016，507*507=257049。
#include
main（）
{longi,j;
for（i=500;i<=800;i++）
if（fine（i）&&fine（i*i））
printf（"\n%ld*%ld=%ld",i,i,i*i）;
}
intfine（longn）
{inti,j=0,sum=0,a[10]={0};
/*a的下标为n的各位数字，先将各元素初始化*/
while（n）
{i=n%10;/*数字分离*/
a[i]=1;/*n中有某数字，将对应的元素置为1*/
n=n/10;
j++;}/*j为n的位数*/
for（i=0;i<10;i++）/*求n共有多少个不同的数字*/
{if（a[i]）sum=sum++;}/*sum为不同数字的个数*/
if（sum==j）return
（1）;
elsereturn（0）;
}
例题：
取出一个十进制正整数中的所有奇数数字，用这些数字构成一个最小数。
（1）编写函数longfun（longs），其函数功能是取出十进制整数s中的所有奇数数字，用这些数字组成一个最小数，函数返回该数。
（2）编写main函数，接收键盘输入的一个长整型数，用该整数作为实参调用fun函数，输出得到的最小数。
测试数据：
876531429
运行结果：
13579
例题：
求级数前n项之和S。
（1）编写函数doublefun（doubleeps），其功能是计算下列正项级数的部分和，当级数某项的值小于eps时，函数返回计算结果。
其中：
Pi（i=1，2，3，…，n）是500以内的素数序列中的第i个素数。
500以内的素数序列为2，3，5，7，11，13，17，…。
升级会员 