主题:[讨论]递归问题:过沙漠
木贝心szh
[专家分:0] 发布于 2007-03-09 17:10:00
希望一辆吉普车以最少的耗油跨越1000 km的沙漠。已知该车总装油量500升,耗油率为1升/ km,必须利用吉普车自己沿途建立临时加油站,逐步前进。问一共要多少油才能以最少的耗油越过沙漠?
这个问题一直找不到可解决的pascal程序,希望哪位好心人帮帮忙呀!
回复列表 (共11个回复)
沙发
knate [专家分:570] 发布于 2007-03-10 00:20:00
/* Note:Your choice is C IDE */
#include "stdio.h"
#define N 10002
main()
{
int t;/*循环次数*/
int k;
/*需要运载次数*/
float leave;/*到下一点需要的*/
float demand;/*当前需要*/
float temp;
printf("%d ",500);
for(t=0,leave=1;t<N;t++)
{
temp=(N*leave-1)/(N-2);
(int) k=temp;
if(temp>k)
k++;
demand=leave+(float)(2*k-1)/N;
/*printf("%g ",demand*500);*/
leave=demand;
}
printf("%g ",demand*500);
}
也可以用贪心算法来处理!
板凳
木贝心szh [专家分:0] 发布于 2007-03-12 20:13:00
谢谢先!我自个儿琢磨一下下。
[em3]
3 楼
木贝心szh [专家分:0] 发布于 2007-03-13 10:47:00
不好意思,我还是想不大明白,有没有更详细一点的解释呀?
[em8]
4 楼
knate [专家分:570] 发布于 2007-03-19 09:10:00
给我留个言吧!!
qq285289302
这里我不会发图片很难说得明白
这样理解吧,把相同的油分多次运到相同的距离,那么一点一点距离地把油运出去,比
每次距离较长地运油出去消耗的油(所走的距离要短!!)要少
5 楼
万里长城 [专家分:340] 发布于 2007-05-09 18:43:00
这道题不用编程。1000升就够了。
6 楼
万里长城 [专家分:340] 发布于 2007-05-09 18:44:00
我想:造好加油站,当场加油。
7 楼
liulibo133 [专家分:170] 发布于 2007-05-16 15:32:00
楼上的不懂不要乱说。这题记得我做过,用贪心是可以的。
8 楼
waglongjuanfeng [专家分:90] 发布于 2007-06-17 18:20:00
采用**逆推法**,具体代码十日内给
最后一点油不剩的到终点
9 楼
木贝心szh [专家分:0] 发布于 2007-06-19 08:56:00
跪求具体代码!
10 楼
我留心愿 [专家分:0] 发布于 2007-11-11 11:05:00
program oil_lib;
var
k;integer;
d,d1:real;
oil,dis:array[1..10] of real;
i:integer;
begin
writeln('No.',' distance(k,m)':30,'oil(l.)':80);
k:=1;
d:=500;
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];
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.
我来回复