Некоторые задачи, где можно применить рекурсию

Предыдущая 1 2 3 4 5 6 789 10 11 12 Следующая

Задача 1. Вычисление факториала целого положительного числа n.

Для решения будем использовать равенства 0!=1, n!=n·(n-1)!

procedure factorial (n: integer; var fact: integer); {положить fact равным факториалу числа y} begin if n=1 then begin fact:=1; end else begin {n>1} factorial (n-1, fact); fact:= fact*n; end; end; С использованием процедур-функций можно написать так: function factorial (n: integer): integer; begin if n=1 then begin factorial:=1; end else begin {n>1} factorial:= factorial (n-1)*n; end; end; Обратите внимание на некоторую двойственность использования имени factorial внутри описания функции: оно обозначает как переменную, так и вызываемую рекурсивно функцию. К счастью, в нашем случае они различаются по скобкам после имени, но если бы функция была без параметров, то дело было бы плохо. (Стандартная, но трудно находимая ошибка возникает, если автор полагает, что он использует значение переменной, а компилятор в этом месте видит рекурсивный вызов.)

Задача 2. Написать рекурсивную функцию вычисления xⁿ, где n 0.

Для решения будем использовать равенства xⁿ= 1, при n = 0, и xⁿ=x·x^n-1, при n>0.

Function pow (x:real; n: byte):real;begin if n=0 then pow:=1 else pow:=x*pow(x,n-1);end;

Задача 3. Ханойские башни.
Когда-то в Ханое стоял храм и рядом с ним три башни (столба). На первую башню надеты 64 диска разного диаметра: самый большой - внизу, а самый маленький - вверху. Монахи этого храма должны были перенести все диски с первого столба на третий, соблюдая следующие правила:

1). можно перемещать только по одному диску;

2). больший диск нельзя класть на меньший;

3). снятый диск нельзя отложить, его необходимо сразу надеть на другой столб.

Предположим, с первого столба А надо перенести на третий С n дисков. Диски пронумерованы в порядке возрастания их диаметров. Предположим, что мы умеем переносить n-1 дисков. В этом случае n дисков перенесем посредством следующих шагов:

1). верхние n-1 дисков перенесем с первого на второй, пользуясь свободным третьим столбом;

2). последний диск наденем на третий столб;

3). n-1 дисков перенесем на третий, пользуясь свободным первым столбом.

Аналогичным образом можно перенести n-1, n-2 и т.д. дисков. Когда n=1, перенос осуществляется непосредственно с первого столба на третий.

Var a,b,c: char; n: integer;Procedure Move (n:integer; a,b,c: char);begin if N>=1 then begin move(n-1,a,c,b); Write(a,'-->',c,' '); move(n-1,b,a,c); end;end;BEGIN write('введи количество колец'); readln (n); move (n,'1','2','3');END. Напишем рекурсивную процедуру перемещения i верхних колец с m-го стержня на n-й (предполагается, что остальные кольца больше по размеру и лежат на стержнях без движения). procedure move(i,m,n: integer); var s: integer; begin if i = 1 then begin writeln ('сделать ход', m, '->', n); end else begin s:=6-m-n; {s - третий стержень: сумма номеров равна 6} move (i-1, m, s); writeln ('сделать ход', m, '->', n); move (i-1, s, n); end; end; (Сначала переносится пирамидка из i-1 колец на третью палочку.После этого i-е кольцо освобождается, и его можно перенести куда следует. Остается положить на него пирамидку.)

Задача 4. Вывести все сочетания из n по k.

При вводе задается набор символов в виде строки. Длина строки len = n. Затем вводится число k.

type stroka = string;var s,ss :stroka; k,n,ii :byte; num,count :integer;procedure cmn(q:stroka;i,j:byte);label 1;var len :integer; Ch :char;begin while count<=n do begin q:=s[j]; count:=count+1; {в стек заносятся элементы по одному} cmn(q,1,j+1); end;1: len:=length(q); if len<k then begin if j+i<=n then cmn(q,i+1,j); end; if (len<k) and (j+i<=n) then begin if q[len]<>s[j+i] then begin q:=q+s[j+i]; goto 1; end; end; if length(q)=k then begin Writeln(q,':',num); num:=num+1; end;end;BEGIN ClrScr; num:=1; Write('Элементы? '); Readln(s); n:=length(s); Write('Сколько элементов ? '); Readln(k); count:=1; cmn('',1,1);END.

Задача 5. Перечислить все способы расстановки n ферзей на шахматной доске n×n, при которых они не бьют друг друга.

Const N=8;Type YesHor = array[1..N] of boolean; {занятость горизонтали, где индекс массива номер горизонтали} YesD1 = array[-(N-1)..(N-1)] of boolean; {номер диагонали определяется разностью индексов квадратной матрицы i-j, а диагонали параллельны главной диагонали матрицы} YesD2 = array[2..2*N] of boolean; {номер диагонали определяется суммой индексов i+j, а диагонали параллельны вспомогательной} ferz = array[1..N] of integer; {индекс - номер ферзя, то есть номер вертикали}Var x :ferz; a :yeshor; b :yesD1; c :YesD2; Count :integer; {номер варианта расстановки ферзей}Procedure Print;var k:integer;begin inc(Count); for k:=1 to N do Write(x[k],'..'); Write(Count); Writeln; if (Count mod 24)=0 then Readln;end;

Procedure Try(i:integer);

Var

j:integer;

begin

for j:=1 to N do

if a[j] and b[i-j] and c[i+j] then {если клетка не бьется, то}

begin

x[i]:=j; {то ферзю i устанавливается номер горизонтали j}

a[j]:=false; b[i-j]:=false; c[i+j]:=false; {соответствующие

горизонтал, и две вертикали становятся занятыми}

if i<n then Try (i+1) else print; {если это не последний

ферзь, то пытаемся поставить следующий ферзь, иначе распечатка варианта}

a[j]:=true; b[i-j]:=true; c[i+j]:=true; {если нет небитого

поля для данного ферзя, то предыдущая занятая позиция освобождается (отход

назад) и все повторяется}

end;

Procedure Init;

begin

ClrScr; Count:=0;

FillChar(a,sizeof(a),1); FillChar(b,sizeof(b),1); FillChar(c,sizeof(c),1);

{Все элементы логических массивов a,b,c становятся TRUE (1), то есть клетки

доски не находятся под боем}

FillChar(x,sizeof(x),0); {все ферзи вне доски, то есть все x[i]=0}

end;

BEGIN

Init; {устанавливаем все первоначальные данные}

Try(1); {выполняем расстановку}

END.

Предыдущая 1 2 3 4 5 6 789 10 11 12 Следующая

Не нашли, что искали? Воспользуйтесь поиском по сайту: