Interface

BEGIN

END

BEGIN

REPEAT

BEGIN

Type

Begin

Var

End.

Writeln(I)

Begin

Var

SI : 0..255;

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

SI := 'А'

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

char(SI) := 'A'

Конструкція приведення типу може знаходитися у всіх позиціях, у яких допускається входження змінної. При цьому слід пам'ятати, що тип даної конструкції завжди визначається ідентифікатором типу перед дужками. Крім того, варто враховувати, що розмір змінної (число байтів, які займає ця змінна) ПОВИНО БУТИ РІВНИМ розміру типу, ідентифікатор якого зазначений у приведенні.

Наведемо ще один приклад. Нехай мається такий опис:

type

Days = (Monday,Tuesay,Wednesday,Thursday,Friday, Satuday,Sunday);

aDay : Days

Num : byte;

Тоді припустимітакі оператори:

Days(Num) := Monday; { Num = 0 }

aDay := Days(Num); { aDay = MonDay }

Num := byte(Friday); { Num = 4 }

Зверніть увагу, що еквівалентом останнього присвоювання буде наступне:

Num := Ord(Friday);

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

aDay := Days(Num+l);

Num := byte(Pred(Friday));

Тип виразу в дужках і ідентифікатор типу перед дужками повинні бути або обидва дискретними типами, або обидва посилковими типами. Якщо один дискретний тип перетвориться до іншого, то таке перетворення може привести до усікання чи збільшення розміру пам'яті, у порівнянні з вихідним значенням. При цьому можлива перевірка на перебування значення в припустимих границях. Наприклад, виконання наступної програми:

li: longint;

I : integer;

LI := 1234567;

I := integer (li+1) ;

приведе до виведення на екран значення -10616 (значення типу longint у процесі приведення до типу integer буде "обрізане").

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

Процедурні типи

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

Найпростіший випадок опису змінної, значеннями якої можуть бути процедури, приведений нижче.

var

Р: procedure;

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

type

Func = function(х,у:integer):integer;

var

Fl, F2 : Func;

Змінним Fl і F2 можуть бути присвоєні як значення функції від двох цілих параметрів, що повертають цілий результат. Наприклад, якщо в цій же програмі мається опис функції

function Add( a,b:integer ) : integer;

begin

Add := a+b

end;

те припустиме присвоювання виду Fl := Add;

Зверніть увагу, що в останньому операторі змінній Fl як значення присвоюється ФУНКЦІЯ Fl; у даному випадку виконання цієї функції не відбувається. Після такого присвоювання мається можливість викликати функцію Add як безпосередньо по її імені, так і за допомогою вказівки змінної F 1. Так, наприклад виконання операторів

WriteLn(Add(l,2))

WriteLn(Fl(l,2))

надрукують число 3.

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

Приклади:

type

Proc = procedure;

BinOperation = function (х, у: real) :real;

OnOperation = function(х:real):real;

Reading = procedure(var F:text;var Elem:char);

Імена формальних параметрів, що вказуються в процедурних типах, грають чисто ілюстративну роль і на зміст визначень ніякого впливу не роблять. Необхідними є тільки ідентифікатори типів параметрів і результатів (для функцій).

Таким чином. Turbo Pascal дозволяє визначати змінні, значеннями яких можуть бути процедури і функції. Для таких змінних припустимі оператори присвоювання, у правих частинах яких знаходяться ідентифікатори інших процедурних змінних чи ідентифікатори підпрограм. Змінна процедурного типу в різні моменти виконання програми може мати як значення різні підпрограми. Такі змінні можна, зокрема, використовувати для виклику підпрограм, що присвоєні цим змінної. Наприклад, якщо в програмі маються наступні описи:

var

Operation : function (х, у : real) :real;

function Add ( a,b:real ) : real;

begin

Add := a+b

end;

function Sub ( a,b:real ) : real;

begin

Sub := a-b

end;

то виконання послідовності операторів

if Condition then

Operation := Add

elseOperation := Sub;

Write(Operation(2.05,3+X))

приведе до присвоєння змінної Operation, у залежності від істинності умови, або функції Add, або функції Sub. Конструкція Operation (2.05, 3+X) викликає активізацію тієї функції, що була присвоєна змінній Operation. Таким чином, у викликах функцій і в операторах процедури, крім ідентифікаторів відповідних підпрограм, можуть стояти імена змінних процедурних типів. Виконання таких конструкцій буде полягати у виклику підпрограм, що були присвоєні цим змінним.

Введення процедурних типів вимагає розв’язку проблеми сумісності, зокрема, сумісності по присвоюванню. У даному випадку питання вирішується досить просто. Процедурні типи, щоб вони були сумісними по присвоюванню, повинні мати однакову кількість формальних параметрів, а параметри на відповідних позиціях повинні бути одного типу. Імена параметрів, як говорилося вище, ніякого значення не мають. Аналогічним чином повинні збігатися типи значень, що повертаються, у випадку функцій.

Використання процедурних типів не обмежується простими процедурними змінними. Як і будь-який інший тип, процедурні типи можуть брати участь у побудові складених типів, наприклад, комбінованих чи регулярних:

type

Proc = procedure ( Т:real );

NoticePtr = ^Notice;

Notice =record

Next : NoticePtr;

Time :real;

Action : Proc

end;

var

NewNotices : array[1..10] of Proc;

Notices : NoticePtr;

з урахуванням цих описів припустимі наступні оператори процедур:

MewNotices[7]((Х+17.5) *2) ;

Notices^.Action(0.25) ;

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

1. Підпрограма, що присвоюється процедурній змінний, повинна бути відтрансльована в режимі "далекого типу викликів". Не поглиблюючи в подробиці системного характеру, досить пояснити, що необхідного ефекту можна досягти, розташувавши перед підпрограмою або групою підпрограм директиву компілятора $F зі знаком '+' (плюс), а наприкінці цієї групи - таку ж директиву зі знаком '-' (мінус), наприклад:

{$?+} function Add ( a,b:real ) : real;

begin

Add := a+b

end;

function Sub ( a,b:real ) : real;

begin

Sub := a-b

end;

{$F-}

Якщо необхідно поширити дію цієї директиви на всю програму, досить помістити одну директиву {$F+} на самому початку тексту.

Еквівалентом директиви компілятора {$F+} є , службове слово far, що, будучи записаним перед блоком підпрограми, задає для неї далекий тип виклику. (Інший можливий тип виклику - "ближній" - задається службовим словом near у тім же місці опису підпрограми). Таким чином, перша процедура з попереднього приклада може бути записана в наступному виді:

function Add ( a,b:real ) : real; far;

begin

Add := a+b

end;

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

var

Func : function ( S:string ) : byte;

function MyLength ( S:string ) : byte; far;

begin .

MyLength := Length(S)

end;

Func := MyLength;

3. Важливим обмеженням є те, що обговорювані підпрограми НЕ МОЖУТЬ БУТИ вкладеними в інші підпрограми.

4. Нарешті, підпрограми, що присвоюються процедурним змінним, не можуть бути підпрограмами спеціального виду, що містять специфікацію interrupt і конструкцію inline.

Зазначені обмеження можуть стати трохи більш зрозумілими, якщо мати на увазі, що на фізичному рівні змінна процедурного типу містить повну адресу початку коду підпрограми в пам'яті (сегмент і зсув). Фактично, процедурна змінна дуже нагадує змінну посилкового типу, тільки замість покажчика на данні вона містить покажчик на код підпрограми. Процедурна змінна завжди займає в пам'яті 4 байти (два слова), причому в першому слові зберігається зсув, у другому - сегмент.

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

program Tables;

type

Func = function (x,y :integer) : integer;

function Add ( a,b:integer ) : integer; far;

begin

Add := a+b

end;

function Mult ( a,b:integer ) : integer; far;

begin

Mult := a*b

end;

procedure MakeTable ( W,H:integer; Operation:Func );

var

i, j : integer;

begin

{ Формуємо заголовок }

Write (' ':6);

for i:=1 to W do Write(i:5);

WriteLn;

Write(' ':6) ;

for i:=1 to W do Write('-----');

WriteLn;

{ Проводимо обчислення }

for i:=1 to H do

begin

Write(i:5,'|');

for j:=1 to W do Write (Operation(j,i):5) ;

WriteLn

end;

WriteLn

end;

begin { MakeTable }

MakeTable(10,10,Add);

MakeTable(10,10,Mult)

end.

Тіло програми Tables містить два виклики процедури MakeTable, що будує таблиці, використовуючи для обчислень у першому випадку функцію Add (одержуючи таблицю додавання 10×10), а в другому випадку - функцію Mult (одержуючи таблицю множення 10×10).

Необхідно нагадати, що хоча змінні процедурних типів можна передавати як параметри підпрограмам, функції, що повертають значення процедурних типів, НЕ ДОПУСКАЮТЬСЯ.

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

type

IntFunc = function : integer;

F : IntFunc;

N : integer;

function Readint : integer; far;

i : integer;

Read(i);

Readint := i

end;

F := Readint; { приссвоїтизначення процедури )

N := Readint; { присвоїти результат функції }

end.

Перший оператор в основній програмі присвоює значення процедури Readint (її адресу) процедурної змінний F, другий оператор ВИКЛИКАЄ функцію Readint і присвоює отримане значення змінній N. Одержання значення процедури чи виклик функції розрізняються по типу присвоюванної змінної (F чи N).

На жаль, виникають ситуації, коли компілятор з контексту не може визначити бажану дію. Наприклад, у наступному операторі для компілятора неочевидно, повинний він порівняти значення процедури в F зі значенням процедури Readint, чи потрібно викликати процедури F і Readint, а потім порівнятиїх значення:

if F = Readint then Writeln('Рівні');

У подібних випадках вважається, що таке входження ідентифікатора процедури чи функції означає виклик функції, тому результатом даного оператора буде виклик F і Readint і порівняння отриманих результатів. Щоб порівняти значення змінної F зі значенням (адресою) процедури Readint, потрібно використовувати наступну конструкцію:

if @F = @ReadInt then Writein('Рівні');

У випадку застосування до ідентифікатора процедури чи функції операції взяття адреси @ запобігає виклику компілятором процедури і у той же час перетворює аргумент у покажчик. Таким чином, @F перетворить F у нетипізований покажчик (pointer), що містить адресу, а @ReadInt повертає адресу Readint. Два значення-покажчики можна порівняти і визначити, чи посилається в даний момент F на Readint.

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

Turbo Pascal цілком підтримує приведення типів змінних для процедурних типів. Наприклад, з урахуванням наступних описів:

Func = function (X:integer) : integer

function MyFunc ( X:integer ) : integer;

begin

MyFunc := X*X

end;

var

F:func

p:pointer

n:integer

можна побудувати наступні присвоювання:

{ змінній F присвоюється функція MyFunc }

F := MyFunc;

( функція MyFunc викликається через змінну F }

N := F(N);

{ Р одержує покажчик на функцію MyFunc }

Р := @F;

{ функція MyFunc викликається через покажчик Р }

N := Func(P)(N);

{ присвоїти значення процедури в Р змінній F }

F := Func(P);

{ присвоїти значення процедури в F покажчику Р }

Func(P) := F;

{ присвоїти значення покажчика в Р змінної F }

@F := Р;

Зауважимо, зокрема, що оператор одержання адреси @, застосований до процедурної змінної, можна використовувати в лівій частині присвоювання. Зверніть також увагу на приведення типів у четвертому операторі при виклику функції через змінну-покажчик.

Рекурсія

Рекурсивні визначення

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

Приклад 1

Значення функції факторіал задаються виразами: 0!=1, n!=n((n-1)! Вони утворять множину {l,2,3,5,8...}: 0!=1, 1=1-0!, 2=2-1!, 6=3-2! і т.д. Усі його елементи, крім першого, визначаються рекурсивно.

Як бачимо, функція факторіал задається рекурентним співвідношенням порядку 1 і початковим відрізком 0!=1. Узагалі, будь-яке рекурентне співвідношення порядку k разом із завданням перших елементів послідовності являє приклад рекурсивного визначення.

Приклад 2.

Арифметичні вирази з константами і знаком операцій '+' у повному дужковому записі (ПДЗ) задаються таким визначенням:

1) константа є виразом у ПДЗ;

2) якщо E і F є виразами в ПДЗ, то (E)+(F) також є виразом у ПДЗ.

Такими виразами є, наприклад, 1, 2, (l)+(2), ((1)+ (2))+(l). Усі вони, крім констант 1 і 2, визначаються рекурсивно.

Об'єкти, визначені в прикладах 1 і 2, тобто значення функції факторіал і дужкові записи виразів, є рекурсивними.

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

Приклад 3

Змінимо визначення функції факторіал на наступне: n!=n(n-1)! при n>0, 0!=1!. Спочатку значення функції від 1 виражається через її ж значення від 0, що, у свою чергу, — через значення від 1. По такому визначенню так і не довідатися, чому ж дорівнює 1!.

Приклад 4

"У попа був собака, піп її любив, вона з'їла шматок м'яса, піп її убив, у землю закопав і на камені написав, що у попа..." і т.д. ця сумна історія не має кінця, і не можна сказати, що ж саме піп написав на камені.

Приклад 5

"Де ти гроші береш?" — "У тумбочці".— "А там вони відкіля?"— "Дружина кладе".— "А в неї відкіля?"— "Я даю" — "А де ти береш?"— "У тумбочці..."

У цьому старому анекдоті не називається дійсне джерело збереження грошей. Якщо через А, В, С позначити чоловіка, його дружину і тумбочку, то переміщення грошей зображується так: A←C←B←A←... і дійсне джерело грошей залишається невідомим.

Щоб подібна "дурна нескінченність" не виникала в рекурсивному визначенні, повинні виконуватися наступні умови:

1) множина обумовлених об'єктів є частково впорядкованою;

2) кожна спадаюча по цьому упорядкуванню послідовність елементів закінчується деяким мінімальним елементом;

3) мінімальні елементи визначаються не рекурсивно;

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

Неважко переконатися, що визначення з прикладів 1, 2 задовольняють цим умовам, а з приклади 3 – 5 — ні.

Рекурсивні підпрограми

За правилами мови Паскаль, що задає область дії визначень, тіло підпрограми може містити виклики підпрограм, заголовки яких записані вище в тексті програми. Звідси випливає, що підпрограма може містити виклики самої себе — рекурсивні виклики. Виконання такого виклику нічим не відрізняється від виконання виклику будь-якої іншої підпрограми. Підпрограма з рекурсивними викликами називається рекурсивною.

Приклад 6

Напишемо рекурсивну функцію f по такому визначенню функції факторіал: n!=n (n-1)!при n>1, 1!=1(вважається, що n>0).

function f (n:integer):integer;

begin

if n=l then f:=l

else f:=n*f(n-l)

end;

При імітації виконання викликів рекурсивних підпрограм їх локальні змінні позначають так: якщо підпрограма викликана з програми, то її локальна змінна X позначається F.X. При виконанні кожного рекурсивного виклику підпрограми F, зазначеного в її тілі, з'являється нова змінна X. Вона позначається додаванням префікса F. до позначення змінної X у попередньому виклику: F.F.X, F.F.F.X і т.п.

Приклад 7

Найбільший спільний дільник НСД(a,b) натуральних чисел a і b можна обчислити рекурсивно на підставі таких рівностей:

якщо b=0, то НСД(а, b)=a;

якщо a mod b=0, то НСД(a, b)=b;

якщо a mod b>0, то НСД(a,b)=НСД(b, a mod b).

Цьому визначенню відповідає наступна рекурсивна функція обчислення НСД:

function GCD(a,b:integer):integer;

begin

if b=0 then GCD:=a

else

if a mod b=0 then GCD:=b

else GCD:=GCD(b,a mod b)

end.

З рекурсивними підпрограмами зв'язані два важливих поняття — глибина рекурсії і загальна кількість викликів, породжених викликом рекурсивної підпрограми.

Розглянемо перше з них. У прикладі 6 приведена функція обчислення n!. Очевидно, що її виклик з аргументом, наприклад 4, закінчується лише по закінченні виклику з аргументом 3, а той у свою чергу, після виклику з аргументом 2 і т.д. Такі виклики називаються вкладеними. Таким чином, виклик з аргументом 4 породжує ще три вкладених виклики. Узагалі, при виклику цієї функції з аргументом n породжується ще n-1 виклик, і загальна кількість незакінчених викликів досягає n. У такий спосіб глибиною рекурсії виклику підпрограми називається максимальна кількість незакінчених рекурсивних викликів при виконанні її виклику.

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

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

Приклад 8

По властивостях трикутника Паскаля, біноміальний коефіцієнт C(m,n)=l при m≤l чи n=0, чи n=m; у противному випадку C(m, n)=C(m-l, n-l)+C(m-l, n).

Відповідно до цієї рівності напишемо рекурсивну функцію обчислення біноміального коефіцієнта C(m, n) по m, n, де 0≤n≤m:

function C(m, n:integer):integer;

begin

if (m<=l)or(n=0)or(n=m) then C:=1

else C:=C(m-l, n-l)+C(m-l, n)

end;

Як бачимо, кожен виклик, у якому значення аргументів m>l, 0<n<m, породжує два вкладених виклики. У результаті відбувається повторне обчислення тих самих величин. Наприклад, виконання виклику з аргументами (5,2) веде до того, що виклик з аргументами (3,1) виконується двічі, виклики з аргументами (2,1), (1,0) і (1,1) — тричі, а загальна кількість вкладених викликів досягає 18.

Неважко зрозуміти, що чим більше m і чим ближче n до m/2, тим більшим буде загальна кількість вкладених викликів. Ми не будемо точно визначати її залежність від аргументів. Скажемо лише, що при n=m div 2 чи n=m div 2+1 вона більше, ніж 2m/2.

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

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

Алгоритми з поверненням. Розв’язок задачі про рух коня

Особливо інтригує область програмування — задачі так називаного «штучного інтелекту». Тут ми маємо справу з алгоритмами, що шукають рішення не за заданими правилами обчислень, а шляхом проб і помилок. Звичайно процес проб і помилок розділяється на окремі задачі. Часто ці задачі найбільше природно виражаються в термінах рекурсії і вимагають дослідження кінцевого числа підзадач. У загальному вигляді весь процес можна мислити як процес пошуку, що будує (і обрізає) дерево підзадач. У багатьох проблемах таке дерево пошуку росте дуже швидко, ріст залежить від параметрів задачі і часто буває експонентним. Відповідно збільшується і вартість пошуку. Іноді, використовуючи деякі евристики, дерево пошуку вдається скоротити і тим самим звести витрати на обчислення до розумних меж.

Почнемо з демонстрації основних методів на добре відомому прикладі— задачі про хід коня.

Дано дошку розміром n×n, тобто таку, що містить n² полів. Спочатку на поле з координатами х₀, у₀ ставлять коня — фігуру, що переміщується по звичайних шахових правилах. Задача полягає в пошуку послідовності ходів (якщо вона існує), при якій кінь точно один раз побуває на всіх полях дошки (обійде дошку), тобто потрібно обчислити n² — 1 ходів.

Очевидний прийом спростити задачу обходу n² полів — рішити більш просту: або виконати черговий хід, або довести, що ніякий хід не можливий. Тому почнемо з визначення алгоритму виконання чергового ходу. Перший його варіант має такий вигляд

PROCEDURE TryNextMovet

BEGIN

ініціалізація вибору ходу;

REPEAT

вибір чергового кандидата зі списку ходів;

IF підходить THEN

BEGIN

запис ходу

IF дошка не заповнена Тhеn

BEGIN

TryNextMove;

IF невдача Then знищення попереднього ходу

END

UNTIL (був удалий хід) OR(кандидатів більше немає)

ENDTtyNextMove

Якщо ми хочемо описати цей алгоритм більш детально, то потрібно вибрати деяке представлення для даних. Дошку, найпростіше, можна представляти як матрицю, назвемо її h. Уведемо, крім того, тип для значень, індексів:

CONST razmer=100

VAR h: ARRAY [1..razmer, 1..razmer] OF INTEGER

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

h[x, у] = 0: поле (x, y) ще не відвідувалося

h[x,y] = i поле (x,y) відвідувалося на i-му ході.

Тепер потрібно вибрати відповідні параметри. Вони повинні визначати початкові умови наступного ходу і результат (якщо хід зроблений). У першому випадку досить задавати координати :поля :(x,y), звідки роблять хід, і число яке вказує номер ходу (для фіксації). Для результату ж потрібно булевий параметр; якщо він істиний, то хід був можливий.

Які оператори можна уточнити на основі прийнятих рішень? Очевидно, умову «дошка не заповнена» можна переписати як i < n². Крім того, якщо ввести дві локальні змінні u і v для можливого ходу, обумовленого відповідно до правил «стрибка» коня, то предикат «допустимо» можна представити як логічну кон’юнкцію умов, що нове поле знаходиться в межах дошки (l<=u<=n і 1<=v<=n) і ще не відвідувалося (h_uv=0).

Фіксація припустимого ходу виконується за допомогою присвоювання h_uv := i, а скасування — за допомогою h_uv=0. Якщо ввести локальну змінну ql і використовувати її як параметр-результат, при рекурсивних звертаннях до цього алгоритму то ql можна підставити замість «є хід». Так ми приходимо до варіанта

PROCEDURE TRY(I,X,Y:INTEGER; VAR Q:BOOLEAN);

VAR U,V:INTEGER; Q1:BOOLEAN;

BEGIN

ініціалізація вибору ходу;

REPEAT

<U,V> — координати наступного ходу;

IF (U>=1) AND (U<=N) AND (V>=1) AND (V<=N) AND (H[U,V]=0)

THEN

BEGIN

H[U,V]:=I

IF I<N*N THEN

BEGIN

IF NOT Q1

THEN H[U,V]:=0

ELSE Q1:= TRUE

END

END;

UNTIL Q1 OR нема інших кандидатів;

Q:=Q1

END.

Ще один крок деталізації — і одержимо вже програму, цілком написану в термінах нашої основної мови програмування. Помітимо, що до цього моменту програма створювалася зовсім незалежно від правил, що керують рухом коня. Ми цілком навмисне відкладали розгляд приватних особливостей задачі. Тепер самий час звернути на них увага.

Якщо задана початкова пара координат x, у, то для наступного ходу u, v існує вісім можливих кандидатів. На малюнку вони пронумеровані від 1 до 8. Одержувати u, v з x, у дуже просто, досить до останнього додавати різниці між координатами, що зберігаються або в масиві різниць, або в двох масивах, що зберігають окремі різниці. Позначимо ці масиви через dx і dy і будемо вважати, що вони відповідним чином ініційовані. Для нумерації чергового ходу-кандидата можна використовувати індекс k. Подробиці показані в nроrрамі. Перший раз до рекурсивної процедури звертаються з параметрами x і y — координатами поля, з якого починається обхід. Цьому полю повинне бути присвоєне значення 1, інші поля маркіруються як вільні:

h [x0, y0] := 1; try (2, x0, y0, q)

Не можна упускати ще одну деталь. Змінна H[u,v] існує лише в тому випадку коли і u i v лежать в діапазоні індексів 1..n. Тому в умові важливо щоб складова H[u,v] =0 була останньою.

program kings_tour;

uses crt,dos;

const razmer=100;

var i,j,n,nsqr:integer;

q:boolean;

dx,dy:array[1..8] of integer;

h:array[1..razmer,1..razmer] of integer;

procedure try(i,x,y:integer; var q:boolean);

var k,u,v:integer;

q1:boolean;

begin

k:=0;

repeat

k:=k+1;q1:=false;

u:=x+dx[k];v:=y+dy[k];

if (u>=1)and (u<=n) and(v>=1) and(v<=n)and(h[u,v]=0) then

begin

h[u,v]:=i;

if i<nsqr then

begin

try(i+1,u,v,q1);

if not q1 then h[u,v]:=0;

end

else q1:=true

end;

until q1 or (k=8);

q:=q1;

end;

begin

clrscr;

write('Razmer->');readln(n);

dx[1]:=2;dx[2]:=1; dx[3]:=-1;dx[4]:=-2;

dx[5]:=-2;dx[6]:=-1;dx[7]:=1;dx[8]:=2;

dy[1]:=1;dy[2]:=2;dy[3]:=2;dy[4]:=1;

dy[5]:=-1;dy[6]:=-2;dy[7]:=-2;dy[8]:=-1;

for i:=1 to n do

for j:=1 to n do

h[i,j]:=0;

write('i->');readln(i);

write('j->');readln(j);

nsqr:=n*n;h[i,j]:=1;

try(2,i,j,q);

if q then begin

for i:=1 to n do

begin

for j:=1 to n do

write(h[i,j]:3);

writeln;

end;

end

else write('goo!');

end.

Характерною особливістю таких алгоритмів є те, що в них виконуються кроки в напрямку загального розв’язку, і всі ці кроки фіксуються таким чином, щоб пізнше можна було повернутись “всліпу” відкидаючи ті кроки, що не ведуть до загального розв’язку. Такий процес називають відкатом або поверненням (backtraking).

Алгоритми з поверненням. Розв’язок задачі про вісьмох ферзів

Задача про вісьмох ферзів — добре відомий приклад використання методів проб і помилок і алгоритмів з поверненнями. У 1850 r. цю задачу досліджував К. Ф. Гаусс, однак цілком він її так і не вирішив. Це нікого не повинно дивувати. Для подібних задач характерна відсутність аналітичного рішення. Вони вимагають величезної кількості виснажливої роботи, терпіння й акуратності. Тому такі задачі стали майже винятково прерогативою електронних обчислювальних машин, адже їм ці властивості притаманні в значно більшому ступені, ніж людині, нехай і геніальній.

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

PROCEDURE Try(i: INTEGER);

ініціалізація вибору положення i-го ферзя;

вибір чергового положення;

IF безпечне THEN

поставити ферзя

IF i<8 THEN

BEGIN

Try(i+1);

IF невдача THEN забрати ферзя

END

UNTIL удача OR місць більше немає

ЕND;

Щоб йти далі, потрібно зупинитися на якому-небудь представленні для даних. Оскільки із шахових правил ми знаємо, що ферзь б'є усі фігури, що знаходяться на тій же самій вертикалі, горизонталі чи діагоналі, то заключаємо, що на кожній вертикалі може знаходитися один і тільки один ферзь, тому при пошуку місця для i-ro ферзя можна обмежити себе лише i-й вертикаллю. Таким чином, параметр і стає індексом вертикалі, а процес вибору можливого місця розташування обмежується вісьма припустимими значеннями для індексу горизонталі j.

Залишається вирішити питання: як представляти на дошці ці вісім ферзів? Очевидно, дошку знову можна було б представити у виді квадратної матриці, але після невеликих міркувань ми виявляємо, що це значно ускладнило б перевірку безпеки поля. Звичайно, подібне рішення небажане, оскільки така операція виконується дуже часто. Тому хотілося б зупинитися на такому представленні даних, щоб, наскільки це можливо спростило б перевірку. У цій ситуації найкраще робити безпосередньо доступною саме ту інформацію, що дійсно важлива і найчастіше використовується. У нашому випадку це не поля, зайняті ферзями, а відомості про те, чи знаходиться вже ферзь на даній горизонталі чи діагоналі. (Ми вже знаємо, що на кожній k-ій вертикалі (1 ≤ k ≤ і) розташований рівно один ферзь.) Ці розуміння приводять до таких описів змінних:

VAR x: ARRAY [l.. 8] OF INTEGER;

a:ARRAY [1.. 8] OF BOOLEAN;

b: ARRAY [bl.. b2] OF BOOLEAN;

с: ARRAY [cl.. c2] OF BOOLEAN;

де

х_i позначає місце розташування ферзя на i-ій вертикалі;

a_jуказує, що на j-ій горизонталі ферзя немає;

b_k указує, що на k-ій /-діагоналі ферзя немає;

c_k указує, що на k-ій \-діагоналі ферзя немає.

Вибір границь індексів bl, b2, cl, c2 визначається, виходячи зі способу обчислення індексів для b і с, на /-діагоналі у всіх полів постійна сума координат і та j, а на \-діагоналі постійна їхня різниця. Відповідні обчислення приведені в nporpамі. Якщо ми уже визначили дані так , то оператор «Поставити ферзя» перетворюється в такі оператори:

x [і] := j; a [j] := FALSE; b [і + j] := FALSE; c[i-j]:=FALSE

а оператор «Забрати ферзя» у такі:

a [j] := TRUE; b [і + j] := TRUE; з [і - j] := TRUE

Умова «безпечне» виконується, якщо поле з координатами <i,j,> лежить на горизонталі і вертикалі, які ще не зайняті. Отже, йому відповідає логічний вираз:

a[j] and b[i + j] and c[i-J]

На цьому створення алгоритму закінчується; цілком він представлений у програмі.

program ferz;

uses crt;

var a: array[1..8] of boolean;

b: array[2..16] of boolean;

c:array[-7..7] of boolean;

x: array[1..8] of integer;

i:integer;q:boolean;

procedure try(i:integer;var q:boolean);

var j:integer;

begin

j:=0 ;

repeat

j:=j+1;q:=false;

if a[j] and b[i+j] and c[i-j]

then

begin

x[i]:=j;

a[j]:=false;b[i+j]:=false;c[i-j]:=false;

if i<8 then

begin

try(i+1,q);

if not q then

begin

a[j]:=true;b[i+j]:=true;c[i-j]:=true

end;

end

else q:=true;

end;

until q or(j=8);

end;

begin

clrscr;

for i:=1 to 8 do a[i]:=true;

for i:=2 to 16 do b[i]:=true;

for i:=-7 to 7 do c[i]:=true;

try(1,q);

for i:=1 to 8 do write(x[i]:3);

writeln

end.

На мал. приведене отримане рішення x = (l, 5, 8, 6, 3, 7, 2, 4).

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

Таке узагальнення виходить досить легко. Нагадаємо, що формування можливих кандидатів відбувається регулярно. Це гарантує, що жоден кандидат не зустрінеться більш ніж один раз. Така властивість алгоритму забезпечується тим, що пошук йде по дереву кандидатів так, що кожна з його вершин проходиться точно один раз. Це дозволяє, якщо знайдено і належним образом зафіксовано одне рішення, просто переходити до наступного кандидату, пропонованому згаданим процесом систематичного перебору. Загальну схему такого процесу можна «вивести» зі схеми.

PROCEDURE Try(i:INTEGER);

VAR k:INTEGER;

FOR k:=l TO m DO

вибір k-го кандидата;

IF підходить ТНЕN

BEGIN

його запис;

IF i<n THEN Try(i+1) ELSE друк рішення ;

стирання запису

END

END;

Зверніть увагу: через те, що умова закінчення в процесі вибору звелася до одного відношення k = m, оператор повторення зі словом REPEAT заміниться на оператор циклу з FOR. Дивно, що пошук усіх можливих рішень виконується більш простою програмою, чим у випадку пошуку одного єдиного рішення.

Узагальнений алгоритм, відшукує 92 рішення задачі про вісьмох ферзів. Однак принципово різних рішень усього 12.

Спробуйте самостійно розробити програму пошуку всіх розв’язків.

Модулі в Турбо Паскалі

У Турбо Паскалі допускається розбивати програми на частині і зберігати ці частини в окремих файлах на диску. Крім основної програми з'являються так називані модулі, що надають основній програмі чи іншим модулям свої змінні, константи, типи, процедури, функції і т.п. Щоб використовувати модуль у програмі, потрібно вказати його ім'я після uses.

При написанні модуля спочатку описується те, що він надає для загального користування (секція інтерфейсу), а потім – як він улаштований (секція реалізації). Іноді існує секція ініціалізації, де записані дії, що виконуються при підключенні цього модуля. Записується це все так:

unit MyUnit;

(*Интерфейсная секція*)

uses ...;

const ...;

type ...;

procedure ...; {Тільки

function ...; заголовки}