Задача (Фибоначчи) Опции

[Witaliy]

Нужно найти элемент с номер 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]

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

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

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

[Гость]

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

[volvo]

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]

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

[volvo]

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

[Witaliy]

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

[TarasBer]

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

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

[volvo]

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

[DarkWishmaster]

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

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]

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

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