实用算法的分析与程序设计――递推法(倒推法) - 梦里水乡的专栏 - 博客频道 - CSDN.NET
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];
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]);
Read full article from 实用算法的分析与程序设计――递推法(倒推法) - 梦里水乡的专栏 - 博客频道 - CSDN.NET
倒推法就是在不知初始值的情况下,经某种递推关系而获知问题的解或目标,再倒过来,推知它的初始条件。因为这类问题的运算过程是一一映射的,故可分析得其递推公式,然后再从这个解或目标出发,采用倒推手段,一步步地倒推到这个问题的初始陈述。
贮油点 一辆重型卡车欲穿过1000公里的沙漠,卡车耗油为1升/公里,卡车总载油能力为500公升,显然卡车装一次油是过不了沙漠的,因此四级必须设法在沿途建立几个贮油点,使卡车能顺利穿越沙漠,试问司机如何建立这些贮油点?每一贮油点应存多少汽油,才能使卡车以消耗最少汽油的代价通过沙漠?
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]);
}
}
recursion(distance, oil, 0, 0.0);
http://blog.sina.com.cn/s/blog_4ca34d0501000b66.htmlRead full article from 实用算法的分析与程序设计――递推法(倒推法) - 梦里水乡的专栏 - 博客频道 - CSDN.NET