期末复习Word格式文档下载.docx
《期末复习Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《期末复习Word格式文档下载.docx(28页珍藏版)》请在冰点文库上搜索。
b,&
c,&
d);
for(i=-100.0;
i<
=99.0;
i=i+1)
j=i+1.0;
if((a*i*i*i+b*i*i+c*i+d)*(a*j*j*j+b*j*j+c*j+d)>
0)
continue;
if(a*i*i*i+b*i*i+c*i+d==0)
printf("
%.2lf
"
i);
}
if((a*i*i*i+b*i*i+c*i+d)*(a*j*j*j+b*j*j+c*j+d)<
while(j-i>
=0.000001)
root=(i+j)/2.0;
if((a*i*i*i+b*i*i+c*i+d)*(a*root*root*root+b*root*root+c*root+d)>
i=root;
if((a*j*j*j+b*j*j+c*j+d)*(a*root*root*root+b*root*root+c*root+d)>
j=root;
j);
}
return
0;
二.一元方程的迭代解法
——牛顿迭代法。
s基本思想:
设xk是方程f(x)=0精确解x*附近的一个猜测解,过点Pk(xk,f(xk))作f(x)的切线。
该切线与x轴的交点是方程的另一个近似解。
s迭代公式:
xk+1=xk-f(xk)/f'
(xk)
数组
一.排序问题
⏹选择排序插入排序冒泡排序
⏹选择排序
从所有元素中选择一个最小元素放在a[0](即让最小元素a[p]与a[0]交换),作为第一轮;
第二轮是从a[1]开始到最后的各元素中选择一个最小元素,放在a[1]中…;
以下依此类推。
n个数要进行(n-1)轮。
在第一轮中要比较(n-1)次,第二轮中比较(n-2)次,…,第i轮中比较(n-i)次。
但在每一轮中只进行一次数据交换
⏹冒泡排序
⏹冒泡排序算法设计
⏹为了表述方便,定义以下3个变量:
⏹n——待排序的数的个数,这里n=6
⏹j——扫描遍数,j=1,2,…,n-1
⏹i——第j遍扫描待比较元素的下标,i=1,2,…,n-j;
#include<
//预编译命令
#include<
memory.h>
intmain()//主函数
{
inti=0,j=0,p=0,a[7];
//整型变量
memset(a,0,sizeof(a));
//整型数组初始化
for(i=1;
i<
=6;
i++)//键入6个数,放入a数组中
{
printf("
请输入待排序的数a[%d]="
i);
//提示
scanf("
%d"
&
a[i]);
//用键盘输入整数赋给a[i]
for(j=1;
j<
=5;
j++)//冒泡排序,外层循环
for(i=1;
=6-j;
i++)//内层循环
if(a[i]<
a[i+1])//如果a[i]<
a[i+1]
{
p=a[i];
//让a[i]与a[i+1]交换
a[i]=a[i+1];
a[i+1]=p;
}
for(i=1;
i++)//输出排序结果
%d\n"
a[i]);
//输出a[i]
return0;
}
二.筛法
例:
使用筛法求100以内的所有素数。
⒈思路
①想象将100个数看作沙子和小石头子,让小石头子权称素数;
让沙子当作非素数。
弄一个筛子,只要将沙子筛走,剩下的就是素数了。
2非素数一定是2、3、4……的倍数。
3使用数组,让下标就是100以内的数,让数组元素的值作为筛去与否的标志。
比如筛去以后让元素值为1。
⒉方法的依据
⏹1至100这些自然数可以分为三类:
⏹单位数:
仅有一个数1。
⏹素数:
是这样一个数,它大于1,且只有1和它自身这样两个正因数。
⏹合数:
除了1和自身以外,还有其他正因数。
1不是素数,除1以外的自然数,当然只有素数与合数。
筛法实际上是筛去合数,留下素数。
⒊效率的考虑
⏹
令n为合数(这里是100),c为n的最小正因数
只要找到c就可以确认n为合数将其筛去
⏹注意:
要进行“筛”的1—100的数字是与数组prime[101]的下标相对应的,而每个数组元素的取值只有2个:
是0或1,分别代表(标志)与下标相对应的数字是素数或不是素数
⒋程序框图如下:
⏹for(c=2;
c<
=100;
c=c+1)
⒌该题目的筛法思路
⏹第一块是一个计数型的循环语句,功能是将prime数组清零。
prime[c]=0;
c=2,3,…,100
⏹第二块是正因数d初始化为d=2
⏹所有d的倍数将会被筛掉
⏹第三块是循环筛数。
这里用了一个dowhile语句,属于一种直到型循环,其一般形式为:
do
循环体语句块
while(表达式)
三.从数组中查找特定的数
1.折半查找法
①前提:
数据已按一定的规律(升序或降序)排列好。
②基本思想:
先检索当中的一个数据,看它是否为所需要的数据,如果不是,则判断要找的数据是当中的哪一边,下次就在这个范围内查找
③折半查找举例
⏹设一组升序排列的数:
8,13,21,28,35,41,52,63,71,76,81,95,101,150,164
⏹折半查找“21”的过程:
⏹设三个变量top、mid和bot分别指向数列开头、中间末尾。
81321283541526371768195101150164
①topmidbot
②topmidbot
③topmidbot
④topmidbot
⏹top>
bot时,查找失败。
四.字符数组
字符串处理举例
统计字符数
判断一个由a-z这26个字符组成的字符串中哪个字符出现的次数最多,如果有多个字符出现的次数相同且最多,输出ascii码最小的那个字符以及它出现的次数。
输入字符串最大长度为1000个字符
解题思路
用字符数组存储字符串,一次读入一个字符串到该字符数组中
⏹声明一个数组intsum[26];
记录每个字符出现的次数
⏹遍历字符数组,统计每个字符出现的次数
⏹输出出现次数最小的字符,注意有相同的输出ascii码最小的。
⏹#include<
⏹intmain(){
⏹charstr[1001];
⏹intsum[26],i,nmax;
⏹scanf(“%s”,str);
⏹for(i=0;
26;
i++)
⏹sum[i]=0;
strlen(str);
⏹sum[str[i]-'
a'
]++;
⏹nmax=0;
⏹for(i=1;
⏹if(sum[i]>
sum[nmax])
⏹nmax=i;
⏹printf(“%c%d\n”,(char)(nmax+'
),sum[nmax]);
⏹return0;
⏹}
函数
一.递推
A、B、C、D、E五人合伙夜间捕鱼,凌晨时都疲惫不堪,各自在河边的树丛中找地方睡着了。
日上三竿,A第一个醒来,他将鱼平分作五份,把多余的一条扔回湖中,拿自己的一份回家去了。
B第二个醒来,也将鱼平分为五份,扔掉多余的一条,只拿走自己的一份。
接着C、D、E依次醒来,也都按同样的办法分鱼。
问五人至少合伙捕到多少条鱼?
每个人醒来后看到的鱼数是多少条?
解题思路
假定A、B、C、D、E五人的编号分别为1、2、3、4、5,整数数组fish[k]表示第k个人所看到的鱼数。
fish[1]表示A所看到的鱼数,fish[2]表示B所看到的鱼数……
⏹fish[1]A所看到的鱼数,合伙捕到鱼的总数
⏹fish[2]=(fish[1]-1)*4/5B所看到的鱼数
⏹fish[3]=(fish[2]-1)*4/5C所看到的鱼数
⏹fish[4]=(fish[3]-1)*4/5D所看到的鱼数
⏹fish[5]=(fish[4]-1)*4/5E所看到的鱼数
⏹写成一般式
fish[i]=(fish[i-1]–1)*4/5
i=2,3,…,5
⏹这个公式可用于知A看到的鱼数去推算B看到的,再推算C看到的,…….。
现在要求的是A看到的,能否倒过来,先知E看到的再反推D看到的,……,直到A看到的。
为此将上式改写为:
fish[i-1]=fish[i]*5/4+1
i=5,4,…,2
分析上述公式
1.当i=5时,fish[5]表示E醒来所看到的鱼数,该数应满足被5整除后余1,即:
fish[5]%5==1
2.当i=5时,fish[i-1]表示D醒来所看到的鱼数,这个数既要满足:
fish[4]=fish[5]*5/4+1
又要满足
fish[4]%5==1
显然,fish[4]不能不是整数,这个结论同样可以用至fish[3],fish[2]和fish[1]
3.按题意要求5人合伙捕到的最少鱼数,可以从小往大枚举,可以先让E所看到的鱼数最少为6条,即fish[5]初始化为6来试,之后每次增加5再试,直至递推到fish[1]得整数且除以5之后的余数为1。
//预编译命令
intmain()//主函数
intfish[6]={1,1,1,1,1,1};
//整型数组,记录每人醒来后看到的鱼数
inti=0;
do
fish[5]=fish[5]+5;
//让E看到的鱼数增5。
for(i=4;
i>
=1;
i--)
if(fish[i+1]%4!
=0)
break;
//跳出for循环
else
fish[i]=fish[i+1]*5/4+1;
//计算第i人看到的鱼数
}while(i>
=1);
//当i>
=1继续做do循环
//输出计算结果
printf(“%d\n”,fish[i]);
递归
一.汉诺(Hanoi)塔问题
故事:
相传在古代印度的Bramah庙中,有位僧人整天把三根柱子上的金盘倒来倒去,原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。
移动过程中恪守下述规则:
每次只允许移动一只盘,且大盘不得落在小盘上面。
有人会觉得这很简单,真的动手移盘就会发现,如以每秒移动一只盘子的话,按照上述规则将64只盘子从一个柱子移至另一个柱子上,所需时间约为5800亿年。
⏹思路上还是先从最简单的情况分析起,搬一搬看,慢慢理出思路。
1在A柱上只有一只盘子,假定盘号为1,这时只需将该盘从A搬至C,一次完成,记为
move1fromAtoC
2在A柱上有二只盘子,1为小盘,2为大盘。
1第
(1)步将1号盘从A移至B,这是为了让2号盘能移动;
2第
(2)步将2号盘从A移至C;
3第(3)步再将1号盘从B移至C;
这三步记为(演示):
move1fromAtoB;
move2fromAtoC;
move1formBtoC;
3.在A柱上有3只盘子,从小到大分别为1号,2号,3号
⏹第
(1)步将1号盘和2号盘视为一个整体;
先将二者作为整体从A移至B,给3号盘创造能够一次移至C的机会。
这一步记为move(2,A,C,B)
意思是将上面的2只盘子作为整体从A借助C移至B。
⏹第
(2)步将3号盘从A移至C,一次到位。
记为move3fromAtoC
⏹第(3)步处于B上的作为一个整体的2只盘子,再移至C。
这一步记为move(2,B,A,C)
意思是将2只盘子作为整体从B借助A移至C。
4、从题目的约束条件看,大盘上可以随便摞小盘,相反则不允许。
在将1号和2号盘当整体从A移至B的过程中move(2,A,C,B)实际上是分解为以下三步
第
(1).1步:
move1formAtoC;
第
(1).2步:
move2formAtoB;
第
(1).3步:
move1formCtoB;
经过以上步骤,将1号和2号盘作为整体从A移至B,为3号盘从A移至C创造了条件。
同样,3号盘一旦到了C,就要考虑如何实现将1号和2号盘当整体从B移至C的过程了。
实际上move(2,B,A,C)也要分解为三步:
第(3).1步:
move1formBtoA;
第(3).2步:
move2formBtoC;
第(3).3步:
5、看move(2,A,C,B)是说要将2只盘子从A搬至B,但没有C是不行的,因为第
(1).1步就要将1盘从A移到C,给2盘创造条件从A移至B,然后再把1盘从C移至B。
看到这里就能明白借助C的含义了。
因此,在构思搬移过程的参量时,要把3个柱子都用上。
6、定义搬移函数move(n,A,B,C),物理意义是将n只盘子从A经B搬到C
⏹move(n,A,B,C)分解为3步
1.move(n-1,A,C,B)理解为将上面的n-1只盘子作为一个整体从A经C移至B;
2.输出n:
AtoC,理解将n号盘从A移至C,是直接可解结点;
3.Move(n-1,B,A,C)理解为将上面的n-1只盘子作为一个整体从B经A移至C。
⏹这里显然是一种递归定义,当着解move(n-1,A,C,B)时又可想到,将其分解为3步:
⏹第1步:
将上面的n-2只盘子作为一个整体从A经B到C,move(n-2,A,B,C);
⏹第2步:
第n-1号盘子从A直接移至B,即n-1:
AtoB;
⏹第3步:
再将上面的n-2只盘子作为一个整体从C经A移至B,move(n-2,C,A,B);
intstep=1;
//整型全局变量,预置1,步数
//声明要用到的被调用函数
voidmove(int,char,char,char);
{//主程序开始
intn;
//整型变量,n为盘数,
printf("
请输入盘数n=“);
//提示信息
scanf(“%d”,&
n);
//输入正整数n
//输出提示信息
在3根柱子上移%d只盘的步骤为:
\n“);
move(n,'
'
b'
c'
);
//调用move函数
//主函数结束
}
//以下函数是被主程序调用的函数
//函数名:
move
//输入:
m,整型变量,表示盘子数目
//p,q,r为字符型变量,表示柱子标号
//返回值:
无
voidmove(intm,charp,charq,charr)
{//自定义函数体开始
if(m==1)//如果m为1,则为直接可解结点,
//直接可解结点,输出移盘信息
[%d]move1#from%dto%d\n”,step,p,r);
step++;
//步数加1
else//如果不为1,则要调用move(m-1)
move(m-1,p,r,q);
//递归调用move(m-1)
//直接可解结点,输出移盘信息
[%d]move%d#from%dto%d\n”,step,m,p,r);
//步数加1
move(m-1,q,p,r);
}//自定义函数体结束
习题:
已知Cmn表示从m个元素中取n个的组合数,又知
Cmn=Cm-1n+Cm-1n-1
1,m=n
Cmn=
m,n=1
写出递归程序求解组合问题。
//计算C(m,n),即从m个数中取n个数的组合数
intCmn(intm,intn)
if(m<
0||n<
0||m<
n)
return0;
if(m==n)//C(m,m)=1
return1;
if(n==1)//C(m,1)=m
returnm;
//C(m,n)=C(m-1,n)+C(m-1,n-1)
returnCmn(m-1,n)+Cmn(m-1,n-1);
intmain()//主函数开始
//测试一些结果
C(6,0)=%d\n“,Cmn(6,0));
C(6,1)=%d\n“,Cmn(6,1));
C(6,2)=%d\n“,Cmn(6,3));
C(6,6)=%d\n“,Cmn(6,6));
}//主函数结束
二.二分查找
//递归实现二分法在有序数组a中查找m,返回m的下标
//没找到返回-1
intbisearch(intary[],inti,intj,intm)
if(i>
j)//没找到
return-1;
if(ary[(i+j)/2]==m)//找到
return(i+j)/2;
elseif(ary[(i+j)/2]>
m)//找左半边
returnbisearch(ary,i,(i+j)/2-1,m);
else//找右半边
returnbisearch(ary,(i+j)/2+1,j,m);
三.快速排序
快速排序的思路
1.将待排序的数据放入数组a中,下标从z到y;
2.取a[z]放变量k中,通过分区处理,为k选择应该排定的位置。
这时要将比k大的数放右边,比k小的数放左边。
当k到达最终位置后,由k划分左右两个集合。
然后再用同样的思路处理左集合与右集合。
3.令sort(z,y)为将数组元素从下标为z到下标为y的y–z+1个元素从小到大排序。
分区处理
1、让k=a[z]
2、将k放在a[m]
3、使a[z],a[z+1],…,a[m-1]<
=a[m