Рекурсия в Паскале

Домашнее задание

Написать программу нахождения НОД двух натуральных чисел, используя алгоритм Евклида и рекурсию

Даны два натуральных числа а и b.

Если а = b, то нод ( а , b)=а.

Если а b, то нод ( а , b)= нод ( а -b , b).

Если а b, то нод ( а , b)= нод ( а , b-а).

Program noddvyxchisel;

var a,b: longint;

function nod(a,b:longint): longint;

begin

If a = b Then

nod := a

else

if ab then nod:= nod(a-b,b)

else nod:= nod(a,b-a)

End;

begin

write(‘a=’);

readln(a);

write(‘b=’);

readln(b);

A:= nod(a,b);

write(‘nod=’,a);

readln;

end.

Задача о Ханойских башнях.

На одном из трех алмазных шпилей надето 64 круглых золотых диска. Диски имеют разные радиусы и расположены на шпиле в порядке убывания радиусов от основания к вершине. Требуется перенести диски с первого шпиля на второй, используя при необходимости и третий шпиль.

При этом неукоснительно должны соблюдаться следующие правила:

• за один раз можно перемещать только один диск;
• больший диск нельзя располагать на меньшем диске;
• снятый диск необходимо надеть на какой-либо шпиль перед тем, как будет снят другой диск.

Трудолюбивые буддийские монахи день и ночь переносят диски со шпиля на шпиль. Легенда утверждает, что когда монахи закончат свою работу, наступит конец света. Можно было бы подсчитать, что для решения задачи с 64 дисками потребуется2 64 – 1 перемещений. Поэтому что касается конца света, то он произойдет по истечении пяти миллиардов веков, если считать, что один диск перемещается за одну секунду. Впрочем, и задачу, и легенду для неё придумал в 1883 году математик Эдуард Люка из колледжа Сен-Луи .

Задача . Составить рекурсивную программу, которая бы решала поставленную выше задачу о Ханойских башнях при количестве дисков, равном n (n = 1, 2, …).

Решение.

Введем имена для шпилей: a, b, c . Пусть hanoi(n,a,b,c) - искомая функция, возвращающая последовательность перемещений дисков с a на b c использованием c по вышеописанным правилам. При n=1 решать задачу мы умеем. Необходимо просто произвести операцию “переместить a на b ”. Предположим, что мы умеем решать эту задачу для n – 1 диска. Переместим n–1 диск с a на с . Далее, переместим один оставшийся диск с a на b и, наконец, переместим n–1 диск с c на b .

Входные данные : количество дисков, находящихся на колышке a;

Выходные данные : последовательность действий;

Шаг0:{определение типа переменных};

Шаг1:{описание процедуры hanoi, которая выводит последовательность действий};

Шаг1.1:{переместить (n-1) дисков с колышка a на колышек b};

Шаг1.2:{переместить n-ый диск с a на c};

Шаг1.3:{переместить (n-1) диск с b на c};

(шаги 1.2-1.3 выполняются рекурсивно);

Шаг2:{основная программа};

Шаг2.1:{ввод количества дисков};

Шаг2.2:{вызов процедуры hanoi}.

0 then begin hanoi(n-1,a,c,b); writeln ('Peremestit disk so sterzhnya ',a,' na sterzhen" ',b); hanoi(n-1,c,b,a); end; end; Begin write ('Vvedite naturalnoe chislo n'); readln (n); a:='a'; b:='b'; c:='c'; hanoi (n,a,c,b); readln; end. " width="640"

Решение задачи в Паскале

Program bahnya;

var n: integer;

a,b,c: char;

procedure hanoi(n: integer;a,b,c: char);

begin

if n0 then

begin

hanoi(n-1,a,c,b);

writeln ('Peremestit disk so sterzhnya ',a,' na sterzhen" ',b);

hanoi(n-1,c,b,a);

end;

end;

Begin

write ('Vvedite naturalnoe chislo n');

readln (n);

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

hanoi (n,a,c,b);

readln;

end.

Домашнее задание

Написать программу вычисления степени с натуральным показателем

Дано: основание степени х

Показатель степени к

Если к=0, тогда степень(к,х)=1,

Иначе

степень (к,х)= х· степень (к-1,х)

Program stepen;

var y: real;

n: integer;

function step(k:integer, x:real): real;

begin

If k = 0 Then

step := 1

else step:= x * step(k-1,x)

End;

begin

write(‘vvedite osnovanie stepeni x=’);

readln(y);

write(‘vvedite pokazatel stepeni k=’);

Readln(n);

write(‘x v stepeni k=’,step(n,y));

readln;

end.

Самостоятельная работа

• Найти сумму цифр числа
• Определить, является ли заданное натуральное число простым
• Найти первую цифру числа
• Перевести натуральное число из десятичной с.с. в двоичную
• Найти сумму элементов целочисленного массива, состоящего из 20 элементов
• Поменять местами значения двух целых чисел
• Упорядочить значения трех переменных а, в, с в порядке их возрастания
• Найти количество цифр в натуральном числе n
• Найти наибольшее из трех данных чисел
• Найти количество положительных чисел среди четырех А, В, С, Д

1 Then dvd (n div 2); begin If n = m Then write (n mod 2); end; prost := true else prost:= (n mod m 0) and prost (m+1, n); End; begin write(‘n=’); begin readln(n); write(‘n=’); dvd (n); readln; Readln(n); end. M:=2; If prost(m,n) then write (n,’prostoechislo’) Else write (n,’sostavnoe’); readln; end. " width="640"

Ответы самостоятельной работы

№ 4

№ 2

program perevod;

Program prostoe;

var n: longint;

var n, m, s: integer;

procedure dvd(n:longint);

begin

function prost(m, n:integer): boolean;

If n 1 Then dvd (n div 2);

begin

If n = m Then

write (n mod 2);

end;

prost := true

else prost:= (n mod m 0) and prost (m+1, n);

End;

begin

write(‘n=’);

begin

readln(n);

write(‘n=’);

dvd (n);

readln;

Readln(n);

end.

M:=2;

If prost(m,n) then write (n,’prostoechislo’)

Else write (n,’sostavnoe’);

readln;

end.