015. Последовательность из 0 и 1

(Время - 1 сек., память - 16 Мб)

Рассмотрим последовательности длины N, состоящие из 0 и 1. Требуется написать программу, которая по заданному натуральному числу N определяет количество тех из них, в которых никакие две единицы не стоят рядом.

Входные данные

В единственной строке входного файла input.txt записано число N (1 ≤ N ≤ 1000).

Выходные данные

В единственную строку выходного файла output.txt нужно вывести одно число - ответ на задачу.

Примеры

input.txt

output.txt

1

2

3

2

3

5

Разбор

.

Программа на Паскале

var

  n,i,j,k1,k2,k3,p : integer;

  f1, f2, f3 : array [1..1000] of integer;

begin

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

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

  read(n);

  if n=1 then write(2) else

    if n=2 then write(3) else begin

      f1[1]:=2; k1:=1; f2[1]:=3; k2:=1;

      for i:=3 to n do begin

        p:=0; k3:=k2;

        for j:=1 to k1 do begin

          p:=p+f1[j]+f2[j]; f3[j]:=p mod 10; p:=p div 10 end;

        for j:=k1+1 to k2 do begin

          p:=p+f2[j]; f3[j]:=p mod 10; p:=p div 10 end;

        if p>0 then begin k3:=k3+1; f3[k3]:=p end;

        k1:=k2; f1:=f2; k2:=k3; f2:=f3

      end;

      for j:=k2 downto 1 do write(f3[j]);

    end;

  close(output)

end.

Программа на С

 

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2008-2009 уч. год, 2-й тур

Тематика

Динамическое программирование

Примерная сложность

47%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=465

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 22.05.2012