Последовательность чисел Фибоначчи образуется так: первый и второй члены...

Question

Последовательность чисел Фибоначчи образуется так: первый и второй члены последовательности равны единице, каждый следующий член равен сумме двух предыдущих. (1,1,2,3,5,13...).Дано натуральное число n. n>=3. а)Найти k-й член этой последовательности; б)Для заданного n определить верно ли, что сумма первых n-членов последовательности есть четное число. Помогите, нужно составить программу для решения данных задач!

Answer 1

var

k : byte;
arr : array of int64;
function Fn (c : byte) : int64;
begin
if arr[c - 1] <> 0 then
begin
Fn := arr[c - 1];
exit;
end;
if c < 3 then Fn := 1
else Fn := Fn (c - 1) + Fn (c - 2);
arr[c - 1] := Result;
end;

begin
read (k);
setlength (arr, k);
writeln (Fn (k));
end.

var
n : byte;
arr : array of int64;

tmp : int64;
function Fn (c : byte) : int64;
begin
if arr[c - 1] <> 0 then
begin
Fn := arr[c - 1];
exit;
end;
if c < 3 then Fn := 1
else Fn := Fn (c - 1) + Fn (c - 2);
arr[c - 1] := Result;
end;

begin
read (n);
setlength (arr, n);
tmp :=  (Fn (n));

tmp := 0;

for i := 1 to n do

  tmp := (tmp + arr[i]) mod 2;

if tmp = 1 then writeln ('No') else writeln ('Yes');

end.

 

Это нисходящее динамическое программирование. В массиве Arr храняится сами числа. Рекурсивная функция Fn (n) возвращает N-ое число. В б) мы сначала просчитываем n чисел (то есть считаем число n, так как для него нужны все предыдущие), а потом ищем их сумму. Так как числа могут быть большими, то мы берем сразу их остаток от деления 2 во избежание преполнения.