Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача (Фибоначчи)
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
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]1.gif0,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
Ну да, для таких случаев надо долгую арифметику делать, но обошолся и без smile.gif
TarasBer
Цитата(volvo @ 25.02.2009 18:15) *

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 для данной задачи (из первого сообщения этой темы) бесполезен.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.