Задача
Требуется подсчитать количество последовательностей длины 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.


© Особенности национальных задач по информатике