实用算法 ( 基础算法 - 递推法 -01)
有一类试题,每相邻两项数之间的变化有一定的规律性,我们可将这种规律归纳成如下
简捷的递推关系式:
Fn=g(Fn-1)
这就在数的序列中, 建立起后项和前项之间的关系, 然后从初始条件 ( 或最终结果 ) 入手,
一步步地按递推关系递推,直至求出最终结果 ( 或初始值 ) 。很多程序就是按这样的方法逐步
求解的。 如果对一个试题, 我们要是能找到后一项与前一项的关系并清楚其起始条件 ( 最终结
果) ,问题就好解决, 让计算机一步步算就是了, 让高速的计算机做这种重复运算, 可真正起
到“物尽其用”的效果。
递推分倒推法和顺推法两种形式。一般分析思路:
if 求解条件 F1
then begin{ 倒推 }
由题意 ( 或递推关系 ) 确定最终结果 Fa;
求出倒推关系式 Fi-1=g'(Fi);
i=n;{ 从最终结果 Fn 出发进行倒推 }
while 当前结果 Fi 非初始值 F1 do 由 Fi-1=g(F1) 倒推前项;
输出倒推结果 F1 和倒推过程;
end {then}
else begin{ 顺推 }
由题意 ( 或顺推关系 ) 确定初始值 F1( 边界条件 ) ;
求出顺推关系式 F1=g(Fi-1);
i=1;{ 由边界条件 F1 出发进行顺推 }
while 当前结果 Fi 非最终结果 Fn do 由 Fi=g(Fi-1) 顺推后项;
输出顺推结果 Fn 和顺推过程;
end; {else}
一、倒推法
所谓倒推法,就是在不知初始值的情况下,经某种递推关系而获知问题的解或目标,再
倒推过来,推知它的初始条件。因为这类问题的运算过程是一一映射的,故可分析得其递推
公式。然后再从这个解或目标出发,采用倒推手段,一步步地倒推到这个问题的初始陈述。
下面举例说明。
[ 例 1] 贮油点
一辆重型卡车欲穿过 1000 公里的沙漠,卡车耗油为 1 升/ 公里,卡车总载油能力为 500
公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点,使卡车能
顺利穿越沙漠,试问司机如何建立这些储油点?每一储油点应存多少油,才能使卡车以消耗
最少油的代价通过沙漠?
评论0
最新资源