IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Задача (Фибоначчи)
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


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


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

Спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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

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


Гость






Мне кажеться, что extended подойдёт, так как n <= 907.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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 !!!
Убедился? Забудь раз и навсегда о точном вычислении значений (а здесь надо именно точное, цифра в цифру, а не примерное) с использованием вещественных чисел.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Понятно, всё сделал, сдал (использовал int64)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Ну да, для таких случаев надо долгую арифметику делать, но обошолся и без smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






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


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


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


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.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 7:12
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name