Зміст (стр. 16 )

ball[j, i] := 1; ball[i, j] := 1;

inc(itog[i],1); inc(itog[j],1);

end else

if (itog[j] < itog[k]) and (itog[i] > itog[j]) then

{ якщо менше, то виграш, якщо у команди противника більше }

begin

math[j, i] := 3; math[i, j] := 3;

ball[j, i] := 1; ball[i, j] := 0;

inc(itog[j],2);

end;

end;

inc(i);

end;

inc(j);

end;

{ визначаємо підсумкове місце збірної Уранії }

mesto := 1;

for i := 1 to n do if itog[i] > itog[k] then inc(mesto);

assign(f, fileout); rewrite(f);

write(f, mesto);

close(f);

end.

У термінах теорії графів задачу можна сформулювати так: Дано мережу N(V, E,W). Знайти найкоротший шлях між Vi і Vk (Vi, Vk Î V).

Найбільш простим для розв'язання даної задачі є алгоритм Дейкстри, який відшукує найкоротшу відстань від початкової вершини до всіх інших вершин, тобто розв'язує більш загальну задачу. Ми приведемо опис алгоритму Дейкстри, застосувати його до сформульованої задачі пропонуємо самостійно.

Алгоритм Дейкстри базується на правилі криволінійного трикутника: якщо a, b, c – сторони такого трикутника і a + b < c, то c := a + b.

Введемо позначення:

C[i, j] – довжина ребра (i, j), С[i, j] >= 0 (якщо ребра немає, то його довжина приймається рівною нескінченності).

D[i] – найкоротша поточна відстань від вершини start до вершини i.

flag[i] – інформація про перегляд вершини i: 0 – якщо вершину не розглянуто, 1 – якщо розглянуто. Якщо вершину розглянуто, то для неї D[i] є найкоротшою відстанню від вершини start до вершини i.

pred[i] – інформація про номер вершини, що передує вершині i в найкоротшому шляху від вершини start.

min – це мінімальна відстань.

Алгоритм:

...

for i := 1 to N do { підготовчий етап }

begin

pred[i] := start; { до всіх вершин шукаємо шлях з start }

flag[i] := 0; { всі вершини ще не розглянуто }

D[i] := C [start, i] { найкоротшою є відстань між ними (якщо вона є!) }

end;

flag[start] := 1; { поки що ми знаємо тільки відстань }

pred[start] := 0; { від вершини start до неї ж, рівну 0 }

for i := 1 to N-1 do

begin

min := maxint; { найменша відстань рівна нескінченності }

for j := 1 to N do

if (flag[ j ] = 0) and (min > D[ j ]) then

begin { знаходимо мінімальні }

min := D[ j ]; { відстані }

k := j; { до невідмічених вершин }

end;

flag[k] := 1; { вершину k помічаємо як розглянуту }

for j := 1 to N do { виконуємо перегляд }

if (flag [ j ] = 0) and (D [ j ] > D [ k ] + C [ k, j ]) then

{ тобто, якщо для вершини j ще не знайдено найкоротшу

відстань від start, і з вершини k по дузі C [ k, j ]

шлях до j коротший, ніж знайдений раніше }

begin

D [ j ] := D [ k ] + C [ k, j ]; { то запам'ятовуємо його }

pred [ j ] := k;

end;

end;

...

Описаний алгоритм було запропоновано ще в 1959 році. Модифікуйте його у застосуванні до умови сформульованої задачі.

Єдина задача, до якої ми не даємо навіть ідеї. Причина? Просто дана задача настільки сподобалась авторам книги, що вони вирішили оголосити заочний конкурс на кращу програму (або доведену ідею) розв'язання даної задачі. Приз – комплект комп'ютерних версій книг з програмування на CD-ROM!

Задача сформульована за мотивами відомих задач, що в різний час використовувались на різних олімпіадах, наприклад, “Максимальна сума” (ІХ олімпіада Житомирської області) або “Гроші на шахівниці” (олімпіада 1998-99 навчального року Київського фізмат–ліцею). Ідеї розв'язку описані повністю при розгляді задачі “Максимальна сума”. Звернемо увагу лише на той факт, що при обчисленні кількості можливих маршрутів можуть виникнути певні труднощі у зв'язку з використанням великих чисел (A, B £ 100), тому для знаходження кількості маршрутів мишки можна використати інший спосіб підрахунку, який базується на тому, що кількість маршрутів до кожної клітинки дорівнює сумі кількості маршрутів до клітинки, розміщеної ліворуч, і кількості маршрутів до клітинки, розміщеної праворуч.

program mouse;

var m, n, i, j : word;

mon, res, kol : array[1..21,1..21] of word;

f : text; st : string;

begin

st := '';

assign(f,'mouse. dat'); reset(f);

readln(f, m, n);

for j:=1 to m do

for i:=1 to n do

begin

read(f, mon[j, i]);

end;

close(f);

assign(f, 'mouse. sol'); rewrite(f);

{ Підраховуємо кількість маршрутів }

for i := 1 to m do kol[i,1] := 1;

for i := 1 to n do kol[1,i] := 1;

for j := 2 to m do for i := 2 to n do kol[j, i] := kol[j-1,i]+kol[j, i-1];

writeln(kol[m, n]); writeln(f, kol[m, n]);

{ Шукаємо оптимальний маршрут і потрібну суму зернин }

res := mon;

for j := m-1 downto 1 do res[j,1] := res[j,1]+res[j+1,1];

for i := 2 to n do res[m, i ]:= res[m, i] + res[m, i-1];

for j := m-1 downto 1 do

for i := 2 to n do

if res[j+1,i] > res[j, i-1] then res[j, i] := res[j, i]+res[j+1,i]

else res[j, i] := res[j, i] + res[j, i-1];

writeln(res[1,n]); writeln(f, res[1,n]);

j := 1; i := n;

repeat

if j<m then

begin

if res[j+1,i] > res[j, i-1] then

begin

j := j+1; st := st + 'B';

end

else if i>1 then

if res[j, i-1] >= res[j+1,i] then

begin

i := i-1; st := st + 'П';

end;

end;

if j = m then while i <> 1 do begin

st := st + 'П';i:=i-1;

end;

if i = 1 then while j<>m do begin

st := st + '‚';j:=j+1;

end;

until (j = m) and (i = 1);

for i := length(st) downto 1 do

begin

write(st[i]);write(f, st[i]);

end;

writeln;close(f);

readln

end.

Задача досить проста і планувалась як втішна, з нею, на думку організаторів олімпіади, повинен був справитись кожен учасник. Ідея розв'язку полягає в наступному: до прочитаного з файлу рядка спереду і в кінці приклеюємо пропуск. Переглядаємо всі послідовності по п'ять символів підряд, якщо дана послідовність є потрібним словом, то у новий рядок вносимо потрібну заміну, якщо ж ні, то у новий рядок додаємо черговий символ вхідного рядка. Описаний алгоритм реалізовано у програмі, що приводиться нижче.

program fish; { бо дельфін харчується рибою! }

const kit = ' кит';

Bkit = ' Кит';

delf = ' дельфін';

Bdelf = ' Дельфін';

inname = 'fish. dat';

outname = 'fish. sol';

var f : text;

st, st1, st2 : string;

i, k : integer;

begin

assign(f, inname); reset(f); readln(f, st); close(f);

st := ' ' + st + ' ';

k := length(st); st1 := ''; i := 1;

while i <= k do

begin

st2 := copy(st, i,5);

if ( st2 = kit ) or ( st2 = bkit ) then

begin

if st2 = kit then st1 := st1 + delf

else st1 := st1 + Bdelf;

inc(i,4)

end

else

begin

st1 := st1 + st[i];

inc(i);

end;

end;

assign(f, outname); rewrite(f); write(f, st1); close(f);

end.

Можливі декілька підходів до розв'язання цієї задачі. Можна використовувати черги, стеки, множини, рекурсію і т. д. Ми приведемо ідею розв'язання, яка використовує тільки базові поняття мови програмування і яка реалізована без використання вищезгаданих методів.

Рис. 1

Для початку розглянемо довільне положення шахового коня на шаховій дошці. Припустимо, що кінь знаходиться у клітинці Е5. На рисунку точками відмічено клітини, у які кінь може піти при черговому ході. Таких клітин може бути від двох (у випадку, коли кінь знаходиться у кутку дошки) до восьми (як у наведеному прикладі). Ідея розв'язання полягає у відшуканні найкоротшого шляху від точки старту (Xstart, YStart) до точки фінішу (Xfine, YFine), тобто задача зводиться до відшукання найкоротшого шляху виходу з лабіринту з заданим положенням коня і точкою виходу з лабіринту (точка фінішу). Відомо багато способів відшукання такого шляху. Будемо одночасно працювати з двома шаховими дошками: одну використаємо для підрахунку кількості кроків до виходу, а іншу – для позначення номерів клітин, з яких ми потрапляємо в чергову клітину.

Обидва масиви спочатку заповнюємо нулями. Потім помічаємо клітину, у якій знаходиться кінь, як пройдену – заносимо в неї 1, причому одночасно на обох дошках.

На кожному з наступних кроків, доки не досягли клітини фінішу робимо так:

Рис. 2. 8	26	36	17	27	46	47	57	67
7	36	15	16	26	36	46	56	0
6	24	34	15	27	35	45	55	65
5	1	13	23	24	34	44	54	0
4	22	36	15	23	35	43	53	63
3	34	15	12	22	34	42	52	0
2	24	34	11	23	31	41	53	61
1	23	13	23	22	32	42	52	0
	1	2	3	4	5	6	7	8
					Рис. 3

n переглядаємо всі клітини шахової дошки і, якщо в них міститься номер ходу, то відшукуємо всі клітини, у які може піти кінь, і заносимо в них значення номера ходу, який на 1 більше розглядуваного, а на іншій дошці вказуємо координати клітини, з якої ми в неї прийшли;