Числа Фиббоначи, рекурсия с условием

@Olya Koroleva · Регистрация: 22.11.2017

Author24 — интернет-сервис помощи студентам

Всем привет, уже три дня ломаю голову над такой задачкой, помогите пожалуйста...

"Проверьте, может ли число S быть суммой некоторого числа первых членов последовательности Фибоначчи."

Я сделала вот так...

Pascal

function fib(n:integer):integer;
begin
  if (n=1) or (n=2) then
    fib := 1
  else fib := fib(n-1) + fib(n-2);
end;
 
function check_fib(a : integer):boolean;
var n, sum : integer;
begin
  n := 1;
  sum := 0;
  while sum < a do begin
    sum := sum + fib(n);
    n := n + 1;
  end;
  check_fib := sum - a=0;   
end;
 
var
  s, i : integer;
begin
  readln(s);
  writeln(check_fib(s));
end.

Мой вариант рабочий, но в нём происходит очень много рекурсий и поэтому он не эффективный, помогите пожалуйста его оптимизировать

@кот Бегемот · 23.11.2017, 01:25

Вот так можно:

Pascal

var
a:array[1..10000]of longint;
i,s,rez:integer;
begin
readln(s);
a[1]:=1;
a[2]:=1;
rez:=0;
i:=0;
while rez<s do
begin
inc(i);
if i>2 then a[i]:=a[i-1]+a[i-2];
rez:=rez+a[i];
end;
if rez=s then writeln('yes')else writeln('no');
end.

А можно и без массива, меняя значения чисел Фибоначчи для вычисления очередного числа.

@Cyborg Drone · 23.11.2017, 12:32

Сообщение от кот Бегемот

Pascal

2	a:array[1..10000]of longint;

Оптимистично. В longint помещаются числа Фибоначчи до 46 включительно. А сумма - до 44 включительно. Сумму можно и не находить, поскольку

$https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> \sum_{i=1}^{n}F_i\,=\,F_{n+2}\,-\,1<br />$

Для вычисления числа Фибоначчи можно отвести две переменные, а не три, пользуясь тем, что

$https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> F_i\,=\,F_{i-1}\,+\,F_{i-2};\ \ \ F_{i-1}\,=\,F_i\,-\,F_{i-2}<br />$

Pascal

var n, f, t: longint;
begin
  write('n = ');
  readln(n);
  t := 1; //F[2];
  f := 2; //F[3];
  while f <= n do
    begin
      f := f + t;
      t := f - t
    end;
  writeln(n, ' is sum of Fibonacci sequence: ', f - 1 = n);
  readln
end.

Если ввести n, большее чем F₄₆+2=1836311905, то в программе возникнет переполнение. При необходимости можно ввод n дополнить соответствующей проверкой.

Можно также применить формулу Бине, но для этой задачи это, по-моему, лишнее.

Ещё известно, что число, например, k, является чилом Фибоначчи тогда и только тогда, когда одно из чисел 5k²+4 или 5k²-4 является полным квадратом. То есть, в принципе, достаточно проверить, является ли целым числом корень квадратный из 5(n+1)²+4 или из 5(n+1)²-4, и всё. Циклы и рекурсия в этом случае, естественно, не требуются. Только вот число, которое можно проверить, для типа longint будет не более 20724. Такое ограничение, по-моему, является слишком большой платой за простоту вычислений. Если применить более ёмкие типы данных, или длинную арифметику, то, возможно, об этом ограничении можно будет забыть.

	23.11.2017, 12:32