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

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

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

 
 Ответить  Открыть новую тему 
> Числа Фибоначчи
Shashlyk
сообщение 20.05.2011 8:19
Сообщение #1


Новичок
*

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

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


Доброе Утро! smile.gif
Помогите пожалуйста написать код, для быстрого подсчёта чисел фибоначчи. Мне очень быстро считать до 50000 члена последовательности. Мне кажется, что нужно написать длинную арифметику по основанию k^l.
Первый член последовательности - 1;
Второй член последовательности - 1;
Мне кажется, что нужно на таком примере делать:
{Длинная арифметика} 

const
pow = 9; // длинная арифметика по 9 десятичных чисел
base = round(1e9); // 10^pow

m = 10; // требуемое количество таких чисел
type
long = array [0..m] of integer;
procedure add(var a : long; var b : long);
var i, c : integer;
begin
c := 0;
for i := 0 to m do
begin
c := c + a[i] + b[i];
if c >= base then
begin
a[i] := c - base;
c := 1;
end else
begin
a[i] := c;
c := 0;
end;
end;
assert(c = 0);
end;

Помогите Пожалуйста написать код!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 21.05.2011 5:53
Сообщение #2


Уникум
*******

Группа: Модераторы
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(Shashlyk @ 20.05.2011 9:19) *
Помогите пожалуйста написать код, для быстрого подсчёта чисел фибоначчи. Мне очень быстро считать до 50000 члена последовательности. Мне кажется, что нужно написать длинную арифметику по основанию k^l.
Понятно, откуда ноги растут (недавно была уже тема про это: Винтовки белочехов - правда, не особо успешная)).

Так вот, я думаю, что честный тупой подсчет по числам Фибоначчи тут бесполезен. Если ты пойдешь по этому пути, ты не уложишься в отведенное время (3 сек). Так что, послушай доброго совета: поищи другой способ. Длинная арифметика тут не нужна.

P.S.
Кроме прочего, все быстрые способы вычисления чисел Фибоначчи относятся к их непоследовательному вычислению. Тут же тебе надо (если считать в лоб) вычислить все числа Ф. И в этом случае каждое следующее просто получается по определению как сумма двух предыдущих, и ничего быстрее этого придумать невозможно, уверяю тебя smile.gif.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 



- Текстовая версия 22.06.2025 1:00
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"