Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Приклади використання двомірних масивів

Задача 219.Скласти програму для розв’язання системи n лінійних рівнянь з n невідомими.

Розв’язання: Задача цікава тим, що вона досить часто постає при розв’язанні фізичних, технічних, економічних та інших практичних задач. У загальному вигляді система n лінійних рівнянь з n невідомими записується у вигляді:

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

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

Хід розв’язання методом виключення невідомих вам добре відомий з курсу математики, томи ми його просто покажемо. Якщо ж у когось виникнуть труднощі з розумінням ходу розв’язання, то ми в черговий раз рекомендуємо відкласти в сторону на деякий час даний підручник і засісти за підручник математики.

Остання система легко розв’язується поступовою підстановкою значень змінних від останнього рівняння до першого: х₃ = 4, х₂ = –2, х₁ = 3.

Весь хід нашого розв’язання можна умовно розбити на дві частини: зведення системи 3-го порядку до рівносильної їй трикутної системи з одиничними коефіцієнтами по діагоналі (цей етап називається прямим ходом алгоритму Гауса), а потім обчислення невідомих, починаючи з кінця (зворотній хід). Зауважимо, що розв’язання даним методом можливе лише тоді, коли початкова система сумісна і має єдиний розв’язок.

При програмній реалізації даного алгоритму необхідно врахувати декілька моментів, а саме: на деякому етапі черговий коефіцієнт, що нам потрібно знайти, може бути рівним нулю. Або ж при діленні, яке ми виконуємо постійно, можемо отримати число, яке може виявитись настільки малим, що для нашого електронного друга воно в пам’яті відображатиметься нулем. Для того, щоб обійти ці невеликі підводні рифи удосконалимо розв’язання у загальному випадку таким чином, що на кожному черговому етапі будемо виключати невідоме з найбільшим за модулем коефіцієнтом, іншими словами, ми будемо переставляти рядки матриці (міняти місцями рівняння).

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

program Gaus;

uses dos, crt;

const k = 20;

type urawnenie = array[1..k+1] of real;

matrix = array[1..k] of urawnenie;

bar = array[1..k] of real;

var mas : matrix;

x : bar;

max, f : real;

i, j, n, d, l : integer;

begin

{ Введення вхiдних даних }

write('Введiть порядок системи: ');readln(n);

for i := 1 to n do

begin

for j := 1 to n do

begin

write('a[',i,',',j,'] = ');

readln(mas[i][j]);

end;

write('b[',i,'] = ');

readln(mas[i][n+1]);

end;

{ Виведення iх на екран у звичному виглядi }

writeln('Програма розв''язуе методом Гауса систему: ');

for i := 1 to n do

begin

for j := 1 to n+1 do

if j < n+1 then

if j = 1 then write(mas[i][j]:2:1,' x',j)

else if mas[i][j] < 0 then write(' - ',-mas[i][j]:2:1,' x',j)

else write(' + ',mas[i][j]:2:1,' x',j)

else write(' = ',mas[i][j]:2:1);

writeln;

end;

{ Алгоритм Гауса - прямий хiд }

for i := 1 to n do

begin

{ вибiр рiвняння з найбiльшим за модулем коеф. при х[i] }

max := abs(mas[i][i]);

d := i;

for l := i+1 to n do

if abs(mas[l][i]) > max then

begin

max := abs(mas[l][i]);

d := l;

end;

{ якщо потрiбно, то переставили мicцями два рiвняння }

if d <> i then

for j := i to n+1 do

begin

f := mas[i][j];

mas[i][j] := mas[d][j];

mas[d][j] := f;

end;

{ дiлимо i-те рiвняння на коеф. при x[i] }

f := mas[i][i];

for j := i+1 to n+1 do mas[i][j] := mas[i][j]/f;

{ виключаемо x[i] з усiх рiвняннь, що стоять нижче }

for l := i+1 to n do

begin

{ виключаемо x[i] з l-го рiвняння }

f:= mas[l][i];

for j := i+1 to n+1 do mas[l][j] := mas[l][j] - mas[i][j]*f;

end;

{ кiнець прямого ходу i початок зворотнього }

x[n] := mas[n][n+1];

for i := n-1 downto 1 do

begin

x[i] := mas[i][n+1];

for j := i+1 to n do x[i] := x[i] - mas[i][j]*x[j]

end;

{ виведення результатiв }

writeln; writeln('Коренi системи рiвнянь:');

for i:=1 to n do write(' x[',i,'] = ',x[i]:2:1);

readln;

end.

Задача 220. (завдання олімпіади Київського фізмат ліцею у 1998-99 навчальному році)

“Гроші на шахівниці”

На кожній клітинці шахівниці розміром Mx N клітин випадковим чином розкладено монети, загальна вартість яких не перевищує 3333$. Пішак можу рухатись або праворуч, або вгору (на одне поле за один хід) від нижнього лівого поля до правого. З усіх клітин, на яких побував пішак знімають монети і складають у сейф.

Завдання. Створіть програму MONEY.*, яка допоможе таким чином зібрати найбільшу кількість монет

Вхідні дані. Перший рядок вхідного файлу MONEY.DAT містить у вказаному порядку натуральні числа M i N, менші за 22. Для j в межах від 1 до M включно (j+1)-й рядок цього ж файлу містить сукупні вартості монет у клітинах j–го рядка шахівниці, якщо рахувати рядки згори до низу, у тому ж порядку, як вони (клітини цього рядка) розташовані на шахівниці. Наприклад:

2 3

1 2 3

6 8 2

Вихідні дані. Перший рядок вихідного файлу MONEY.RES має містити найбільшу кількість монет, яку можна зібрати таким чином. Наступний рядок цього ж файлу містить M+N–2 символи, що описують напрям ходів пішака (від першого до останнього): U – вгору (від англійського Up), R – праворуч (від англійського Right), які дають можливість зібрати найбільше грошей, і в якій хід праворуч здійснюється якомога пізніше на кожній ділянці шляху. Наприклад, для наведеного прикладу:

RUR

Розв’язання: Задачу можна розв’язувати різними способами. Ми познайомимо вас на прикладі даної задачі з однією з модифікацій “жадібного” алгоритму, який покладено в основу одного з методів динамічного програмування і який у даному випадку працює просто прекрасно і дає можливість знайти розв’язок всього за два проходження по масиву. Для більшої наочності візьмемо конкретний приклад. Нехай наша шахівниця має розмір 4 на 5. Розміщення монет на шахівниці відобразимо відповідною матрицею (Рис. 1).





		Рис. 1





		Рис. 2





		Рис.3





		Рис. 4

На підставі даної матриці сформуємо нову, користуючись правилами ходу, описаними в умові задачі. Але у клітини нової матриці ми будемо заносити сумарні (вже зібрані) найбільші кількості монет. Зрозуміло, що в любу клітину нижнього рядка ми можемо попасти тільки з клітини розміщеної ліворуч, а в довільну клітину лівого стовпчика тільки з нижньої клітини, тому нова матриця після заповнення нижнього рядка і лівого стовпчика набуде вигляду, як показано на рисунку 2. У клітинку [3,2] ми можемо попасти або з клітинки [3,1], або з клітинки [4,2]. Зрозуміло, що нам вигідніше попасти в неї з клітинки розміщеної ліворуч ([3,1]), так як у цьому випадку ми зберемо більшу кількість монет. Аналогічні міркування застосуємо до всіх клітинок незаповненого нижнього рядка, рухаючись зліва направо і вибираючи ту з двох клітин, розміщених ліворуч або нижче, прийшовши з якої ми зберемо більшу кількість монет. Такі алгоритми, що грунтуються завжди на виборі більшого з можливих варіантів прийнято називати «жадібними». Застосувавши описаний алгоритм до конкретного прикладу, отримаємо масив для сумарної кількості монет, зображений на рис. 3. Після заповнення всього масиву здійснюємо зворотний хід по новоутвореному масиву рухаючись або вліво, або вниз, вибираючи ту з комірок, у якій міститься більша кількість монет. При рівній кількості монет у вказаних комірках ми будемо вибирати комірку, що знаходиться ліворуч, так як згідно умови задачі ми повинні рухатись праворуч як можна пізніше. Оскільки рухаючись назад ми ліворуч підемо раніше, то при прямому ході ми праворуч звернемо пізніше. Маршрут, отриманий таким чином, відображено жирним шрифтом на рисунку 4. Нам залишилось привести програму, що повністю реалізує описаний алгоритм і розв’язує поставлену задачу. Необхідні пояснення приведено в коментарях до програми. Одразу наголосимо, що для наочності ми будемо у програмі виводити обидва масиви і маршрут руху на екран. Модифікувати програму для випадку виводу у файл, як того вимагає умова задачі ми надаємо право вам.

program money;

var m, n, i, j : integer;

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

f : text; st : string;

begin

st := '';

assign(f,'money.dat'); reset(f); { згадайте роботу з файлами – див. §2.5 }

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);{ закрили файл }

{ Зверніть увагу на наступний рядок! Виявляється у Паскалі з цілими маси вами можна працювати як з окремими змінними. }

res:=mon; { однією командою скопіювали весь масив! }

for j:=1 to m do

begin

for i:=1 to n do write(mon[j,i]:5); { вивели масив на екран }

writeln;

end;

writeln;

{ утворюємо новий масив – спочатку заповнюємо лівий стовпчик }

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];

{ виводимо новоутворений масив на екран, знову ж таки тільки з метою кращої наочності }

for j:=1 to m do

begin

for i:=1 to n do write(res[j,i]:5);

writeln;

end;

writeln(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+'u'; { то пишемо що потрібно йти вгору }

end

else if i>1 then

if res[j,i-1] >= res[j+1,i] then { а якщо вліво }

begin

i:=i-1; st:=st+'r'; { то пишемо, що вправо }

end;

{ якщо дійшли до низу, то рухаємось тільки вліво }

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

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

end;

{ а якщо дійшли до лівого краю, то рухаємось тільки вниз }

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

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

end;

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

{ оскільки ми здійснювали зворотний хід, то утворений маршрут потрібно вивести на екран у зворотному порядку: }

for i:=length(st) downto 1 do write(st[i]);

writeln;

readln

end.

Задача 221. (завдання обласної олімпіади 1993 року) Скласти програму для гри з комп’ютером в морський бій.

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

Всі роздуми щодо логічної побудови програми будуть приведені в тексті програми у вигляді коментарів.

Як нам організувати робоче поле? Всім відомо, що при грі в морський бій використовують ігрове поле розміром 10 на 10 клітинок. Ми також будемо грати на полі 10 на 10, але для зручності програмування гри в пам’яті комп’ютера будемо зберігати поле 12 на 12, тобто ми з усіх сторін ігрового поля добавимо же по рядку. Зроблено це для того, щоб спростити перевірки виходу за межі ігрового поля. Отже, замість масиву mypole[1..10,1..10] ми використаємо масив mypole[0..11,0..11]. Домовимось, що при створенні математичної моделі гри будемо дотримуватись таких правил:

– якщо клітинка ігрового поля пуста і в неї не стріляли, то в ній буде міститися 0;

– якщо в даній клітинці розташовано корабель, то в ній міститься 1;

– якщо в клітинку стріляли, то в ній міститься 2.

Всі бокові клітинки, які є ніби «зайвими» і на екрані не відображаються заповними одразу двійками. Стріляти по ігровим полям будемо з комп’ютером по черзі, право першого пострілу залишимо за гравцем. Перед початком бойових дій кількості кораблів суперників прирівняємо до 10, після попадання в корабель зменшуємо відповідну кількість кораблів на 1. Бойові дії закінчується, якщо потоплено всі кораблі одного з противників.

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

program morboj;

uses dos, crt,graph;

label mmm;

var gd,gm,i,j,l,i1,j1 : integer;

ch : char;

bul : boolean;

mypole, ibmpole : array[0..11,0..11] of byte; { для поля гри 12 на 12 }

mykor, ibmkor : integer;

k, kk : integer;

st : string;

xod : integer;

{ Очистка буферу клавiатури }

procedure och;

begin

repeat ch:=readkey until not keypressed;

end;

procedure wokrug;

var i : integer;

begin

for i:=0 to 11 do

begin

mypole[i,0]:=2; ibmpole[i,0]:=2;

mypole[i,11]:=2; ibmpole[i,11]:=2;

mypole[0,i]:=2; ibmpole[0,i]:=2;

mypole[11,i]:=2; ibmpole[11,i]:=2;

end;

end;

procedure ibmkorabel; { комп’ютер розставляє свої кораблі }

var

flag1 : boolean;

begin

kk := 10;

while kk <> 0 do

begin

flag1 := true;

i := 1 + round(random(10));

j := 1 + round(random(10));

for i1 := i-1 to i+1 do

for j1 := j-1 to j+1 do

if ibmpole[i1,j1] <> 0 then flag1 := false;

if flag1 = true then

begin

ibmpole[i,j] := 1;

dec(kk);

end;

end;

wokrug;

end;

procedure korabel; { ставимо один свій корабель }

var i1,j1 : integer;

flag1 : boolean;

begin

flag1 := true;

for i1 := i-1 to i+1 do

for j1 := j-1 to j+1 do

if getpixel(15+i1*10,15+j1*10)<>0 then flag1 := false;

if flag1 = true then

begin

Setcolor(5);

Setfillstyle(1,5);

bar(10+10*i,10+10*j,20+10*i,20+10*j);

mypole[i,j]:=1; { заповнюємо масив розташування своїх кораблів }

dec(k);

end;

end;

procedure wistrel; { наш постріл }

var i1,j1 : integer;

begin

if ibmpole[i,j] = 1 then

begin

ibmpole[i,j]:=2;

line(190+10*i,10+10*j,200+10*i,20+10*j);

line(190+10*i,20+10*j,200+10*i,10+10*j);

for i1:=i-1 to i+1 do

for j1:=j-1 to j+1 do

if ibmpole[i1,j1] = 0 then putpixel(195+10*i1,15+10*j1,1);

dec(ibmkor);

end

else

begin

putpixel(195+10*i,15+10*j,1);

xod := 0;

end

end;

procedure myxod;

begin

repeat

Setcolor(2);Rectangle(190+10*i,10+10*j,200+10*i,20+10*j);

ch := readkey;

Setcolor(1);Rectangle(190+10*i,10+10*j,200+10*i,20+10*j);

case ch of

{ вліво } #75 : dec(i);

{ вправо } #77 : inc(i);

{ вверх } #72 : dec(j);

{ вниз } #80 : inc(j);

{ пропуск } #32 : wistrel;

end; { case }

if i<1 then i := 10;

if i>10 then i := 1;

if j<1 then j := 10;

if j>10 then j := 1;

if ibmkor=0 then xod := 0;

until xod = 0;

end;

procedure ibmxod;

begin

repeat

i := round(random(10))+1;

j := round(random(10))+1;

until mypole[i,j]<>2;

putpixel(15+i*10,15+j*10,1);

if mypole[i,j]=1 then

begin

for i1:=i-1 to i+1 do

for j1:=j-1 to j+1 do

begin

mypole[i1,j1]:=2;

if (i1>0) and (i1<11) and (j1>0) and (j1<11) then

putpixel(15+i1*10,15+j1*10,1);

end;

line(10+i*10,10+j*10,20+i*10,20+j*10);

line(20+i*10,10+j*10,10+i*10,20+j*10);

dec(mykor);

end else begin mypole[i,j]:=2; xod:=1 end;

end;

{ Головна програма }

begin

gd:=CGA; gm:=0; {- 640 x 480}

mmm:

for i := 0 to 11 do

for j := 0 to 11 do

begin

mypole[i,j] := 0; { обнуляємо масив своїх кораблів }

ibmpole[i,j] := 0; { і кораблів комп’ютера }

end;

initgraph(gd,gm,'egavga.bgi');

{ малюємо поле для своїх кораблів }

setcolor(1);

mykor := 10; k := 10; { кількість моїх кораблів}

for i := 0 to 10 do line(20+10*i,20,20+10*i,120); { моє ігрове поле }

for i := 0 to 10 do line(20,20+10*i,120,20+10*i);

{ і для кораблів противника - комп’ютера }

ibmkor := 10; kk := 10; { кількість кораблів ПЕОМ}

for i := 0 to 10 do line(200+10*i,20,200+10*i,120); { ігрове поле ПЕОМ}

for i := 0 to 10 do line(200,20+10*i,300,20+10*i);

ibmkorabel;

i := 1; j := 1;

repeat

Setcolor(2);Rectangle(10+10*i,10+10*j,20+10*i,20+10*j);

ch := readkey;

Setcolor(1);Rectangle(10+10*i,10+10*j,20+10*i,20+10*j);

case ch of

{ left } #75 : dec(i);

{ right} #77 : inc(i);

{ up } #72 : dec(j);

{ down } #80 : inc(j);

#32 : korabel;

end; { case }

if i<1 then i := 10;

if i>10 then i := 1;

if j<1 then j := 10;

if j>10 then j := 1;

until k = 0;

{ А тепер можна і в бій }

xod:=1;

repeat

if (ibmkor<>0) and (mykor<>0) then if xod=1 then myxod else ibmxod;

until (ibmkor=0) or (mykor=0);

if ibmkor = 0 then outtextxy(30,150,'Ви перемогли! ')

else if mykor=0 then outtextxy(30,150,'Ви програли! ');

outtextxy(30,180,'Ще раз? (Y/N)');

ch := readkey;

st:=ch;

if (st = 'Y') or (st = 'y') then goto mmm;

closegraph;

end.

Перед розглядом наступної задачі рекомендуємо спочатку звернутись до §11.3, де описано роботу з файлами, і після ознайомлення зі згадуваними операціями повернутись до даного розділу. Ми вже з вами підійшли до того рівня, коли без операцій з файлами важко обійтись.

Задача 222. (ХІІІ обласна олімпіада з інформатики – м. Житомир, 1999 р.)

Шаховий кінь. У файлi CHESS.DAT задано через пропуск координати стартової А(наприклад, А5) та кiнцевої В (наприклад, С7) клiтин маршруту коня. Вивести у перший рядок файлу CHESS.SOL мiнiмальну кiлькiсть ходiв N для переходу з клiтини А на клiтину В. Наступнi N рядкiв повиннi мiстити один з можливих маршрутiв по мiнiмальному маршруту з клiтини А у клiтину В. Програма повинна мати iм'я CHESS.*

Примiтка: Клiтини шахової дошки нумеруються по горизонталi великими лiтерами латинського алфавiту: A,B,C,D,E,F,G,H, а по вертикалi цифрами 1–8.

Приклад вхiдних та вихiдних даних:

CHESS.DAT CHESS.SOL

A5 C7 4

B3

D4

B5

C7

Розв’язання: Дана задача допоможе нам познайомитись з одним цікавим методом програмування, який відноситься до методів динамічного програмування.

Рис. 1

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

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

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

Рис. 2.

Рис. 3

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

n координати клітини обраховуємо за формулою: k = X·10+Y;

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

Так, для наведеного в умові прикладу значення масивів для клітин обох дощок будуть мати такий вигляд, як зображено на рис. 2, 3. Стартову і кінцеву клітину маршруту виділено більш товстими лініями.

Якщо досягли потрібної клітини, то по другій дошці відшукуємо номери клітин, починаючи з кінцевої, маршруту до стартової клітини, доки значення клітини не стане рівним 1 – це означає, що ми досягли стартової клітини. На кожному кроці координати наступної клітини дошки визначаються за формулами: x = k div 10, y = k mod 10, де k – число, занесене у відповідну клітину дошки. Власне кажучи, це є використання вказівників, але без їх прямого опису. Отримані координати перетворюємо у назви клітин шахової дошки і у зворотному порядку виводимо на екран.

Описаний алгоритм розв’язання реалізовано у приведеній нижче програмі. Звертаємо увагу на необхідність акуратного оформлення перевірки можливості чергового ходу коня (процедура hod). Все інше зрозуміло з тексту програми.

program chess;

const inname = 'chess.dat';

outname = 'chess.sol';

var area, point : array[1..8,1..8] of byte;

namex : array[1..8] of char;

i, j, XStart, YStart, XFine, YFine, X, Y, step : byte;

f : text;

kod : integer;

c : char; st, st1 : string;

flag : boolean;

procedure hod(x, y, step : byte);

begin

if (x - 2 > 0) and (y - 1 > 0) and (area[x-2,y-1] = 0) then

begin

area[x-2,y-1] := step + 1;

point[x-2,y-1] := 10*x + y;

end;

if (x-2 > 0) and (y+1 < 9) and (area[x-2,y+1] = 0) then

begin

area[x-2,y+1] := step + 1;

point[x-2,y+1] := 10*x + y;

end;

if (x+2 < 9) and (y-1 > 0) and (area[x+2,y-1] = 0) then

begin

area[x+2,y-1] := step + 1;

point[x+2,y-1] := 10*x + y;

end;

if (x+2 < 9) and (y+1 < 9) and (area[x+2,y+1] = 0) then

begin

area[x+2,y+1] := step + 1;

point[x+2,y+1] := 10*x + y;

end;

if (x-1 > 0) and (y-2 > 0) and (area[x-1,y-2] = 0) then

begin

area[x-1,y-2] := step + 1;

point[x-1,y-2] := 10*x + y;

end;

if (x-1 > 0) and (y+2 < 9) and (area[x-1,y+2] = 0) then

begin

area[x-1,y+2] := step + 1;

point[x-1,y+2] := 10*x + y;

end;

if (x+1 < 9) and (y-2 > 0) and (area[x+1,y-2] = 0) then

begin

area[x+1,y-2] := step + 1;

point[x+1,y-2] := 10*x + y;

end;

if (x+1 < 9) and (y+2 < 9) and (area[x+1,y+2] = 0) then

begin

area[x+1,y+2] := step + 1;

point[x+1,y+2] := 10*x + y;

end;

end;

procedure back_and_print;

begin

assign(f, outname); rewrite(f);

st := '';

X := XFine; Y := YFine;

repeat

st1 := namex[X]; st := st + st1;

str(Y,st1); St := st + st1;

XFine := point[x,y] div 10;

YFine := point[x,y] mod 10;

x := xfine; Y := Yfine;

until point[x, y] = 1;

writeln(f, step); writeln(step);

kod := length(st) - 1;

while kod >= 1 do

begin

writeln(f,copy(st,kod,2));

writeln(copy(st,kod,2));

dec(kod,2);

end;

close(f);

end;

begin

fillchar(area, sizeof(area), 0);

fillchar(point, sizeof(point), 0);

namex[1]:='A';

for i:=2 to 8 do namex[i] := succ(namex[i-1]);

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

c := st[1];

for i:=1 to 8 do if c=namex[i] then XStart := i;

c := st[2]; val(c,YStart,kod);

c := st[4];

for i:=1 to 8 do if c=namex[i] then XFine := i;

c := st[5]; val(c, YFine, kod);

X := XStart; Y: = YStart;

flag := false; step := 1;

area[xStart, yStart] := step;

point[Xstart, yStart] := 1;

while flag = false do

begin

for i := 1 to 8 do

for j := 1 to 8 do

if area[i,j] = step then hod(i, j, step);

if area[XFine,YFine] > 0

then flag := true

else inc(step);

end;

back_and_print;

end.

Читайте також:
XIII. Використання амортизаційних відрахувань
А. Розрахунки з використанням дистанційного банкінгу.
Альтернативна вартість та її використання у проектному аналізі
Аналіз використання капіталу.
Аналіз використання матеріальних ресурсів
Аналіз використання матеріальних ресурсів.
Аналіз використання обладнання.
Аналіз використання прибутку та резервів його зростання
Аналіз використання робочого часу на підприємстві
Аналіз використання фонду робочого часу.
Аналіз ефективності використання активів (капіталу)
Аналіз ефективності використання каналів розподілу

Переглядів: 432

<== попередня сторінка | наступна сторінка ==>

Двомірні масиви | Вправи та завдання

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.05 сек.