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