Прошу помочь с задачей по обьектно ориентированному:
Курьеру отдела поручено разнести переписку в N различных подразделений организации, после чего вернуться в отдел. Расстояние Aij (i,j=1,2,...N) между подразделениями и расстояние Bi между отделом и подразделениями заданы. Определить очередность обхода подразделений, при которой длина маршрута минимальна.
Исходные данные:
N=5; B = (40, 40, 140, 100, 160);
| 0 5 2 100 75 |
| 5 0 20 20 20 |
| 2 20 0 10 70 | = A
|100 20 10 0 100 |
| 75 20 70 100 0 |
Как я понимаю это разновидность стандартной задачи о коммивояжере из курса алгоритмов обработки данных, а у меня с этим всегда были напряги
Последний срок у меня раннее утро 22го. Будет время - разберитесь пожалуйста.
p.s.: или вариант - задача на дельфи -
Имеется возможность выбора недели, в каждой неделе выбора дня. Каждый день задаётся 5 отметок температур. Выдавать по требованию: - день с наибольшей средней температурой за месяц; - максимальную и минимальную температуру за месяц.
Для сохранения данных использовать типизированные файлы. Файлы исходных данных формировать программным способом.
Курьер на Паскале. Ввод температур на дельфи.
Вот вариант решения задачи на подобие первой(про комивояжора, придется подогнать под условия).
[syntax='delphi']
program PRG1;
uses
crt;
const
MaxN=10;
var
F:text;
rBuf:string;
nBuf:string;
iBuf:integer;
Roads:array[1..MaxN,1..MaxN]of integer;
Visited:array[1..MaxN]of boolean;
Alloved:array[1..MaxN]of boolean;
Tmp:array[1..MaxN]of integer;
i:integer;
j:integer;
c:integer;
k:integer;
Start:integer;
Current:integer;
Count:integer;
procedure Init;
begin
writeln('Чтение INPUT.TXT...');
Assign(F,'INPUT.TXT');
reset(f);
for i:= 1 to Count do
begin
readln(f,rBuf);
k:=1;
for j:= 1 to length(rBuf)+1 do
begin
if (rBuf[j]<>' ')and(j<>length(rBuf)+1) then
nBuf:=nBuf+rBuf[j]
else
begin
val(nBuf,iBuf,c);
nBuf:='';
Roads[k,i]:=iBuf;
inc(k);
end;
end;
end;
close(f);
writeln;
for i:=1 to count do
begin
for j:=1 to count do
write(roads[j,i], ' ');
writeln;
end;
for i:= 1 to MaxN do
Alloved:=true;
end;
function AllVisited:boolean;
var
i:integer;
b:boolean;
begin
b:=true;
for i:= 1 to count do
b:= b and visited;
AllVisited:=b;
end;
procedure CheckAlloved;
var
i:integer;
begin
for i:= 1 to count do
begin
if not ((not Visited)or (allvisited) ) then
begin
Tmp:=maxint;
Alloved:=false;
end
else Tmp:=Roads[i,current];
end;
end;
function FindNearest:integer;
var
min:integer;
num:integer;
label R;
begin
checkalloved;
R: min:=maxint;
if allvisited then
begin
FindNearest:=start;
exit;
end;
for i:= 1 to count do
if (Tmp<min)and(Tmp<>0) then
begin
min:=tmp;
num:=i;
end;
if not alloved then goto R;
FindNearest:=num;
end;
begin
clrscr;
writeln('Введите размер матрицы:');
readln(Count);
writeln;
init;
writeln; writeln('Введите номер города, из которого начинается маршрут:');
readln(start);
current:=start;
visited[start]:=true;
Assign(f,'OUTPUT.TXT');
rewrite(f);
write(f,start);
repeat
current:=FindNearest;
visited[current]:=true;
write(f, ' ',current);
until (current=start);
close(f);
writeln;
writeln('Данные записаны в файл OUTPUT.TXT');
writeln('Press <ENTER>');
repeat until keypressed;
end.
[/syntax]
Решение кривое, но рабочее.
Потом выложу на всякий случай решение второй.
[syntax='delphi']
program PRG1;
uses
crt;
const
MaxN=10;
var
F:text;
rBuf:string;
nBuf:string;
iBuf:integer;
Roads:array[1..MaxN,1..MaxN]of integer;
Visited:array[1..MaxN]of boolean;
Alloved:array[1..MaxN]of boolean;
Tmp:array[1..MaxN]of integer;
i:integer;
j:integer;
c:integer;
k:integer;
Start:integer;
Current:integer;
Count:integer;
procedure Init;
begin
writeln('Чтение INPUT.TXT...');
Assign(F,'INPUT.TXT');
reset(f);
for i:= 1 to Count do
begin
readln(f,rBuf);
k:=1;
for j:= 1 to length(rBuf)+1 do
begin
if (rBuf[j]<>' ')and(j<>length(rBuf)+1) then
nBuf:=nBuf+rBuf[j]
else
begin
val(nBuf,iBuf,c);
nBuf:='';
Roads[k,i]:=iBuf;
inc(k);
end;
end;
end;
close(f);
writeln;
for i:=1 to count do
begin
for j:=1 to count do
write(roads[j,i], ' ');
writeln;
end;
for i:= 1 to MaxN do
Alloved:=true;
end;
function AllVisited:boolean;
var
i:integer;
b:boolean;
begin
b:=true;
for i:= 1 to count do
b:= b and visited;
AllVisited:=b;
end;
procedure CheckAlloved;
var
i:integer;
begin
for i:= 1 to count do
begin
if not ((not Visited)or (allvisited) ) then
begin
Tmp:=maxint;
Alloved:=false;
end
else Tmp:=Roads[i,current];
end;
end;
function FindNearest:integer;
var
min:integer;
num:integer;
label R;
begin
checkalloved;
R: min:=maxint;
if allvisited then
begin
FindNearest:=start;
exit;
end;
for i:= 1 to count do
if (Tmp<min)and(Tmp<>0) then
begin
min:=tmp;
num:=i;
end;
if not alloved then goto R;
FindNearest:=num;
end;
begin
clrscr;
writeln('Введите размер матрицы:');
readln(Count);
writeln;
init;
writeln; writeln('Введите номер города, из которого начинается маршрут:');
readln(start);
current:=start;
visited[start]:=true;
Assign(f,'OUTPUT.TXT');
rewrite(f);
write(f,start);
repeat
current:=FindNearest;
visited[current]:=true;
write(f, ' ',current);
until (current=start);
close(f);
writeln;
writeln('Данные записаны в файл OUTPUT.TXT');
writeln('Press <ENTER>');
repeat until keypressed;
end.
[/syntax]
Решение кривое, но рабочее.
Потом выложу на всякий случай решение второй.
Ни что так не ограничивает фантазию программиста, как компилятор...
Интересно, зачем во второй задаче ввод недели и дня, если потом всеравно анализируются данные за месяц?
И не совсем понятно с тиризированными файлами:
формат не оговорен, следовательно, если например сделать файл integer, то никто его прочитать не сможет. Или под типизированным файлом подразумевается тип "text"?
И не совсем понятно с тиризированными файлами:
формат не оговорен, следовательно, если например сделать файл integer, то никто его прочитать не сможет. Или под типизированным файлом подразумевается тип "text"?
Ни что так не ограничивает фантазию программиста, как компилятор...