|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
Результаты опроса: На ваш взгляд это сложная задача? | |||
Очень сложная | 0 | 0% | |
Сложная | 3 | 75.00% | |
Простая | 0 | 0% | |
Очень простая | 1 | 25.00% | |
Голосовавшие: 4. Вы еще не голосовали в этом опросе |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
||||
|
||||
Требуется помощь в написании проги!(динамическое программирование)
Сижу уже неделю, и не как не могу осилить! Даже мыслей никаких нет! А ведь скоро мне ее сдвать! Прошу-ПОМОГИТЕ!
задача: Есть дорога длинной 500км, в общем случае. В начале дороги находится АЗС. Есть автомобиль с баком в 100л и 2 канистры по 25л. Автомобиль на 1 км жрет 1л литр бензина. Требуется определить минимальное количество бензина, которое потребуется что бы проехать этот путь. А также вывести указание о том, как надо двигаться и где оставлять бензин. Подразумевается что в любой точке пути можно оставить любое количество бензина. samara@box.vsi.ru |
#2
|
||||
|
||||
Типа помоги себе сам... так понял?
У меня есть кое-какие варианты решения этой задачи.
Предлогается решать методом с конца Ну, типа в отметке 350км, что бы достичь конца дороги требуется 150л, в отметке 300км требуется 300л.(пощитано руками). Так конечно можно прочситать все!Но это же можно треснуть! Надо найти алгорим который бы это мог делать! ЗЫ может теперь кто поможет... |
#3
|
||||
|
||||
Цитата:
1) При чем тут АЗС (на что в твоей задаче это влияет)? 2) Минимальное количество бензина, которое потребуется что бы проехать этот путь = длинне дороги (из рассчета 1 литр на километр, если конечно на дороге нет развилок и объездных путей). Цитата:
А не 200 ли литров требуется в отметке 300км? (из рассчета 1 литр на километр) Цитата:
Если исходить из рассчета 1 литр на километр, то длинна дороги - текущая позиция = кол-во бензина, которое потребуется что бы проехать остаток пути... P.S. А вообще, из всего, написанного тобой ранее не очень понятно, чего в конечном итоге ты хочешь добиться... Зачем тебе это нужно? |
#4
|
||||
|
||||
???
Объясняю на пальца!
в начале дорога заправка. Начало дороги будем считать нулевым километром. Машине надо добраться до отметки в 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
|
||||
|
||||
Цитата:
Хочу посчиать минимальное количество бензина, которое потребуется что бы проехать эту дорогу таким макаром! А надо мне это для тго, что бы зачет в конце декабря получить! Задали мне такую вот прогу по теме Динамическое программирование! |
#6
|
||||
|
||||
С++
Есть следующий выриант решения этой задачи на С++, но в нем где то есть небольшая ошибка, а так я не знаю С++, то естественно этой ошибки не могу найти.
Может кто переведет мне этот код на 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
|
||||
|
||||
Нашлись добрые люди, которые помогли мне с решением этой задачей! Жаль только, что не на этом форуме!
Если Кому интересно, то могу выложить исходники! |
#8
|
||||
|
||||
Выложи. Любопытно взглянуть как это решается.
|
#9
|
||||
|
||||
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
|
||||
|
||||
Буду благодарен любым замечанииям! Может кто найдет баги или ошибки! Хотелось бы, что бы не молчали! Пишите о своих замечаниях! Может у кого есть более эффективный алгоритм! Буду рад всем новым постам по этой теме!
|
#11
|
||||
|
||||
Help!!!
Ан не тут то было! рано я радовался! сегодня показал ее преподу и он меня послал! сказал, что не верный ответ, и даже не стал смотреть исходники! так что где ошибка не знаю! И снова мне ТРЕБУЕТСЯ ВАША ПОМОЩЬ!!!
ЗЫ http://ega-math.narod.ru/Nquant/Puzzle.htm - ссылка для тех кому интересны подобные задачи! |
#12
|
||||
|
||||
И вот еще одни вариант... и снова не верный. Вроде как принцип такой, но вот ответ неверный! Узнать бы хотя бы сколько надо бензина, тогда можно было бы подогнать алгоритм под этот ответ!!! А так когда не знаешь к чему стремиться совсем не в жилу решать задачи подобного типа!
//Имеется пустыня длиной 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
|
||||
|
||||
Замечание...
Проехав любое расстояние между двумя точками я могу оставить в конечной точке не более 50 литров бензина(имеется ввиду не более чем за одну ходку) Принцип следующий:
Для каждой из 74 точек предшествующих той точке в которой находится автомобиль(пусть это будет точка i) в данный момент, надо надо найти количество бензина которое потребуется что бы из этой точки доехать до конца пути! Причем для точки i надо выбрать следующую точку в которую мы поедем(пусть это будет точка j,(i<j)), и при этом в точке j должно быть то минимальное количество бензина, которое необходимо что бы доехать до конца!(т.е до точки 500км) ЗЫ: в этой задачи надо использовать подход решения задачи с конца! При этом надо к ней применить волновой алгоритм!(надеюсь, что многие из посетителей этого форума знают что это такое) Причем волну по нахождению решения надо запустить с конца! (т.е с точки 350, т.к в этой точке мы знаем минимальное количество бензина-150л) Так расчитывая необходимое количество бензина для того чтобы доехать до следующей точки, и выбирая минимальное из них мы дойдем до точки 0! Т.е если имеется массив [0..500], то в точке 0 мы будем знать то количество бензина, которое потребуется, что бы доехать доконца!И дело остается за малым: найти наилучший путь, т.е тот маршрут по которому надо двигаться, что бы достич этого результата! Последний раз редактировалось Rom@NS, 16.11.2006 в 13:35. |
#14
|
||||
|
||||
Написал новую версию этой проги! Получил ответ 164100! почему я раньше думал, что он не верный? черт его знает?кто то с мысли видно сбил! завтра пойду показывать ее преподу снова! надеюсь что примет! тогда выложу для тех кому надо... да и для тех кому не надо тоже выложу...:d
VSU, AMM, Software and administration of information systems We are the best among the best! |
#15
|
||||
|
||||
все сходится к тому что верный ответ 164100...
VSU, AMM, Software and administration of information systems We are the best among the best! |