算法的基本工具和优化技巧

算法的基本工具和优化技巧第1页，课件共45页，创作于2023年2月循环与递归将大量重复处理大量数据的步骤抽象成循环或递归模式，设计出可以针对不同规模解决问题的算法。第2页，课件共45页，创作于2023年2月循环设计中要注意算法的效率循环体的特点是：“以不变应万变”。所谓“不变”是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。第3页，课件共45页，创作于2023年2月【例1】求1/1!-1/3!+1/5!-1/7!+…+（-1）n+1/(2n-1)!

数学模型2：Sn=Sn-1+An；

An=(-1)*An-1*((2*n-2)*(2*n-1))main(){inti,n,sign;floats,t=1;cin>>n;s=1；for(i=2;i<=n;i++){t=(-1)*t*(2*i-2)*(2*i-1)};s=s+1/t;}cout<<“Sum=”<<s;}第4页，课件共45页，创作于2023年2月“自顶向下”的设计方法【例2】编算法找出1000以内所有完数例如，28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28第5页，课件共45页，创作于2023年2月1）顶层算法

for(i=2;i<=n;i++){判断i是否是完数；是完数则按格式输出;}

2）判断i是否是完数for(j=2;j<i;j++)

找i的因子，并累加如果累加值等于i，i是完数

第6页，课件共45页，创作于2023年2月3）进一步细化——判断i是否“完数”算法s=1for(j=2;j<i;j++)if(i%j=0)s=s+j;if（s==i）i是“完数”;

第7页，课件共45页，创作于2023年2月算法如下：main(){inti,k,j,s;for(i=1;i<=1000;i++){s=1;/*两个赋初值语句s=1for(j=2;j<i;j++)if(i%j)==0)s=s+j;if(i==s)cout<<s<<endl;}}

第8页，课件共45页，创作于2023年2月

在算法中，递归一词用于表示直接或间接的调用自身的算法。

特别的，用函数自身给出定义的函数被称之为递归函数。

第9页，课件共45页，创作于2023年2月天津城市建设学院什么是递归？

其实，我们在生活中经常运用递归的方式来思考问题，如参考下面这个例子：例1：第5个人的年龄比第4个人的年龄大2岁，第4个人的年龄比第3个人的年龄大2岁，第3个人的年龄比第2个人的年龄大2岁，第2个人的年龄比第1个人的年龄大2岁，第1个的年龄10岁。第5个人的年该该是多少呢？第10页，课件共45页，创作于2023年2月天津城市建设学院

著名的意大利数学家斐波那契(Fibonacci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子?

(当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)我们需要研究表中的规律，找出一般的方法，去解决这个问题。第11页，课件共45页，创作于2023年2月天津城市建设学院“兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N)，我们有：

这是因为每月的大兔子数目一定等于上月的兔子总数，而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。第12页，课件共45页，创作于2023年2月递归设计要点直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。递归是一种比迭代循环更强、更好用的循环结构。只需要找出递归关系和最小问题的解。递归方法只需少量的步骤就可描述出解题过程所需要的多次重复计算，大大地减少了算法的代码量。第13页，课件共45页，创作于2023年2月递归的关键在于找出递归方程式和递归终止条件。递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。第14页，课件共45页，创作于2023年2月递归算法解题通常有三个步骤：1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。3）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。常见的递归算法阶乘Fibonacci数列著名的汉诺塔问题二叉树的3种遍历第15页，课件共45页，创作于2023年2月天津城市建设学院故事： 相传在古代印度的Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为5800亿年。第16页，课件共45页，创作于2023年2月Hanoi塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。第17页，课件共45页，创作于2023年2月在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n＞1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。Hanoi塔问题

voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}第18页，课件共45页，创作于2023年2月【例】任给十进制的正整数，请从低位到高位逐位输出各位数字。

循环算法设计：f1(n){while(n>=10){cout<<n%10;n=n/10;}cout<<n;}第19页，课件共45页，创作于2023年2月递归算法设计：1）同上，算法从低位到高位逐位求出各位数字并输出，求个位数字的算式为n%10，下一步则是递归地求n/10的个位数字。2）当n<10时，n为一位数停止递归。递归算法如下：f2(n){if(n<10)cout<<n;else{cout<<n%10;f(n/10);}}第20页，课件共45页，创作于2023年2月【例】任给十进制的正整数，请从高位到低位逐位输出各位数字。循环算法设计：本题目中要求“从高位到低位”逐位输出各位数字，但由于我们并不知道正整数的位数，算法还是“从低位到高位”逐位求出各位数字比较方便。这样就不能边计算边输出，而需要用数组保存计算的结果，最后倒着输出。第21页，课件共45页，创作于2023年2月循环算法如下：f3(n){intj,i=0,a[16];while(n>=10){a[i]=n%10;i=i+1;n=n/10;}a[i]=n;for(j=i;j>=0;j--)cout<<n;}第22页，课件共45页，创作于2023年2月递归算法设计：

与f2不同，递归算法是先递归地求n/10的个位数字，然后再求个位数字n的个位数字并输出。这样输出操作是在回溯时完成的。递归停止条件与f2相同为n<10。递归算法如下：f4(n){if(n<10)cout<<n;else{f(n/10);cout<<n%10;}}第23页，课件共45页，创作于2023年2月例4排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。分析：n=1输出：r1n=2输出：r1r2r2r1n=3输出：r1r2r3r1r3r2r2r1r3r2r3r1r3r1r2r3r2r1分析r3，全部排列可以分为三类：（1）r1类：r1后跟r2r3的全排列（2）r2类：r2后跟r1r3的全排列（3）r3类：r3后跟r1r2的全排列将（1）中r1r2互换位置，得到（2）；将（1）中r1r3互换位置，得到（3）；它说明可以用循环的方式重复执行交换位置，后面跟随剩余序列的所有排列，对剩余序列再使用这个方法，这就是递归调用，当后跟的元素没有时就得到递归的边界。第24页，课件共45页，创作于2023年2月递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。第25页，课件共45页，创作于2023年2月

由于递归算法的实现包括递归和回溯两步，当问题需要“后进先出”的操作时，还是用递归算法更有效。如数据结构课程中二叉树的各种遍历、图的深度优先等算法都是如此。所以不能仅仅从效率上评价两个控制重复机制的好坏。事实上，无论把递归作为一种算法的策略，还是一种实现机制，对我们设计算法都有很好的帮助。第26页，课件共45页，创作于2023年2月例7判断s字符串是否为回文的递归函数intishuiwen(char*s,intn){ if(n==0||n==1)return1; else {if(*s==*(s+n-1))ishuiwen(s+1,n-2); elsereturn0; }}第27页，课件共45页，创作于2023年2月天津城市建设学院

递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，充分发挥计算机长于重复处理的特点，现举一例递推第28页，课件共45页，创作于2023年2月天津城市建设学院猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？a9=2a8=(a9+1)*2第29页，课件共45页，创作于2023年2月天津城市建设学院作业：1、运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。第30页，课件共45页，创作于2023年2月天津城市建设学院作业：2、国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？第31页，课件共45页，创作于2023年2月天津城市建设学院作业：3、出售金鱼。第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？第32页，课件共45页，创作于2023年2月天津城市建设学院作业：4、某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？第33页，课件共45页，创作于2023年2月天津城市建设学院作业：5、小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少钱页？第34页，课件共45页，创作于2023年2月天津城市建设学院作业：6、日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？第35页，课件共45页，创作于2023年2月科目及格学生学号语文1，9，6，8，4，3，7代数5，2，9，1，3，7外语8，1，6，7，3，5，4，9

枚举法：

一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。第36页，课件共45页，创作于2023年2月求X，使X2为一个各位数字互不相同的九位数。（枚举法）分析：只能用枚举法尝试完成此题。由X2为一个九位数，估算X应在10000——32000之间。1）

用一个10个元素的状态数组p，记录数字0——9在X2中出现的情况。数组元素都赋初值为0，表示数字0——9没有被使用过。

2）

对尝试的每一个数x，求x*x,并取其各位数字，数字作为数组的下标，若对应元素为0，则该数字第一次出现，将对应的元素赋为1，表示该数字已出现一次。否则，若对应元素为1，则说明有重复数字，结束这次尝试。

3）容易理解当状态数组p中有9个元素为1时，就找到了问题的解。但这样判定有解，需要扫描一遍数组p。为避免这个步骤，设置一个计数器k，在取x*x各个位数字的过程中记录不同的数字的个数，当k=9时就找到了问题的解。第37页，课件共45页，创作于2023年2月main(){longx,y1,y2;intp[10],2,i,t,k,num=0;for(x=10000;x<32000;x++){for(i=0;i<=9;i=i+1)p[i]=0;y1=x*x;y2=y1;k=0;for(i=1;i<=9；i++){t=y2%10;y2=y2/10;if(p[t]==0){k=k+1;p[t]=1;}elsebreak;}if(k==9){num=num+1;cout<<“No.”<<num<<“：=”<<x<<“n2=”<<y1);}}}第38页，课件共45页，创作于2023年2月警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。审问中

a说：“我不是小偷。”

b说：“c是小偷。”

c说：“小偷肯定是d。”

d说：“c在冤枉人。”

现在已经知道四个人中三人说的是真话，一人说的是假话，

问到底谁是小偷？

信息数字化第39页，课件共45页，创作于2023年2月算法设计：用变量x存放小偷的编号，则x的取值范围从1取到4，就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成：

a说的话：x<>1b说的话：x=3c说的话：x=4d说的话：x<>4或not(x=4)

注意:在x的枚举过程中，当这四个逻辑式的值相加等于3时，即表示“四个人中三人说的是真话，一人说的是假话”。

第40页，课件共45页，创作于2023年2月算法如下：main(){intx;for(x=1;x<=4;x++)if((x<>1)+(x==3)+(x==4)+(x<>4)==3)cout<<chr(64+x)<<“isathief.”;

}运行结果：

cisathief.第41页，课件共45页，创作于2023年2月三位老师对某次数学竞赛进行了预测。他们的预测如下：甲说：学生A得第一名，学生B得第三名。

乙说：学生C得第一名，学生D得第四名。

丙说：学生D得第二名，学生A得第三名。

竞赛结果表明，他们都说对了一半，说错了一半，并且无并列名次，试编程输出A、B、C、D各自的名次。

第42页，课件共45页，创作于2023年2月算法设计：

1）用a，b，c，d代表四个同学，其存储的值代表他们的名次。设置第一层计数循环a的范围从1到4；设置第二层计数循环b的范围从1到4