递归和分治思想笔记_两点水

《递归和分治思想笔记_两点水》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、递归和分治思想笔记递归递归的定义：把一个直接调用自己或通过一系列的调用语句简介的调用自己的函数，称为递归函数斐波纳斯数列斐波那契数列指的是这样一个数列o,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368自然中的斐波那契数列注意：第0项是0,第1项是第一个1。这个数列从第三项开始，每一项都等于前两项之和。1.迭代实现Fibonacci代码：#includeintmain(){in

2、ti;inta[40];a[0]=0;a[l]=l；for(i=2;i<40;i++){a[i]=a[i-l]+a[i-2];}printf(H%dM,a[39]);return0;}2.递归实现Fibonacci代码：#includeintFib(inta)returna==O?O:l;}returnFib(a-l)+Fib(a-2);}intmain(){printf(”％d”,Fib(39));return0;逆序输出输入的字符串具体题目要求：将输入的任意长度的字符串反向输出，输入“#"为结束1.

3、STL函数实现逆序输出输入的字符串#include#includeusingnamespacestd;intmain()intcount=0;charval=,i,;〃随便给val—个字符，不要是”护stacks;while(val!=,#1)scanf(”％c蔦&val);s.push(val);count++;};s.popO;count-;while(count-){printf(”％c“,s・top());s・pop();}return0;}乙递归实现逆序输出输入的字符串#i

4、ncludevoidFib(){chara;scanf("%c",&a);if(a!='#'){Fib();}if(a!=*#•)〃这里是为了输入”护时不打印!{printf(H%cn,a);}}intmain(){Fib();return0;}分治思想分治思想就是把一个问题规模比较大且不易求解的时候，就可以考虑将问题分成几个小的模块一一解决！递归和分治的思想是分不开的!!汉诺塔汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚程柱子，在一根柱子上从下往上按照

5、大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。64T盘子思路：先可以这样想，从最后一步想起：1.先将前63个盘子从x移动到Y上，确保大盘子在下，小盘子在上2.再将最底下的第64个盘子移动到Z上3.然后再将Y上的63个盘子移动到Z上然后就想第一步和第三部怎样做，因为第二步可以直接把盘子移动过去第一步的做法：1.把前62个盘子从y移动到z上2.将第63个盘子从x移动到y上3.然后将62个盘子移动到y上第三步和第一

6、步也差不多！如此类推下去，就是递归的思想代码：#include伪算法:1.if(n==l)直接把一个盘子从x移动到zelse把n-1个盘子从x借助z移动到y把第n个盘子从x移动到z上把n-1个盘子从y借助x移动到z}voidhannuotafintn,charx,chary,charz){if(n==l){printf(n%c->%c',/x,z);}else{hannuota(n-l,x,z,y);printf("%c->%c',,x,z);hannuota(n・l,y,x,z);}}intmai

7、n(){charx='x,/y=,y,/z='z,;hannuota(64,x,y,z);return0;}八皇后问题（递归法）八皇后问题八皇后是一道很具典型性的题目。它的基本要求是这样的：在一个8*8的矩阵上面放置8个物体，一个矩阵点只允许放置一个物体，任意两个点不能在一行上，也不能在一列上，不能在一条左斜线上，当然也不能在一条右斜线上。代码：#includeintcount=0;intnotDanger(introw,intj,int(*chess)[8]){inti,k,flagl=O,flag2=0

8、#flag3=0,flag4=0/flag5=0;//判断列方向for(i=0;i<8;i++){if(*(*(chess+i)+j)!=0){flagl=1;break;}}//判断左上方for{i二row,k=j;i>=0&&k>=0;i-,k-){if(*(*(chess+i)+k)