Рекурсивное программирование (стр. 4 )

об окончании генерации.

Алгоритм генерации, по сути, есть последовательное

увеличение на 1 четверичного числа, хранящегося в иве-

ивее (см. действия с многозначными числами).

}

program Signs;

uses

Crt;

const

N = 6;

S = 35;

var

I, p: Integer;

c: array [0..(N-1)] of Integer;

procedure WriteOneSign(Sgn: Integer);

begin

case Sgn of

0: Write(‘+’);

1: Write(‘-‘);

2: Write(‘*’);

3: Write(‘/’);

end;

end;

procedure OutputSigns;

var

i: Integer;

begin

for I := 1 to N-2 do

Write(‘(‘);

Write(‘1’);

for I := 1 to N-2 do

begin

WriteOneSign(c[i]);

Write(i+1, ‘)’);

end;

WriteOneSign(c[N-1]);

Writeln(N, ‘=’, S);

end;

begin

ClrScr;

for I := 0 to N-1 do

c[i] := 0;

while c[0] = 0 do

begin

{ Вычисление суммы при текущей комбинации знаков }

p := 1;

for I := 2 to N do

case c[i-1] of

0: Inc(p, i);

1: Dec(p, i);

2: p := p * I;

3: p := p div I;

end;

if p = S then OutputSigns;

{ Следующая комбинация }

Inc(c[N-1]);

I := N-1;

while c[i] = 4 do

begin

c[i] := 0;

Inc(c[i-1]);

Dec(i);

end;

end; { while }

end.

Задача 9 « О скобках»

Поострить все слова длины n>0 в алфавите скобок «(» и «)», представляющие правильные скобочные записи.

Алгоритм состоит в следующем:

Будем рекурсивно строить слова из скобок. Также для соблюдения верности расстановки будем хранить код строки Code: при новой скобке '(' Code увеличивается на 1, а при новой скобке ')' Code уменьшается на 1 (в конце должно выполняться Code = 0). На каждом шаге должно выполняться Code > 0. По сути, на каждом шаге значение Code есть разность количества открывающих и закрывающих скобок.

Пусть на некотором шаге имеем слово S. Пробуем добавить скобки:

'(' - возможно, если до конца полного слова (длины N), возможно будет закрыть все открывающие скобки, т. е. если N - Length(S) > Code; ')' - возможно, если впереди есть хотя бы одна незакрытая открывающая скобка, т. е. если Code > 0. При достижении длины слова, равной N, выводим слово.

program Problem8;

uses Crt;

const

N = 10; { N должно быть четным! }

Var S: String; Code: Integer;

procedure BuildWords;

begin

if Length(S) = N then

begin

if Code = 0 then Writeln(S)

end

else begin

{ '(' }

if N - Length(S) > Code then

begin

S := S + '(';

Inc(Code);

BuildWords;

{ Откат }

Dec(Code);

S[0] := Pred(S[0]); { уменьшение длины слова на 1 }

end;

{ ')' }

if Code > 0 then

begin

S := S + ')';

Dec(Code);

BuildWords;

{ Откат }

Inc(Code);

S[0] := Pred(S[0]); { уменьшение длины слова на 1 }

end;

end;

end;

Задача 10

Дана строка S и набор слов A[1], …, A[n]. Разбить строку S на слова набора всеми возможными способами.

Решение:

Общий алгоритм состоит в следующем. Рекурсивно пробуем разбить последовательно (слева направо) строку S на слова и проверить, чтобы они содержались в наборе и, к тому же, не повторялись.

Решение оформлено в виде рекурсивной процедуры Solve(pos: Integer), которая производит разбиение части строки S, начиная с символа pos+1. Принцип ее работы таков. Пробуем выделять слова S[(pos+1)..(pos+1)], S[(pos+1)..(pos+2)], …, S[(pos+1)..Length(S)]. Каждое такое слово ищем в наборе и проверяем, не использовано ли оно на текущий момент в текущем частичном разбиении. Если все верно, добавляем слово (а, точнее, его индекс) в разбиение и запускаем подпроцедуру.

В задаче приходится много раз искать слова в наборе. Это, явно, гораздо быстрее делать двоичным поиском (за время O(log2N)). Для этого требуется предварительная сортировка набора А[ ]. Но поскольку при сортировке приходится обменивать значения элементов, а обмен строк (по сути, обмен массивов) – дело довольно долгое, вместо этого удобнее сортировать указатели на слова:

A[i] – i-ое слово до сортировки,

p[i] – указатель на i-ое слово после сортировки, фактически значение i-ого слова после сортировки будет A[p[i]].

Например, если вначале A = {‘Z’, ‘A’, ‘CC’}, то после сортировки массив А не изменится но массив p будет выглядеть так: p = {2, 3, 1} (т. к. отсортированный массив должен был быть таким: A = {‘A’, ‘CC’, ‘Z’}).

После сортировки возможен двоичный поиск в наборе. Он оформлен в виде функции FindWord(W: String): Integer, где W – искомое слово. Функция возвращает либо номер искомого слова (т. е. W=A[p[FindWord(W)]]), либо 0, если такого слова нет. Логический массив used[ ] …

program Problem10;

uses

Crt;

const

MaxN = 100;

MaxWordLength = 10;

type

ShortStr = String[MaxWordLength];

var

N, i: Integer;

S: String;

A: array [1..MaxN] of ShortStr;

p: array [1..MaxN] of Integer;

used: array [0..MaxN] of Boolean;

razb: array [0..MaxN] of Integer;

{ Двоичный поиск заданного слова в

отсортированном наборе }

function FindWord(W: String): Integer;

var

L, R, C: Integer;

begin

L := 1;

R := N;

while R - L > 1 do

begin

C := (L + R) div 2;

if A[p[C]] > W then

R := C

else

L := C;

end;

FindWord := 0;

if A[p[L]] = W then

FindWord := L

else

if A[p[R]] = W then

FindWord := R;

end;

{ Сортировка указателей на слова набора }

procedure SortWords;

var

i, j, tmp: Integer;

begin

{ Пузырек ;) }

for j := N-1 downto 2 do

for i := 1 to j do

if A[p[i]] > A[p[i+1]] then

begin

tmp := p[i];

p[i] := p[i+1];

p[i+1] := tmp;

end;

end;

{ Рекурсивная процедура-решение задачи }

{ pos - позиция последнего занятого символа в S }

procedure Solve(pos: Integer);

var

i: Integer;

begin

if pos = Length(S) then

begin

for i := 1 to razb[0] do

Write(A[p[razb[i]]], ' ');

Writeln;

End

else

begin

for i := pos + 1 to Length(S) do

begin

{ Можно ли добавить выделенное слово? }

if not used[FindWord(Copy(S, pos+1, i - pos))] then

begin

Inc(razb[0]);

razb[razb[0]] := FindWord(Copy(S, pos+1, i - pos));

used[razb[razb[0]]] := True;

Solve(i);

{ Откат }

used[razb[razb[0]]] := False;

Dec(razb[0]);

end;

end;

end;

end;

begin

ClrScr;

Readln(S);

Readln(N);

for i := 1 to N do

begin

Readln(A[i]);

p[i] := i;

used[i] := False;

end;

ClrScr;

SortWords;

razb[0] := 0;

used[0] := True;

Solve(0);

end.

Задача 11

Задана матрица из натуральных чисел А[1..n, 1..m], n<=m. За каждый проход через клетку (i, j) взимается штраф A[i, j]. Необходимо определить минимальный суммарный штраф, с которым можно пройти из клетки (1,1) в клетку (n, m). При этом из текущей клетки можно переходить в любую из 3 соседних клеток, находящихся в строке с номером, на 1 большим, чем текущий номер строки.

Program problem 11;

Var

N, M, i, j: byte;

A:array [1..100, 1..100] of byte;

MinP: array [1..100, 1..100] of word;

Procedure Solution (i, j: byte);

begin

if i=N then Exit;

{Where can we go from (i, j) ?}

{Down and left}

if (j>1) and (MinP[i+1, j-1] > MinP [i, j] + A[i, j]) then

begin

MinP[i+1, j-1]:= MinP[i, j] + A[i, j];

Solution(i+1, j-1);

end;

{Down}

if MinP[i+1, j] > MinP[i, j] + A[i, j] then

begin

MinP[i+1, j]:= MinP[i, j] + A[i, j] ;

Solution(i+j, j);

end;

{Down and right}

if (j < M) and (MinP[i+1, j+1] > MinP[i, j] + A[i, j] then

begin

MinP[i+1, j+1]:= MinP[i, j] + A[i, j] ;

Solution(i+j, j+1);

end;

end;

Begin

{input data}

Writeln (‘ input N & M …’);

Readln (N, M);

Writeln (‘input matrica A[‘, N, ‘, ‘, M, ‘];

For i:=1 to N do

For j:=1 to M do

Read (A[i, j]);

{Initializing MinP}

FillChar (MinP, SizeOf(MinP), $FF);

{Solution}

MinP[1,1]:=0;

Solution(1, 1);

{Output results}

if MinP[N, M]=$FFFF then

writeln (‘There isn’t path from (1, 1) to (‘, N, ‘ , ‘, M, ‘) .’)

else

writeln (MinP[N, M] + A[N, M]);

End.

Задача 12"Суммы"

Любое целое число N>0 можно представить в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2. Суммы, различающиеся лишь порядком слагаемых, считаются одинаковыми.

Найти K - число способов, которыми можно представить число N в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2.

Например, для N=7 :

7=4+2+1

7=4+1+1+1

7=2+2+2+1

7=2+2+1+1+1

7=2+1+1+1+1+1

7=1+1+1+1+1+1+1

и, следовательно, K=6

Составим подряд несколько разложений:

N=1 N=2 N=3 N=4 N=5 N=6 N=7

1 2 2+1 4+2 4+2+1

1+1 1+1+1 2+2 2+2+1 4+1+1 4+1+1+1

2+1+1 2+1+1+1 2+2+2 2+2+2+1

1+1+1+1 1+1+1+1+1 2+2+1+1 2+2+1+1+1

2+1+1+1+1 2+1+1+1+1+1

1+1+1+1+1+1 1+1+1+1+1+1+1

Введем обозначение

K(i)- количество разложений числа i по условиям задачи

Сразу замечаем, что

K(1)=1, K(2)=2

K(i)=K(i-1), если i - нечетное

(в каждой из строк для соответствующего

предыдущего разложения добавляется +1,

а количество строк не меняется)

K(i) зависит от K(i-1) следующим образом K(i)=K(i-1) + X

То есть количество разложений i-того числа, равно количеству разложений i-1-го числа плюс еще сколько то. Сколько же?

Для примера рассмотрим детальнее разложения при N=6 и отметим те строки, которые перешли в разложение N=6 из разложения N=5 добавлением +1:

N=5 N=6

4+1 4+2

2+2+1 ! 4+1+1

2+1+1+1 2+2+2

1+1+1+1+1 ! 2+2+1+1

! 2+1+1+1+1

! 1+1+1+1+1+1

Теперь выпишем строки, оставшиеся непомеченными, то есть те, которые добавлены по другому закону (как раз и определяющему наше X):

4+2

2+2+2

Интересно, что все они составлены из четных чисел. Поделим все эти числа на 2, получим

2+1

1+1+1

А теперь обращаем внимание, что это как раз разложение числа 3, которое можно получить из числа 6 тоже делением на 2. Итого получаем X=K(i div 2)

А окончательное рекуррентное соотношение имеет вид

K(i-1), если i нечетное и K(i-1)+K(i div 2), если i четное.

Второй тестовый пример

N=7 N=8

4+2+1 8

4+1+1+1 4+4

2+2+2+1 4+2+2

2+2+1+1+1 ! 4+2+1+1

2+1+1+1+1+1 ! 4+1+1+1+1

1+1+1+1+1+1+1 2+2+2+2

! 2+2+2+1+1

! 2+2+1+1+1+1

! 2+1+1+1+1+1+1

! 1+1+1+1+1+1+1+1

Непомеченными остались строки:

8

4+4

4+2+2

2+2+2+2

После деления всех чисел на 2 получим

4

2+2

2+1+1

1+1+1+1

А это как раз и есть разложение числа 4, которое может быть получено из исходного N=8 делением на 2. И тогда полное решение задачи может состоять в рекуррентном заполнении массива K[1..N] и выводе значения K[N].

Можно также заметить, что k[2]=k[1]+k[2 div 2]=k[1]+k[1]=2

То есть k[2] можно вычислять общим порядком. Достаточно задать только начальное значение k[1]. Вот полное (!) решение данной задачи:

program by00m1t2;

var

N,i : longint;

K : array [1..1000] of longint;

begin

assign (input,'sum. in'); reset(input);

assign (output,'sum. out'); rewrite(output);

readln (N);

k[1]:=1;

for i:=2 to N do

if odd(i)

then k[i]:=k[i-1]

else k[i]:=k[i-1] + k [i div 2];

writeln(K[N]);

close (input); close (output);

end.

Задача 13 "Отбор в разведку"

Из N солдат, выстроенных в шеренгу, требуется отобрать нескольких в разведку. Для того, что бы сделать это, выполняется следующая операция: если солдат в шеренге больше чем 3, то удаляются все солдаты стоящие на четных позициях, или все солдаты, стоящие на нечетных позициях. Эта процедура повторяется до тех пор, пока в шеренге останется 3 или менее солдат. Их и отсылают в разведку. Подсчитайте сколькими способами могут быть сформированы таким образом группы разведчиков ровно из трех человек.

Решение.

Обозначим K(N) - количество способов, которым можно сформировать группы разведчиков из N человек в шеренге.

По условию задачи K(1) = 0, K(2)=1, K(3)=1, то есть из трех человек можно сформировать только одну группу, из одного или двух - ни одной.

Рассмотрим теперь случай с произвольным числом N солдат в шеренге.

Если N число четное, то применяя определенную в задаче операцию удаления солдат в шеренге, мы получим в качестве оставшихся либо N div 2 солдат стоящих на четных позициях, либо N div 2 солдат, стоящих на нечетных позициях. А общее количество способов можно найти по формуле: K(N) = 2 * K(N div 2) (если N четное). Количество способов сформировать группу разведки из солдат, оставшихся на четных позициях плюс количество способов сформировать группу разведки из солдат, оставшихся на нечетных позициях. Если N число нечетное, то у нас останется либо N div 2 солдат стоявших на четных позициях, либо (N div 2)+1 солдат, стоявших на нечетных позициях. А общее количество способов можно найти по формуле: K(N) = K(N div 2) + K((N div 2)+1) (если N нечетное)

Таким образом, рекуррентное соотношение имеет вид: / 0, если N=1 или N=2, K(N) = 1, если N=3, K(N) = 2* K(N div 2), если N - четное, K(N) = K(N div 2) + K((N div 2)+1), если N – нечетное.

Применив рекурсивное вычисление рекуррентной величины K(N), получаем алгоритм:

{$m 65520,0,0}

program problem13;

var N : longint;

function K(N:longint):longint;

begin

if N<3

then K:=0 else if N=3

then K:=1

else if odd(N)

then K:= K(N div 2) + K(N div 2 + 1)

else K:= 2 * K(N div 2);

end;

begin

assign(input,'input. txt'); reset(input);

assign(output,'output. txt'); rewrite(output);

read(N);

writeln(K(N));

close(input); close(output);

end.

Список литературы

1. , Марченко в среде TURBO PASCAL 7.0. – М.: Бином Универсал, 1998.

2. , , Кузьмич для персональных компьютеров. – Мн.: Вышэйшая школа, 1991.

3. , Бушмелева по Турбо Паскалю. - Киров, 1997.

4. Долинский . Общие сведения о рекуррентных соотношениях. – Гомель, 2005.

5. Журнал «Репетитор» № 9. – Мн:, 2001.