Приклади використання двомірних масивів » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

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

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

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

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

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

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

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

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

    Остання система легко розв’язується поступовою підстановкою значень змінних від останнього рівняння до  першого:  х3 = 4,  х2 = –2,  х1 = 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;
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.

 

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

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

    На кожній клітинці шахівниці розміром M x 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), які дають можливість зібрати найбільше грошей, і в якій хід праворуч здійснюється якомога пізніше на кожній ділянці шляху. Наприклад, для наведеного прикладу:

19

RUR

 

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

 

6

14

19

22

12

11

16

18

19

9

13

18

14

11

23

5

12

17

19

21

 

 

Рис. 1

 

 

 

35

 

 

 

 

29

 

 

 

 

18

 

 

 

 

5

17

34

53

74

 

 

Рис. 2

 

 

 

 

35

66

89

111

123

29

52

70

89

106

18

36

50

64

97

5

17

34

53

74

 

 

   Рис.3

 

 

 

35

66

89

111

123

29

52

70

89

106

18

36

50

64

97

5

17

34

53

74

 

 

  Рис. 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;
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.

 

    Задача 3. (завдання обласної олімпіади 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, де описано роботу з файлами, і після ознайомлення зі згадуваними операціями повернутись до даного розділу. Ми вже з вами підійшли до того рівня, коли без операцій з файлами важко обійтись.

 

    Задача 4. (ХІІІ обласна олімпіада з інформатики – м. Житомир, 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

     A5       C7

 

     CHESS.SOL

     4

     B3

     D4

     B5

     C7

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

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

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

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

  • переглядаємо всі клітини шахової дошки і, якщо в них міститься номер ходу, то відшукуємо всі клітини, у які може піти кінь, і заносимо в них значення номера ходу, який на 1 більше розглядуваного, а на іншій дошці вказуємо координати клітини, з якої ми в неї прийшли;
  • координати клітини обраховуємо за формулою: k = X10+Y;
  • якщо досягли потрібної клітини, то встановлюємо прапорець виходу з подальшого перегляду клітин дошки, у противному випадку збільшуємо номер ходу на одиницю і повторюємо все спочатку.

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

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

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

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

Рис.2


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.

скачать dle 10.4фильмы бесплатно Наступна сторінка » Вправи та завдання Попередня сторінка » Двомірні масиви