Такси компания
Задача:
(Зимни състезания по математика и информатика Плевен 1998, Тема по информатика 8-9 клас)
Експрес такси
Движението по дълга улица на "Експрес такси" е организирано, така че има спирка на всеки километър. "Експрес такси" се движи по улицата от всяка спирка 1,2,3,... или 10 километра без спиране.
За всяко от десетте разстояния цените са дадени в таблица, например:
1 12
2 21
3 31
4 40
5 49
6 58
7 69
8 79
9 90
10 101
Пътник иска да пътува n (1<=n<=100) километра. Какви разстояния на пътуване трябва да избере, така че пътуването да му излезе най-евтино, и каква е цената на цялото пътуване?
Напишете програма, която да реши проблема.
Входни данни:
В първия ред на входния файл INPUT3.TXT са записани 10 цели числа, които са цените за пътуване, съответно на 1,2,3,...,10 километра, а във втория ред е записано само числото n.
Изходни данни:
Всеки ред без последния от изходния файл OUTPUT3.TXT трябва да съдържа две числа ѕ дължината на маршрута и цената на билета. Цената на цялото пътуване трябва да се запише на последния ред от изходния файл.
Примерен вход:
12 21 31 40 49 58 69 79 90 101
15
Примерен изход
3 31
6 58
6 58
147
Решение:
Не е трудно да се забележи, че условието броят на спирките да бъде точно 10 е несъществено. Ето защо ще разгледаме задачата в по-общия случай, когато броят на спирките k се задава като параметър и се определя от броя на целите числа, записани на първия ред от входния файл (TAXI.TXT). Резултата ще извеждаме на екрана.
Настоящата задача е типичен пример за задача, която се решава с динамично оптимиране. Дефинираме целевата функция F така:
F(0) = 0
F(X) = min[F(X-Y) + C(Y)], (X і Y; 1ЈXЈn, 1ЈYЈk), където F(X) е търсената минимална цена за X километра, а C(Y) е дадената по условие тарифа за превоз на Y километра.
Забележете, че за разлика от класическия случай на динамично оптимиране, тук не се налага поддържането на множество от участващите в конкретен маршрут разтояния, тъй като за тях няма наложени никакви ограничения. Функцията MAIN, решаваща задачата, съдържа два вложени For-цикъла със сложности съответно O(n) и O(k), като сложността на тялото им е константа, т. е. O(1). Оттук за общата им сложност получаваме O(n.k). Тъй като n и k са независими един от друг параметри, полученият резултат O(n.k) не би могъл да се опрости.
Стойностите на целевата функция F(X) ще изчисляваме последователно, започвайки от 1. За всяко X (1ЈXЈn) ще пазим изчислената стойност на F(X), както и разстоянието Y от рекурентната формула, за което тя се постига. Така при изчислението на F(X) всички необходими ни предишни стойности на F ще бъдат вече пресметнати. Разстоянието Y не ни е необходимо за изчисленията, но трябва да се помни, тъй като то ни позволява за всяко X да намерим едно конкретно пътуване, с минимална стойност.
Възстановяването на търсения път се извършва със сложност O(n). Последният маршрут в този път ще бъде това Y1, което съответства на F(n). Предпоследният маршрут ѕ Y2, съответстващо на F(n-Y1) и т. н. След обръщане на получената последователност получаваме търсения минимален път. В приложената програма резултатът се извежда директно, без да се обръща. Това се прави основателно, тъй като между отделните маршрути не съществува връзка. Тогава при произволна пермутация на маршрутите, съставящи даден път, отново получаваме валиден път, при това със същата цена. В частност последното важи и при обръщане последователността на маршрутите.
Програма:
PROGRAM TAXI;
CONST MaxN = 100; { Максимален брой километри }
MaxK = 20; { Максимален брой спирки }
TYPE OgrN = 0..MaxN;
OgrK = 0..MaxK;
TCena = LongInt;
CONST MaxCena = MaxLongInt;
VAR Ceni : Array[OgrK] of TCena;
Rast : Array[OgrN] of Record
Nov : OgrK; { Последна измината отсечка }
Cena : TCena { Цена на разстоянието }
End;
N : OgrN;
K : OgrK;
PROCEDURE INIT; { Прочитане на входните данни }
Var F : TEXT;
Begin
Assign(F,'TAXI.TXT'); Reset(F); K := 0;
While not EoLn(F) do begin Inc(K); Read(F,Ceni[K]) end;
ReadLn(F); ReadLn(F,N);
Close(F)
End;
PROCEDURE MAIN(N : OgrN); { Решава задачата чрез динамично оптимиране }
Var I : OgrN;
J : OgrK;
Begin
Rast[0].Cena := 0;
For I := 1 to N do
With Rast[I] do
begin Cena := MaxLongInt;
For J := 1 to K do
If (I >= J) and (Rast[I-J].Cena + Ceni[J] < Cena) then
begin Cena := Rast[I-J].Cena + Ceni[J]; Nov := J end
end
End;
PROCEDURE PRINT(N : OgrN); { Извежда резултата на екрана }
Begin
WriteLn('Обща стойност на пътуването: ',Rast[N].Cena);
WriteLn('Дължина и стойности на отделните отсечки:');
While N > 0 do
With Rast[N] do begin WriteLn(Nov,' ',Ceni[Nov]); Dec(N,Nov) end
End;
BEGIN
INIT;
MAIN(N);
PRINT(N)
END.
Преслав Наков
студент - СУ