首页  »   编程

适用算法的分析与程序设计——递推法(倒推法)

网友分享于:2015-04-28  浏览:0次
实用算法的分析与程序设计——递推法(倒推法)

倒推法就是在不知初始值的情况下,经某种递推关系而获知问题的解或目标,再倒过来,推知它的初始条件。因为这类问题的运算过程是一一映射的,故可分析得其递推公式,然后再从这个解或目标出发,采用倒推手段,一步步地倒推到这个问题的初始陈述。

贮油点 一辆重型卡车欲穿过1000公里的沙漠,卡车耗油为1升/公里,卡车总载油能力为500公升,显然卡车装一次油是过不了沙漠的,因此四级必须设法在沿途建立几个贮油点,使卡车能顺利穿越沙漠,试问司机如何建立这些贮油点?每一贮油点应存多少汽油,才能使卡车以消耗最少汽油的代价通过沙漠?

算法分析

这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述

代码

/*
 * =====================================================================================
 *
 *       Filename:  recursion.cc
 *
 *    Description:  贮油点,一辆重型卡车欲穿过1000公里的沙漠,卡车耗油为1升/
 *          公里,卡车总载油能力为500公升。司机设法在沿途设几个储油
 *             点,使卡车能顺利穿越沙漠,问司机如何建立贮油点?每一贮 
 *          油点应存多少汽油,才能使卡车以消耗最少汽油的代价通过?
 *
 *        Version:  1.0
 *        Created:  04/25/15 08:57:38
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  xiu 
 *   Organization:  
 *
 * =====================================================================================
 */

#include<iostream>
using namespace std;

const int N = 100;      //N为所设贮油点数
const float Distance = 1000;    //沙漠的总长度
const int capacity = 500;   //卡车的载油能力


//输出各贮油点的信息,距离distance是距终点的距离
void out(float *distance, float *oil, int cur)
{
    cout<<"输出各贮油点的信息,距离distance是距终点的距离"<<endl;
    cout << "NO\tdistance\toil\n";
    for (int i = 0; i < cur; i++) 
    {
        cout << i +
            1 << "\t" << distance[i] << "\t\t" << oil[i] << "\n";
    }
}

//递推求距离和贮油量
void recursion(float *distance, float *oil, int cur, float dis_sum)
{
    if ((dis_sum - Distance) >= 0.0001) 
    {
        out(distance, oil, cur);
        return;
    } 
    else 
    {
        oil[cur] = (cur+1) * capacity;
        distance[cur] = dis_sum + ((float) capacity) / (2 * cur + 1);
        recursion(distance, oil, cur + 1, distance[cur]);
    }
}

int main()
{
    float distance[N] = { 0 };
    float oil[N] = { 0 };
    recursion(distance, oil, 0, 0.0);
    return 0;
}

相关解决方案

最新解决方案