[Rom@NS]

Сижу уже неделю, и не как не могу осилить! Даже мыслей никаких нет! А ведь скоро мне ее сдвать! Прошу-ПОМОГИТЕ!

задача:

Есть дорога длинной 500км, в общем случае. В начале дороги находится АЗС. Есть автомобиль с баком в 100л и 2 канистры по 25л. Автомобиль на 1 км жрет 1л литр бензина. Требуется определить минимальное количество бензина, которое потребуется что бы проехать этот путь. А также вывести указание о том, как надо двигаться и где оставлять бензин.
Подразумевается что в любой точке пути можно оставить любое количество бензина.

samara@box.vsi.ru

[Rom@NS]

У меня есть кое-какие варианты решения этой задачи.
Предлогается решать методом с конца
Ну, типа в отметке 350км, что бы достичь конца дороги требуется 150л, в отметке 300км требуется 300л.(пощитано руками). Так конечно можно прочситать все!Но это же можно треснуть! Надо найти алгорим который бы это мог делать!

ЗЫ может теперь кто поможет...

[Decoding]

Есть дорога длинной 500км, в общем случае. В начале дороги находится АЗС. Есть автомобиль с баком в 100л и 2 канистры по 25л. Автомобиль на 1 км жрет 1л литр бензина. Требуется определить минимальное количество бензина, которое потребуется что бы проехать этот путь.

1) При чем тут АЗС (на что в твоей задаче это влияет)?

2) Минимальное количество бензина, которое потребуется что бы проехать этот путь = длинне дороги (из рассчета 1 литр на километр, если конечно на дороге нет развилок и объездных путей).

Ну, типа в отметке 350км, что бы достичь конца дороги требуется 150л, в отметке 300км требуется 300л.(пощитано руками).

А не 200 ли литров требуется в отметке 300км? (из рассчета 1 литр на километр)

Так конечно можно прочситать все!Но это же можно треснуть! Надо найти алгорим который бы это мог делать!

Если исходить из рассчета 1 литр на километр, то
длинна дороги - текущая позиция = кол-во бензина, которое потребуется что бы проехать остаток пути...

P.S.
А вообще, из всего, написанного тобой ранее не очень понятно, чего в конечном итоге ты хочешь добиться... Зачем тебе это нужно?

[Rom@NS]

Объясняю на пальца!

в начале дорога заправка. Начало дороги будем считать нулевым километром. Машине надо добраться до отметки в 500 км. Естественно за раз этого сделать не возможно. С заправки за раз я могу увести не более 150 литров бензина. Но при этом в любой точке дороги я могу оставить любое количество бензина.

Например, пусть мне надо проехать 200км, тогда надо поступить следующим образом:

|_________50км____________________________|
0км............................................... ................200км

1)надо из отметки 0км взять 150 литров бензина
2)проехать 50км и оставить на отметке 50км 50литров бензина
3)теперь вернуться обратно на 0км(на заправку)
{к этому моменту будет израсходовано 100 литров бензина}
4)берем снова в отмеке 0км 150 литров
5)доезжаем до отметки 50км и заливаем ту канистру которую там оставили
{итого уже сожгли 150}
{при этом на борту имеем 150л, как раз необходимые для того что бы доехать до отметки в 200км. Итого 300л}

А теперь представь что дорога в 500км!!!Вот подобными телодвижениями надо проехать всю дорогу, тоская из одной точки бензин в другую

Один из вариантов, что в точке 300км надо иметь 300л бензина, тогда доехав до точки 350 будем иметь на борту 150 литров, совершаем последний рывок в 150 км и вот он финиш!

[Rom@NS]

Сообщение от Decoding

1)P.S.
А вообще, из всего, написанного тобой ранее не очень понятно, чего в конечном итоге ты хочешь добиться... Зачем тебе это нужно?

Хочу посчиать минимальное количество бензина, которое потребуется что бы проехать эту дорогу таким макаром!
А надо мне это для тго, что бы зачет в конце декабря получить! Задали мне такую вот прогу по теме Динамическое программирование!

[Rom@NS]

Есть следующий выриант решения этой задачи на С++, но в нем где то есть небольшая ошибка, а так я не знаю С++, то естественно этой ошибки не могу найти.
Может кто переведет мне этот код на Delphi.... а заодно и ошибку увидит...

B — бак
K — канистра
L — расстояние
Решать начал с конца т.е от 350 до 500 км мы можем проехать без проблем (500 — бак -две_канистры) =500-150=350.
Теперь нам необходимо заполнить от 350 до 0.
Заполнение такое: считаем максимальное расстояние которое мы можем проехать на двух канистрах и баке, что то оставить, и вернуться. ras=(B+2*K)/2-1; т.е 74 км.
Потом считаем сколько бензина можем оставить в j точке, при том, что надо ещё и вернуться (ost=B+2*K-2*j) оставить больше двух канистр не можем, а меньше можем.
Далее считаем количесвто рейсов необходимое чтобы перевезти бензин в j точку (reis=(pust[i+j].liter-(B-j)-1)/ost+1)
здесь значит так: (литров_до_конца — в_баке_now-1)/ost+1
Рассчитываем количество бензина необходимое из данной точки чтобы доехать до конца (ben=pust[i+j].liter+reis*j+(reis-1)*j)

А вот реализация этого алгоритма:



#define L 500 //расстояние которое необходимо проехать
#define K 25 //канистры
#define B 100 //бак

typedef struct _Pust_struct
{
int next; //следующий километр
int liter; //сколько литров до конца
} Pust_struct;

void do_it(Pust_struct* pust)//процедура подсчёта
{

int ost,reis,ben;

for(int i=L-1;i>L-B-2*K-1;i--) //заполняем с конца или от 500 до 350
{
pust[i].liter=L-i;
pust[i].next=L;
}

int ras=(B+2*K)/2-1; //считаем максимальное расстояние которое можем проехать, что то оставить, и вернуться.

for(int i=L-B-2*K-1;i>=0;i--) //начинаем заполнять
{
pust[i].liter=0xFFFFFFF; //очень большое число для сравнения
pust[i].next=i;
for(int j=1;j<ras;j++)
{
ost=B+2*K-2*j; //считаем сколько можем оставить при условии того, что надо ещё и вернуться

if (ost>2*K) ost=2*K; //округляем

reis=(pust[i+j].liter-(B-j)-1)/ost+1; //количество рейсов необходимое что бы перевезти бензин
//из i-ой точки в j-ую

ben=pust[i+j].liter+reis*j+(reis-1)*j;//количество топлива необходимое, что бы доехать
//до конца из i+j точки

if (pust[i].liter>ben)//выбираем оптимальное количество топлива
{
pust[i].next=i+j; //следующая точка в которую мы можем попасть из i-ой
pust[i].liter=ben;//количество бензина что бы доехать до конца
}
}
}
}

int main()
{
int i=0;
Pust_struct p[L]; //массив

do_it(p);//выполняем все вычесления
//вывод всего
//for (i=0;i<L;i++)printf("point= %d\t liter= %d\t next= %d\t\n",i,p[i].liter,p[i].next);

//вывод решения
int temp=p[0].next;
printf("point= %d\t liter= %d\t next= %d\t\n",0,p[0].liter,p[0].next);

for(i=0;i<L;i++)
{
if (i == temp)
{
printf("point= %d\t liter= %d\t next= %d\t\n",i,p[i].liter,p[i].next);
temp=p[i].next;
}
}


return 0;
}

[Rom@NS]

Нашлись добрые люди, которые помогли мне с решением этой задачей! Жаль только, что не на этом форуме!

Если Кому интересно, то могу выложить исходники!