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

BEGIN

BEGIN

BEGIN

END

BEGIN

Begin

Read(i);

Readint:= i

end;

begin

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 цілком підтримує приведення типів змінних для процедурних типів. Наприклад, з урахуванням наступних описів:

type

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,6,...}: 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=O)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 вона більше, ніж 2^m/2.

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

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

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

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

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

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

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

PROCEDURETryNextMovet

BEGIN

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

REPEAT

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

IF підходить THEN

BEGIN

запис ходу

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

BEGIN

TryNextMove;

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

END

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-уe ході.

Тепер потрібно вибрати відповідні параметри. Вони повинні визначати початкові умови наступного ходу і результат (якщо хід зроблений). У першому випадку досить задавати координати _:поля:(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 [xO, yO]:= 1; try (2, xO, yO, 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. цю задачу досліджував К. Ф. Гаусс, однак цілком він її так і не вирішив. Це нікого не повинно дивувати. Для подібних задач характерна відсутність аналітичного рішення. Вони вимагають величезної кількості виснажливої роботи, терпіння й акуратності. Тому такі задачі стали майже винятково прерогативою електронних обчислювальних машин, адже їм ці властивості притаманні в значно більшому ступені, ніж людині, нехай і геніальній.

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

PROCEDURETry (i: INTEGER);

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

REPEAT

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

IF безпечне THEN

BEGIN

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

IF i<8 THEN BEGIN

Try(i+l);

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

с: 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

його запис;

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

Дата добавления: 2014-12-16