论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

实用算法(基础算法-递推法-01)

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:45:40

    有一类试题,每相邻两项数之间的变化有一定的规律性,我们可将这种规律归纳成如下简捷的递推关系式:
    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公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点,使卡车能顺利穿越沙漠,试问司机如何建立这些储油点?每一储油点应存多少油,才能使卡车以消耗最少油的代价通过沙漠?
算法分析:
    编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。
        No.        Distance(k.m.)        oil(litre)
        1                X X                X X
        2                X X                X X
        3                X X                X X
       ...              .....              ......
    设dis[i]   为第i个贮油点至终点(i=0)的距离;
      oil[i]   为第i个贮油点的存贮油量;
    我们可以用倒推法来解决这个问题。从终点向始点倒推,逐一求出每个贮油点的位置及存油量。
下图表示倒推时的返回点:


    从贮油点i向贮油点i+1倒推的策略是,卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗尽500公升汽油,而每次从i+1出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下使i点贮足i*500分升汽油的要求(0<=i<=n-1)。具体地讲,第一个贮油点i=1应距终点i=0处500km且在该处贮藏500公升汽油,这样才能保证卡车能由i=1处到达终点i=0处,这就是说
    dis[1]=500        oil[1]=500;
    为了在i=1处贮藏500公升汽油,卡车至少从i=2处开两趟满载油的车至i=1处。所以i=2处至少贮有2*500公升汽油,即oil[2]=500*2=1000。另外,再加上从i=1返回至i=2处的一趟空载,合计往返3次。三次往返路程的耗油量按最省要求只能为500公升。即d12=500/3km
        dis[2]=dis[1]+d12=dis[1]+500/3


    为了在i=2处贮存1000公升汽油,卡车至少从i=3处开三趟满载油的车至i=2处。报以i=3处至少贮有3*500公升汽油,即oil[3]=500*3=1500。加上i=2至i=3处的二趟返程空车,合计5次。路途耗油量也应为500公升,即d23=500/5,
        dis[3]=dis[2]+d23=dis[2]+500/5;


    依此类推,为了在i=k处贮藏k*500公升汽油,卡车至少从i=k+1处开k趟满载车至i=k处,即
    oil[k+1]=[k+1]*500=oil[k]+500,加上从i=k处返回i=k+1的k-1趟返程空间,合计2k-1次。这2k-1次总耗油量按最省要求为500公升,即
    dk,k+1=500/(2k-1)
        dis[k+1]=dis[k]+dk,k+1
                =dis[k]+500/(2k-1);


    最后,i=n至始点的距离为1000-dis[n],oil[n]=500*n。为了在i=n处取得n*500公升汽油,卡车至少从始点开n+1次满载车至i=n,加上从i=n返回始点的n趟返程空车,合计2n+1次,2n+1趟的总耗油量应正好为(1000-dis[n])*(2n+1),即始点藏油为oil[n]+(1000-dis[n])*(2n+1)。
下面为程序代码:
program oil_lib;
var
k:integer;  {贮油点位置序号}
d,            {累计终点至当前贮油点的距离}
d1:real;      {i=n至始点的距离}
oil,dis:array[1..10] of real;
i:integer;    {辅助变量}
begin
    writeln('NO.','distance(k.m)':30,'oil(1.)':80);
    k:=1;
    d:=500;    { 从i=1处开始向始点倒推}
    dis[1]:=500;
    oil[1]:=500;
    repeat
        k:=k+1;
        d:=d+500/(2*k-1);
        dis[k]:=d;
        oil[k]:=oil[k-1]+500;
    until d>=1000;
   
    dis[k]:=1000;        {置始点至终点的距离值}
    d1:=1000-dis[k-1];    {求i=n处至始点的距离}
    oil[k]:=d1*(2*k+1)+oil[k-1];    {求始点藏油量}
    for i:=0 to k do        {由始点开始,逐一打印始点至当前贮油点的距离和藏油量}
        writeln(i,1000-dis[k-i]:30,oil[k-i]:80);
end. {main}

转换为C语言程序如下:
#include<stdio.h>
void main()
{
    int k;            /*贮油点位置序号*/
    float d,d1;       /*d:累计终点至当前贮油点的距离,d1:i=n至始点的距离*/
    float oil[10],dis[10];
    int i;
    printf("NO. distance(k.m.)\toil(l.)\n");
    k=1;
    d=500;        /*从i=1处开始向始点倒推*/
    dis[1]=500;
    oil[1]=500;
    do{
        k=k+1;
        d=d+500/(2*k-1);
        dis[k]=d;
        oil[k]=oil[k-1]+500;
    }while(!(d>=1000));
    dis[k]=1000;        /*置始点至终点的距离值*/
    d1=1000-dis[k-1];    /*求i=n处至始点的距离*/
    oil[k]=d1*(2*k+1)+oil[k-1];    /*求始点藏油量*/
    for(i=0;i<k;i++)       /*由始点开始逐一打印始点至当前贮油点的距离和藏油量*/
        printf("%d\t%f\t%f\t\n",i,1000-dis[k-i],oil[k-i]);
}
上一篇:{应用}链表的运算(05) 人气:6293
下一篇:{应用}实用算法(基础算法-递推法-02) 人气:5411
视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程