Задача
Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом
Входные данные
Во входном файле записано целое число N (1<=N<=100)
Выходные данные
В выходной файл вывести количество искомых последовательностей
Например:
SEQUENCE.IN
5
SEQUENCE.OUT
13
Идея
Динамическое программирование - длинная арифметика
Комментарии
Назовем последовательность из 0 и 1, в которой никакие две единицы не стоят подряд хорошей. Обозначим число хороших последовательностей длины k через Fk
Попытаемся теперь выразить количество хороших последовательностей длины k через количества хороших последовательностей меньшей длины. Для этого рассмотрим, как можно построить хорошую последовательность длины k. Если последним символом этой последовательности выбрать 0, то в качестве предыдущих k-1 символов можно взять произвольную хорошую последовательность длины k-1. А таких последовательностей Fk-1. Если же последним символом выбрать 1, то на (k-1)-ом месте 1 стоять не может, а значит там стоит 0. Тогда в качестве первых k-2 символов можно взять любую хорошую последовательность длины k-2, а их количество Fk-2. Таким образом, находим, чтo Fk=Fk-1 +Fk-2
Получив эту рекуррентную формулу, нам остается задать первые два значения рассматриваемой последовательности (F0=1, F1=2), а затем в цикле последовательно вычислить числа F2,F3,...,FN
Можно вычислять числа Fk и не в цикле, а с помощью рекурсивной функции, основанной на выведенной нами формуле. Однако этот алгоритм неприемлем в данной задаче, т.к. он не сможет за разумное время закончить свою работу. (Заметьте: значение FN-2 эта функция будет вычислять 2 раза - при вычислении FN и FN-1, значение FN-3 - 3 раза, a F2 - число раз, по порядку равное FN)
Рекурсивную функцию, однако, использовать все же можно, если запоминать уже вычисленные значения (например, в статическом массиве) и никогда не вычислять их заново. Этот прием особенно эффективно применять в тех случаях, когда в процессе вычислений числа FN нам нужны не все предыдущие значения FK, а только некоторые из них, причем заранее сложно указать, какие именно.
Отметим также, что при указанных в условии задачи ограничениях необходимо использовать длинную арифметику, т.к. число F100 имеет в десятичной записи 21 цифру
Замечание
Рекуррентная формула, полученная нами при решении этой задачи, совпадает с формулой, определяющей числа Фибоначчи. Это объясняет тот факт, что FN совпадает с (N+1)-ым числом Фибоначчи
Решение
{$A+,B-,D+,E-,F-,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 65520,0,655360}
program sequence;
const
lenMax = 100;
pow = 10000;
type
tNumber = record
len : integer;
num : array[1..lenMax] of word;
end;
var
f1, f2, temp : tNumber;
i, N : integer;
procedure add(var a : tNumber; const b : tNumber);
var
r : word;
i : integer;
begin
r := 0;
if a.len < b.len then
a.len := b.len;
for i := 1 to a.len do begin
inc(r, a.num[i]+b.num[i]);
a.num[i] := r mod pow;
r := r div pow;
end;
if r > 0 then begin
inc(a.len);
a.num[a.len] := 1;
end;
end;
procedure print(const a : tNumber);
var
i : integer;
j : longint;
begin
if a.len = 0 then
write(0)
else begin
write(a.num[a.len]);
for i := a.len-1 downto 1 do begin
j := a.num[i]+ord(a.num[i]=0);
while j*10 < pow do begin
write(0);
j := j*10;
end;
write(a.num[i]);
end;
end;
writeLn;
end;
Begin
assign(input, 'sequence.in');
reSet(input);
assign(output, 'sequence.out');
reWrite(output);
read(N);
fillChar(f1, sizeOf(f1), 0);
fillChar(f2, sizeOf(f2), 0);
f1.len := 1; f1.num[1] := 2;
f2.len := 1; f2.num[1] := 1;
for i := 2 to N do begin
temp := f1;
add(f1, f2);
f2 := temp;
end;
print(f1);
close(input);close(output)
End.
|