N – 1 A – C(B)

A – B

N – 1 C – B(A)

Розв’язання мовою Паскаль:

Procedure Hanoi (disk: byte; Start, finish, Help:char);

Begin

if disk=1

then writeln (Start, ‘?’, Finish)

Else begin

Hanoi (disk-1, Start, Help, Finish);

Hanoi (1, Start, Finish, Help);

Hanoi (disk-1, Help, Finish, Start);

end;

end.

Формальні параметри процедури:

disk – кількість дисків, що пересуваються;

start – початковий стрижень;

finish – результуючий стрижень;

help – допоміжний стрижень.

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

Приклад 1. Обчисліть значення функції n!. Дивіться в пункті 5.4 §5 (Частина І.)

Приклад 2. Отримайте n перших чисел Фібоначчі.

Алгоритм-функція має вигляд:

Розв’язання легко пояснити на такому прикладі:

1) f1=1; f2=1

2) f3=f1+f2=1+1=2

3) f4=f2+f3=1+2=3,

Але якщо зробити заміну f1 на f2 а f2 на f3

(f1:=f2; f2:=f3), то f4:=f1+f2

Приклад 3. Обчислити степінь числа х^у, де х і у – цілі числа.

Алгоритм-функція має вигляд:

АЛГ ціл st (ціл х, у)

ПОЧ ціл R

R:=1

поки y>0

пц

якщо y mod 2 =1

то R:=R*x

Все

y:=y div 2

x:=x*x

кц

st:=R

КІН

Розв’язання отримано з таких міркувань:

а) якщо степінь парний, xⁿ можна отримати так: xⁿ=x^{n div 2}*x^{n div 2};

б) якщо степінь непарний, то xⁿ=x^n-1*x.

Тоді функція піднесення числа х до степеня у мовою Паскаль має вигляд:

Function Pow (x: real; y: byte): real;

var R: real;

Begin

R:=1;

while y>0 do

Begin

if y mod 2=1

then R:=R*x;

x:=x*x;

y:=y div 2;

end;

Pow:=R;

End;

Приклад 4. Знайти найбільший спільний дільник двох чисел.

Алгоритм-функція має вигляд:

АЛГ ціл НСД (ціл a, b)

ПОЧ ціл х, у

x:=a; y:=b

поки x<y

пц

якщо x>y

то x:=x – y

інакше y:=y – x

Все

кц

НСД:=х

КІН

Як було описано вище, оптимальнішим є використання цілочисельного ділення. Алгоритм мовою Паскаль:

Function NSD (a, b: longint): longint;

var c: longint;

Begin

while a mod b<>0 do

Begin

a:=a mod b;

c:=a; a:=b; b:=c;

end;

NSD:=b;

end;

Приклад 5. Знайти суму цифр натурального числа.

Алгоритм розв’язання цього завдання може мати вигляд:

АЛГ Сума цифр нат. числа (ціл n, s)

АРГ n

РЕЗ s

ПОЧ ціл і, m, c

{ підсумовування цифр натурального числа }

m:=dlc(n)

s:=0

для і від 1 до m

пц

c:=int(n/10 i – 1) – int(n/10i)*10

s:=s+c

кц

ДРУКУВАТИ s

КІН

Алгоритм-функція визначення довжини натурального числа (кількості цифр у числі).

АЛГ ціл dlc(ціл n)

ПОЧ ціл і, m

{ знаходження довжини числа }

m:=n

k:=0

поки m>0

пц

m:=int(m/10)

k:=k+1

кц

dlc:=k

КІН

У запропонованому алгоритмі спочатку визначається кількість цифр у числі, а потім у циклі з параметром знаходять суму цифр числа. Але можна знаходити цю суму, не знаючи скільки у числі цифр. Для цього виділяємо останню цифру (n mod 10) і додаємо її до загальної суми, після чого цю цифру відкидаємо (n div 10). Процес повторюється, доки від числа не будуть відкинуті всі цифри, тобто число не стане нулем.

Мовою Паскаль це виглядає так:

Function Sum (n: longint): byte;

var S: byte;

Begin

S:=0;

while n<>0 do

Begin

S:=S+n mod 10;

n:=n div 10;

end;

end.

Поиск по сайту: