递归与回溯.ppt

递归与回溯
安庆十四中胡锋
递归部分
问题一中位数
【问题描叙】
输入n个整数求出它们的中位数。(提示:如果是偶数个,中位数为中间两个数之和的平均数,如果是奇数个,中位数为正中间的数。)
【输入样例】
4
2 4 8 1
【输出样例】
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=8
8=2*4
8=2*2*2
【问题分析】
一个自然数分解之后形成新的自然数之积,但是其中的各个分解之后的自然数也还是一样的处理,还是要按照原来的方式分解,所以我们可以称这样的操作叫做递归,那么一个自然数如何操作呢?
从2到这个数n div 2去试,同时还要注意本身这个数自己输出。
【关键点】递归
问题四数的计数
【问题描叙】
数的计数(20分)
[问题描述]
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n≤1000), 然后对此自然数按照如下方法进行处理:
;
,但该自然数不能超过原数的一半;
,继续按此规则进行处理,直到不能再加自然数为止。