Форум по Delphi программированию

Delphi Sources



Вернуться   Форум по Delphi программированию > Все о Delphi > Разное
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Результаты опроса: На ваш взгляд это сложная задача?
Очень сложная 0 0%
Сложная 3 75.00%
Простая 0 0%
Очень простая 1 25.00%
Голосовавшие: 4. Вы еще не голосовали в этом опросе

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 05.11.2006, 15:48
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Вопрос Требуется помощь в написании проги!(динамическое программирование)

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

задача:

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

samara@box.vsi.ru
Ответить с цитированием
  #2  
Старый 06.11.2006, 23:29
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Лампочка Типа помоги себе сам... так понял?

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

ЗЫ может теперь кто поможет...
Ответить с цитированием
  #3  
Старый 07.11.2006, 01:55
Аватар для Decoding
Decoding Decoding вне форума
Местный
 
Регистрация: 03.06.2006
Адрес: Почту найдете на моем сайте
Сообщения: 576
Версия Delphi: D10.2
Репутация: 214
По умолчанию

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

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

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

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

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

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

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

P.S.
А вообще, из всего, написанного тобой ранее не очень понятно, чего в конечном итоге ты хочешь добиться... Зачем тебе это нужно?
Ответить с цитированием
  #4  
Старый 07.11.2006, 16:41
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Восклицание ???

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

в начале дорога заправка. Начало дороги будем считать нулевым километром. Машине надо добраться до отметки в 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 км и вот он финиш!

Ответить с цитированием
  #5  
Старый 07.11.2006, 16:50
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Злость

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

Хочу посчиать минимальное количество бензина, которое потребуется что бы проехать эту дорогу таким макаром!
А надо мне это для тго, что бы зачет в конце декабря получить! Задали мне такую вот прогу по теме Динамическое программирование!
Ответить с цитированием
  #6  
Старый 08.11.2006, 19:06
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Восклицание С++

Есть следующий выриант решения этой задачи на С++, но в нем где то есть небольшая ошибка, а так я не знаю С++, то естественно этой ошибки не могу найти.
Может кто переведет мне этот код на 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, 21.11.2006 в 17:46.
Ответить с цитированием
  #7  
Старый 10.11.2006, 16:33
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Радость

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

Если Кому интересно, то могу выложить исходники!
Ответить с цитированием
  #8  
Старый 10.11.2006, 18:08
Аватар для Decoding
Decoding Decoding вне форума
Местный
 
Регистрация: 03.06.2006
Адрес: Почту найдете на моем сайте
Сообщения: 576
Версия Delphi: D10.2
Репутация: 214
По умолчанию

Выложи. Любопытно взглянуть как это решается.
Ответить с цитированием
  #9  
Старый 10.11.2006, 22:09
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Лампочка be or not to be?

вот один вариант решения этой задачи! конечно не совсем уверен, что она решается именно так, но на следующей неделе будет точно ясно правильно или нет! Ребята, которые щас на курс старше меня, уже сдавали ее, так, что мне кажется - и у меня все получится! в понедельник или среду попробую показать ее своему преподу, если подтвердит, то я обязатьль напишу! Я исходник тока сегодня надыбал, завтра буду разбираться, как она работает!!! И если знать принцип то мне кажется, что не так все сложно! я сегодня уже глянул одним глазом, вроде похоже на true!

Листинг:


//Имеется пустыня длиной 500 км, автомобиль с баком на 100 л,
//который может перевезти до 2-х канистр по 25 л
//Расход бензина 1 л/км
//Необходимо проехать пустыню с наименьшими затратами топлива

unit upust;
interface
const S = 500;
bak=100;
konistri=25;

type tkm=record
next:integer;
liter:integer;
end;
tpust=array[0..S]of tkm;

procedure fill(var p:tpust);

implementation
procedure fill(var p:tpust);
var i,j,ras,reis,ben:integer;
begin
//Заполняем от 350 до 500
for i:=S downto S-bak-2*konistri do
begin
p[i].liter := S-i;
p[i].next := S;
end;

//Считаем макс. возможное расстояние кот. можно проехать, что-то оставить,
// и вернуться, но остаток горючего не равен нулю,
// т.е. минимальный остаток горючего = 1!
ras := (bak + 2*konistri -1) div 2;

//Заполнение
for i := S - bak-2*konistri -1 downto 0 do
begin
p[i].liter := maxint;
p[i].next:=i;
for j:=1 to ras do //Выбираем оптимальное расстояние до следующей точки
begin
//Сколько рейсов необх., чтобы перевезти бензин из i в j точку
reis:=(p[i+j].liter) div 50;
//кол-во топлива необх чтобы доехать из точки i+j до конца
//потраченный бензин-один рейс + неох кол-во в точке+ путь до точки +сколько надо добавить
// ben := 2*j*(reis-1)+j+p[i+j].liter+(p[i+j].liter mod 50);
// ben := 2*j*(reis-1)+j+(150-j)+(p[i+j].liter-p[i+j].liter mod 50);
ben := 2*j*(reis-1)+(150-2*j)*(reis-1)+j+(150-j);
if p[i].liter > ben
then
begin
p[i].next := i+j; //след точка в ко-ю мы можем попасть из i
p[i].liter := ben; //кол-во бензина чтобы доехать до конца
end;
end;
end;
end;//fill
end.



unit umain;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls,upust, Grids, Buttons;

type
TForm1 = class(TForm)
bobr: TButton;
sgmain: TStringGrid;
BitBtn1: TBitBtn;
procedure bobrClick(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure BitBtn1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
p:tpust;

implementation

{$R *.dfm}

procedure TForm1.bobrClick(Sender: TObject);
var i: integer;
begin
fill(p);
sgmain.RowCount:=502;

for i:=1 to S+1 do
begin
sgmain.Cells[0,i]:=inttostr(i-1);
sgmain.Cells[1,i]:=inttostr(p[i-1].liter);
sgmain.Cells[2,i]:=inttostr(p[i-1].next);
end;

end;

procedure TForm1.FormCreate(Sender: TObject);
begin
sgmain.Cells[0,0]:='Км';
sgmain.Cells[1,0]:='Литры до конца';
sgmain.Cells[2,0]:='Следующий км';
end;

//вывод решения
procedure TForm1.BitBtn1Click(Sender: TObject);
var i,nom, j: integer;
begin
fill(p);
nom:= p[0].next;
sgmain.RowCount:= 2;
sgmain.Cells[0, 1]:= inttostr(0);
sgmain.Cells[1, 1]:= inttostr(p[0].liter);
sgmain.Cells[2, 1]:= inttostr(p[0].next);
j:= 2;
for i:= 0 to S do
if i = nom then
begin
sgmain.Cells[0, j]:= inttostr(i);
sgmain.Cells[1, j]:= inttostr(p[i].liter);
sgmain.Cells[2, j]:= inttostr(p[i].next);
nom:= p[i].next;
sgmain.RowCount:= sgmain.RowCount + 1;
j:= j + 1;
end;

end;

end.



если есть какие притензии мылить сюда:
samara@box.vsi.ru

Последний раз редактировалось Rom@NS, 12.11.2006 в 15:01.
Ответить с цитированием
  #10  
Старый 10.11.2006, 22:13
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Вопрос

Буду благодарен любым замечанииям! Может кто найдет баги или ошибки! Хотелось бы, что бы не молчали! Пишите о своих замечаниях! Может у кого есть более эффективный алгоритм! Буду рад всем новым постам по этой теме!
Ответить с цитированием
  #11  
Старый 13.11.2006, 20:44
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Печаль Help!!!

Ан не тут то было! рано я радовался! сегодня показал ее преподу и он меня послал! сказал, что не верный ответ, и даже не стал смотреть исходники! так что где ошибка не знаю! И снова мне ТРЕБУЕТСЯ ВАША ПОМОЩЬ!!!

ЗЫ http://ega-math.narod.ru/Nquant/Puzzle.htm - ссылка для тех кому интересны подобные задачи!
Ответить с цитированием
  #12  
Старый 15.11.2006, 18:20
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Вопрос

И вот еще одни вариант... и снова не верный. Вроде как принцип такой, но вот ответ неверный! Узнать бы хотя бы сколько надо бензина, тогда можно было бы подогнать алгоритм под этот ответ!!! А так когда не знаешь к чему стремиться совсем не в жилу решать задачи подобного типа!

//Имеется пустыня длиной 500 км, автомобиль с баком на 100 л,
//который может перевезти до 2-х канистр по 25 л
//Расход бензина 1 л/км
//Необходимо найти наименьшее количество бензина
//которое потребуется что бы проехать пустыню

unit upust;
interface
const S = 500;
bak=100;
konistri=25;

type tkm=record
next:integer;
liter:integer;
end;
tpust=array[0..S]of tkm;

procedure fill(var p:tpust);

implementation
function Distanse(x,y:integer;benz:integer):integer;
var
Vway,Vdost,Vf:integer;
begin
//x начальная точка
//y-конечная точка
Vway:=150-(y-x)*2;//можно доставить за раз при длине пути y-x
Vdost:=0;//количество доставленного бензина в j точку
Vf:=0;//количество израсходованого бензина на доставку

while Vdost<benz do
begin
if (benz-Vdost)<150-(y-x)//если количество бензина которое можно увезти
then //за раз меньше количества которое осталось доставить тогда
begin
Vdost:=benz;
Vf:=Vf+(y-x);
end
else
begin
vf:=vf+(y-x)*2;//сделать рейс
Vdost:=Vdost+Vway//увеличить количество доставленого
end;
end;
result:=Vf+Vdost;
end;


procedure fill(var p:tpust);
var i,j,ras,reis,ben:integer;
begin
//Заполняем от 350 до 500
for i:=S downto S-bak-2*konistri do
begin
p[i].liter := S-i;
p[i].next := S;
end;
ras := (bak + 2*konistri -1) div 2;
//Заполнение от 349 до 0
for i := S - bak-2*konistri -1 downto 0 do
begin
p[i].liter := maxint;
p[i].next:=i;
for j:=1 to ras do //Выбираем оптимальное расстояние до следующей точки
begin
//кол-во топлива необх чтобы доехать из точки i до конца
ben :=distanse(i,i+j,p[i+j].liter);
if p[i].liter > ben
then
begin
p[i].next := i+j; //след точка в ко-ю мы можем попасть из i
p[i].liter := ben; //кол-во бензина чтобы доехать до конца
end;
end;
end;
end;//filL
// ben := 2*j*(reis-1)+j+p[i+j].liter+(p[i+j].liter mod 50);
// ben := 2*j*(reis-1)+j+(150-j)+(p[i+j].liter-p[i+j].liter mod 50);
//2*j*(reis-1)+(150-2*j)*(reis-1)+j+(150-j);
end.
Ответить с цитированием
  #13  
Старый 16.11.2006, 13:18
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Восклицание Замечание...

Проехав любое расстояние между двумя точками я могу оставить в конечной точке не более 50 литров бензина(имеется ввиду не более чем за одну ходку) Принцип следующий:
Для каждой из 74 точек предшествующих той точке в которой находится автомобиль(пусть это будет точка i) в данный момент, надо надо найти количество бензина которое потребуется что бы из этой точки доехать до конца пути! Причем для точки i надо выбрать следующую точку в которую мы поедем(пусть это будет точка j,(i<j)), и при этом в точке j должно быть то минимальное количество бензина, которое необходимо что бы доехать до конца!(т.е до точки 500км)

ЗЫ: в этой задачи надо использовать подход решения задачи с конца! При этом надо к ней применить волновой алгоритм!(надеюсь, что многие из посетителей этого форума знают что это такое) Причем волну по нахождению решения надо запустить с конца! (т.е с точки 350, т.к в этой точке мы знаем минимальное количество бензина-150л) Так расчитывая необходимое количество бензина для того чтобы доехать до следующей точки, и выбирая минимальное из них мы дойдем до точки 0! Т.е если имеется массив [0..500], то в точке 0 мы будем знать то количество бензина, которое потребуется, что бы доехать доконца!И дело остается за малым: найти наилучший путь, т.е тот маршрут по которому надо двигаться, что бы достич этого результата!

Последний раз редактировалось Rom@NS, 16.11.2006 в 13:35.
Ответить с цитированием
  #14  
Старый 20.11.2006, 00:15
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
Лампочка

Написал новую версию этой проги! Получил ответ 164100! почему я раньше думал, что он не верный? черт его знает?кто то с мысли видно сбил! завтра пойду показывать ее преподу снова! надеюсь что примет! тогда выложу для тех кому надо... да и для тех кому не надо тоже выложу...:d
__________________
VSU, AMM, Software and administration of information systems
We are the best among the best!
Ответить с цитированием
  #15  
Старый 21.11.2006, 17:47
Аватар для Rom@NS
Rom@NS Rom@NS вне форума
Прохожий
 
Регистрация: 05.11.2006
Адрес: Россия
Сообщения: 18
Репутация: 10
По умолчанию

все сходится к тому что верный ответ 164100...
__________________
VSU, AMM, Software and administration of information systems
We are the best among the best!
Ответить с цитированием
Ответ


Delphi Sources

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 12:57.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2023

ВКонтакте   Facebook   Twitter