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 4+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
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
