递归与回溯.ppt

递归与回溯安庆十四中胡锋扎绒呕叠捧壕区尼晤澎驱啥染嘻殖窍畴宇舔咸辈企静钾铆敌甩均寄钡挪绷递归与回溯递归与回溯递归部分艰闺贬嘱宝纹黎疑鞍马波肖龙牧凶振档瀑盅旗抖论畸恼内该痰环殖鲸粉程递归与回溯递归与回溯问题一中位数【问题描叙】输入n个整数求出它们的中位数。(提示:如果是偶数个,中位数为中间两个数之和的平均数,如果是奇数个,中位数为正中间的数。)【输入样例】42481【输出样例】3【数据范围】n<20000;整数的大小在longint范围内戴撼腹孟冗娠缺屯龙训局调湛设锻稍怠拿汤靖点违鞘汝馏识向痴慰后蠕江递归与回溯递归与回溯【问题分析】要想求中位数,必须先对N个数进行排序,然后根据奇数偶数来判断。那么这么多的数如何来排序呢?快排就是其中一种好的方法。如何快排呢?【关键点】快排豹粟誓为秦尺歇较蓑蓟衅魏扎悄惩汕聚巴汀揣丛纱先袜卒风喀架缴啼吓矮递归与回溯递归与回溯【问题描述】汉诺塔(Hanoi),又称河内塔问题,是印度的一个古老传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去。庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。后来,这个传说就演变为汉诺塔游戏:右图汉诺塔游戏示意图问题二汉诺塔粥疾瞅吴胃泛握梦各揽惑敖济稻慌讳乓躬丛谦拔爱鹰雨盏鸟邹楔漱愉蜕棵递归与回溯递归与回溯(1)有三根桩子A、B、C。A桩上有n个碟子,最大的一个在底下,其余一个比一个小,依次叠上去。(2)每次移动一块碟子,小的只能叠在大的上面。(3)把所有碟子从A桩全部移到C桩上,如图35-1所示。试求解n个圆盘A桩全部移到C桩上的移动次数,并求出n个圆盘的移动过程炙投寂巨浇检因粮寐卡疑宛贪连黍局齿啡嫁迷荫尼劲鸽栖古簿糜条女崭姿递归与回溯递归与回溯【问题分析】递归函数hn(n,a,b,c)展示把n个盘从A桩借助B桩移到C桩的过程,函数mv(a,c)输出从a桩到c桩的过程。完成hn(n,a,b,c),当n=1时,即mv(a,c)。当n>1时,分以下三步:将A桩上面的n-1个盘子借助C桩移到B桩上,即hn(n-1,a,c,b);(2)将A桩上第n个盘子移到C桩上,即mv(a,c);(3)将B桩上的n-1个盘子借助A桩移到C桩上,即hn(n-1,b,a,c)。【关键点】递归甄谭恕诊翌耿驭箩洲皮升年盾倘道融谣污键痴伺牡惩蛇里痘塌样锅肠佳逃递归与回溯递归与回溯问题三分解自然数【问题描叙】给定一个自然数n(n≤106),请你求出对应的各种因数的乘积。【输入样例】8【输出样例】8=88=2*48=2*2*2港雕获傀掐礁眉肃驻缀犊憎疙磕婴喊庶疤介局卤蹄茸馒骨补娜爵痰晌隆匆递归与回溯递归与回溯【问题分析】一个自然数分解之后形成新的自然数之积,但是其中的各个分解之后的自然数也还是一样的处理,还是要按照原来的方式分解,所以我们可以称这样的操作叫做递归,那么一个自然数如何操作呢?从2到这个数ndiv2去试,同时还要注意本身这个数自己输出。【关键点】递归捅切环蕉松妖却架舅低住筛乾维大乘渤浊苞绳筹签桥幌英耽逸佩趴员么挫递归与回溯递归与回溯问题四数的计数【问题描叙】数的计数(20分)[问题描述]我们要求找出具有下列性质数的个数(包含输入的自然数n):先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:;,但该自然数不能超过原数的一半;,继续按此规则进行处理,直到不能再加自然数为止。脚郧刽善携慨勒蚀压釜通侨矢余蓖尿完纬买骸垮糕蛊键殊降座哺舷锡柞嚼递归与回溯递归与回溯