Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задача (Фибоначчи)

Автор: Witaliy 25.02.2009 20:15

Нужно найти элемент с номер N (1 <= N <= 907) строки. Строка будуеться так: до конца строки последовательно дописывается сдедуеще число Фибоначчи. Получаем:
1123581321...

Например: 6
Выходные даные : 8
Ещё
1
Выход: 1

мой код:

{$n+}
program my;
var  a: array[1..1100] of char;
     l,i : integer;
     s : string;
     arr : array[1..3] of extended;
     n : longint;
begin
l := 2;
a[1] := '1';
a[2] := '1';
arr[1] := 1;
arr[2] := 1;
while l < 1100 do
 begin
 arr[3] := arr[2]+arr[1];
 arr[1] := arr[2];
 arr[2] := arr[3];
 str(arr[3]0,s);
  for i := 1 to length(s) do
   a[l+i] := s[i];

 l := l+length(s);
 end;
readln(n);
writeln(a[n]);
end.

Но он хорошо не работает.

Спасибо.

Автор: volvo 25.02.2009 20:42

Цитата

Но он хорошо не работает.

Для решения этой задачи не надо ни массивов, ничего подобного... Все, что надо - это находить очередное число Фибоначчи, и вычислять его длину (Сколько цифр оно содержит. Напиши для этого функцию). Вычислил, если длина меньше N, значит N уменьшаешь на эту величину, если нет, то значит ты добрался до числа, которое содержит искомую цифру. ТОЛЬКО его переводи в строку (а можно и без этого обойтись), и находи N-ый элемент строки. Особые случаи (N=1 и N=2) обрабатываются отдельно.

P.S. Похоже, что встроенных целочисленных типов, способных работать с такими значениями, в Турбо-Паскале нет... Так что, без длинной арифметики не обойтись.

Автор: Гость 25.02.2009 21:31

Мне кажеться, что extended подойдёт, так как n <= 907.

Автор: volvo 25.02.2009 21:49

Extended? Ну, давай посмотрим... Можно уточнить, при использовании Extended, какое будет число Фибоначчи №82? Тебе придется его вычислить, даже 90-ое придется вычислять при N = 900, например. Но... Уже в 82-м Extended дает ошибку (вычислены числа Фибоначчи с номерами от 75 до 84 и использованием типов QWord и Extended):

  75              5527939700884757              5527939700884757
  76              8944394323791464              8944394323791464
  77             14472334024676221             14472334024676221
  78             23416728348467685             23416728348467685
  79             37889062373143906             37889062373143906
  80             61305790721611591             61305790721611591
  81             99194853094755497             99194853094755497
  82            160500643816367088            160500643816367090 !!!
  83            259695496911122585            259695496911122590 !!!
  84            420196140727489673            420196140727489670 !!!

Убедился? Забудь раз и навсегда о точном вычислении значений (а здесь надо именно точное, цифра в цифру, а не примерное) с использованием вещественных чисел.

Автор: Witaliy 25.02.2009 22:05

Понятно, всё сделал, сдал (использовал int64)

Автор: volvo 25.02.2009 22:15

int64 - тоже не панацея... Для 90-го числа Фибоначчи он уже переполняется, и выдает отрицательное значение. Даже положительного QWord-а хватает только на 91 число. А если больше понадобится при N = 907? Будет глючить...

Автор: Witaliy 25.02.2009 22:38

Ну да, для таких случаев надо долгую арифметику делать, но обошолся и без

Автор: TarasBer 25.02.2009 22:56

Цитата(volvo @ 25.02.2009 18:15)

Там надо найти не 907е число, а 907ю цифру в последовательности из чисел Фибоначчи. Так что всё на так страшно.

Автор: volvo 25.02.2009 23:30

Ага... Только 907 цифра находится в 92-м числе, если я не ошибаюсь... Так что довольно неприятно может быть...

Автор: DarkWishmaster 30.03.2011 3:30

Вот способ для получения чисел Фибоначчи, может будет интересно:


Uses Crt;
const Phi=1.618033;
var i,n:byte; Fib:longint;
begin ClRScr;
readln(n);
Fib:=1;
i:=1;
while i<=n do begin
   if (i=1) or (i=2) then Fib:=1 else
    Fib:=round(Fib*Phi);
write(Fib,' ');
inc(i);
end;
readln;
end.

Автор: TarasBer 30.03.2011 13:34

Ты считаешь число Фибоначчи по известной формуле, но возводишь в степень число, известное только до 6 знаков.
Ты уверен, что погрешность не проявится?

Кстати, тип longint для данной задачи (из первого сообщения этой темы) бесполезен.