Число Фибоначчи 10^18

@ridikyu · Регистрация: 24.10.2013

Студворк — интернет-сервис помощи студентам

Очень важную роль в математике играет ряд чисел Фибоначчи. Каждое следующее число ряда Фибоначчи можно вычислить как сумму двух предыдущих.

F1 = F2 = 1
Fi = Fi-1 + Fi-2

Для заданного N (1 ≤ N ≤ 10^18) найдите N-ое число ряда Фибоначчи. Так как данное число может быть достаточно большим, выведите его по модулю 1000000007.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
int main(int k, int f)
{
    unsigned long long  Fi, F0, F1;
    int n, i;
    std::cin >> n;
        
    F0 = 0;
    F1 = 1;
    for (i = 2; i <= n; i++)
    {
        Fi = F1 + F0;
        F0 = F1;
        F1 = Fi;
    }
        
        Fi = Fi % 1000000007;
        std::cout << Fi << "\n";
    
 
    return 0;
}

Ни как не могу понять кокой тип данных мне использовать. Помогите пожалуйста.

@_Ivana · 28.11.2014, 21:06

Сообщение от TheFox

Прочитать это

Думаю, с не меньшим успехом можно почитать и это http://mitpress.mit.edu/sicp/chapter1/node15.html (в конце). Но второй вопрос (который поинтереснее) имхо все равно остается открытым

@D_in_practice · 28.11.2014, 21:51

Нашел ошибку:

Сообщение от ridikyu

C++
1
int n, i;//unsigned long long

И интересное решение:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{a}_{n} = {a}_{k+1}*{a}_{n-k} + {a}_{k}*{a}_{n-k-1}, k\in [1; n-2]$

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
 
const unsigned long long N = 1000000007;
 
unsigned long long fi(unsigned long long n){
    
    if (n == 1 || n == 2){
        return 1;
    }else if (n == 3){
        return 2;
    }else{
        unsigned long long k = n/2;
        return (fi(k + 1)*fi(n - k) + fi(k)*fi(n - k - 1))%N;
    }   
}
 
int main(int k, int f)
{
    
    unsigned long long  Fi, F0, F1;
    unsigned long long n, i;
    std::cin >> n;
        
    F0 = 0;
    F1 = 1;
    for (i = 2; i <= n; i++)
    {
        Fi = (F1 + F0)%N;
        F0 = F1;
        F1 = Fi;
    }
        
        std::cout << Fi << "\n";
        std::cout << fi(n) << "\n"; 
    return 0;
}

@ridikyu · 28.11.2014, 22:02 **[ТС]**

D_in_practice, спасибо большое. не прошел только последний тест, он там очень хитрый. Но без него он тоже принимает. Спасибо еще раз.

@D_in_practice · 28.11.2014, 22:05

на самом деле рекурсивный код считает дольше

(ввел большое число),
да и памяти никакой не хватит

@ridikyu · 28.11.2014, 22:14 **[ТС]**

понятн)))

@_Ivana · 28.11.2014, 22:23

D_in_practice, все равно уже лучше, чем было. У меня тоже навскидку считает примерно так же и до стольких же числе, что и у вас. Чтобы посчитал для 10^18 надо действительно подумать, навскидку не скажу.

@ridikyu · 28.11.2014, 22:27 **[ТС]**

_Ivana, D_in_practice все четка сделал. там последний тест, хитро сделанный. не пойми на какие значения проверяет. Может он на ноль проверяет, или на отрицательное число. или еще на что.

@_Ivana · 28.11.2014, 22:32

Ну, во-первых, отрицательные Фибоначчи тоже надо считать - они такие же Фибоначчи как и положительные, только знаки чередуются. А во-вторых, пока до 10^18 не дотягиваем, 10^10 где-то тянем, хотя у нас разные алгоритмы. Похоже, можно еще подумать, периодичность обещанную как-то использовать или еще что. Но это конечно если захотеть добить задачу для любых n вообще, даже не ограниченных 10^18.

ridikyu, было бы хорошо, если бы он выдавал те входные данные, на которых не дает ответ.

@ridikyu · 28.11.2014, 22:35 **[ТС]**

_Ivana, ну это да.

@_Ivana · 28.11.2014, 22:54

ridikyu, попробуйте заменить строчку

C++
1
std::cin >> n;

на

C++
1
std::cin >> n; n %= (2*N);

- если я не ошибся и считает правильно, то должно прожевывать вообще любые n.

@ridikyu · 28.11.2014, 22:58 **[ТС]**

_Ivana, ок попробую. правда чуть позже, сервер с кантестам упал.

@_Ivana · 28.11.2014, 23:16

UPD неправильно считаю новое n, но сам подход верен - надо рассчитать другое n, с которым запускать алгоритм.

Добавлено через 17 минут

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int _tmain(int argc, _TCHAR* argv[])
{   
    unsigned long long Fi, F0, F1;
    unsigned long long n, n1, i;
    std::cin >> n;  
    n1 = n%(2000000016); // волшебное число для числа 1000000007
        
    F0 = 0; F1 = 1;
    for (i = 2; i <= n; i++)
    {
        Fi = (F1 + F0)%N;
        F0 = F1;
        F1 = Fi;
    }
    std::cout << "up to n = " << Fi << "\n";
 
    F0 = 0; F1 = 1;
    for (i = 2; i <= n1; i++)
    {
        Fi = (F1 + F0)%N;
        F0 = F1;
        F1 = Fi;
    }       
    std::cout << "up to n1= " << Fi << "\n";
 
    system("pause");
    return 0;
}

Победа разума над косной материей - волшебное число судя по всему найдено

Проверено на n = 10^10, по идее должно считать для любых n вообще. Осталось только попробовать оптимизировать сам код до любого числа, заменить цикл на что-то подобное двум ссылкам, данным в этом топике - и будет вообще огонь

@ridikyu · 28.11.2014, 23:23 **[ТС]**

_Ivana, ну ты даешь))) спасибо за помощь. Но мне аж стыдно. Когда же я все это смогу сам делать. и понимать!

@_Ivana · 28.11.2014, 23:30

Запустил тест проверки для n=10^11, до самого n пока считает, жду что покажет. Если совпадет, то будет хорошо. А что стыдно - это хорошая мотивация что-то делать и постигать самому. Вот D_in_practice тоже имхо начинал с простого, а упорство и некий хороший перфекционизм в сочетании с подписью дает уже очень неплохие плоды. Особенно по сравнению с другими учащимися кодерами.

ЗЫ ну и если честно, то я не сам из головы все это придумал - благо в наше время есть интернет и там можно найти много интересного, в том числе и по математике и по алгоритмам

@D_in_practice · 28.11.2014, 23:35

_Ivana, мне кажется этот путь не канает, тк, для:

N = 2, период будет = 3
N = 3, период будет = 8
N = 4, период будет = 6
N = 5, период будет = 12+...

с чего Вы взяли, что для
N = 1 000 000 007, период будет = 2 000 000 016

при n = 1 000 000 007 программа считает уже несколько секунд, что уже плохо

интересно что 1 000 000 007 - простое число

@ridikyu · 28.11.2014, 23:36 **[ТС]**

_Ivana, картинку одну видел)) так там статистика проблем при программирование в процентах. больше всего % на придумывание названия для проги и роботы с чужим кодам))))

@_Ivana · 28.11.2014, 23:58

Сообщение от D_in_practice

с чего Вы взяли, что для
N = 1 000 000 007, период будет = 2 000 000 016

пока не досчитает запущенную 10^11, у меня только одно подтверждение этого - 10^10. Понятно, что 2 частных случая ничего не докажут, но мне вот ооочень кажется, что это оно

Пока можете считать это видЕнием

Сообщение от D_in_practice

при n = 1 000 000 007 программа считает уже несколько секунд, что уже плохо

Я и говорил, что параллельно с ограничением потолка надо оптимизировать сам расчет, и уже который раз упоминал про две ссылки тут для этого.

Добавлено через 17 минут
Совпало для 10^11. Сейчас попробую перевести на С оптимизацию расчета - для обещанного огня

@D_in_practice · 29.11.2014, 00:11

для чисел
3
4
15
100
1 000
1 000 000 006
работает

@_Ivana · 29.11.2014, 00:16

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const unsigned long long N = 1000000007;
 
unsigned long long fib(unsigned long long a, unsigned long long b, unsigned long long p, unsigned long long q, unsigned long long n)
{
    if (n==0)   return b%N; else
    if (n%2==0) return fib(a%N, b%N, (p*p+q*q)%N, (q*q+2*p*q)%N, n/2); else
                return fib((b*q+a*q+a*p)%N, (b*p+a*q)%N, p%N, q%N, n-1);
}
 
int _tmain(int argc, _TCHAR* argv[])
{   
    unsigned long long Fi, F0, F1;
    unsigned long long n, n1, i;
    std::cin >> n;  
       
    F0 = 0; F1 = 1;
    for (i = 2; i <= n; i++)
    {
        Fi = (F1 + F0)%N;
        F0 = F1;
        F1 = Fi;
    }
    std::cout << "up to n = " << Fi << "\n";
 
    n1 = n%(2000000016); // волшебное число для числа 1000000007
    F0 = 0; F1 = 1;
    for (i = 2; i <= n1; i++)
    {
        Fi = (F1 + F0)%N;
        F0 = F1;
        F1 = Fi;
    }       
    std::cout << "up to n1= " << Fi << "\n";
 
    std::cout << "fire! n1= " << fib (1, 0, 0, 1, n1) << "\n";
 
    system("pause");
    return 0;
}

А вот это уже настоящий огонь - как и обещал

Для малых чисел любуемся всеми тремя ответами. Для чисел побольше комментируем первый расчет и его вывод - любуемся двумя. А для ощущения огня оставляем только третий расчет - через рекурсивную функцию, впечатляемся скоростью и понимаем, как надо по-хорошему написать эту задачку

@ridikyu · 29.11.2014, 00:21 **[ТС]**

_Ivana, жесть)) буду разбираться. спасиб

Новые блоги и статьи Все статьи Все блоги /
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .

Число Фибоначчи 10^18

Решение

Решение

Решение

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	28.11.2014, 22:02 [ТС]
	D_in_practice, спасибо большое. не прошел только последний тест, он там очень хитрый. Но без него он тоже принимает. Спасибо еще раз. 0

@D_in_practice 343 / 343 / 331 Регистрация: 02.10.2014 Сообщений: 666
	28.11.2014, 22:05
	на самом деле рекурсивный код считает дольше(ввел большое число), да и памяти никакой не хватит 0

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	28.11.2014, 22:14 [ТС]
	понятн))) 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	28.11.2014, 22:23
	D_in_practice, все равно уже лучше, чем было. У меня тоже навскидку считает примерно так же и до стольких же числе, что и у вас. Чтобы посчитал для 10^18 надо действительно подумать, навскидку не скажу. 0

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	28.11.2014, 22:27 [ТС]
	_Ivana, D_in_practice все четка сделал. там последний тест, хитро сделанный. не пойми на какие значения проверяет. Может он на ноль проверяет, или на отрицательное число. или еще на что. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	28.11.2014, 22:32
	Ну, во-первых, отрицательные Фибоначчи тоже надо считать - они такие же Фибоначчи как и положительные, только знаки чередуются. А во-вторых, пока до 10^18 не дотягиваем, 10^10 где-то тянем, хотя у нас разные алгоритмы. Похоже, можно еще подумать, периодичность обещанную как-то использовать или еще что. Но это конечно если захотеть добить задачу для любых n вообще, даже не ограниченных 10^18. ridikyu, было бы хорошо, если бы он выдавал те входные данные, на которых не дает ответ. 0

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	28.11.2014, 22:35 [ТС]
	_Ivana, ну это да. 0

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	28.11.2014, 22:58 [ТС]
	_Ivana, ок попробую. правда чуть позже, сервер с кантестам упал. 0

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	28.11.2014, 23:23 [ТС]
	_Ivana, ну ты даешь))) спасибо за помощь. Но мне аж стыдно. Когда же я все это смогу сам делать. и понимать! 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	28.11.2014, 23:30
	Запустил тест проверки для n=10^11, до самого n пока считает, жду что покажет. Если совпадет, то будет хорошо. А что стыдно - это хорошая мотивация что-то делать и постигать самому. Вот D_in_practice тоже имхо начинал с простого, а упорство и некий хороший перфекционизм в сочетании с подписью дает уже очень неплохие плоды. Особенно по сравнению с другими учащимися кодерами. ЗЫ ну и если честно, то я не сам из головы все это придумал - благо в наше время есть интернет и там можно найти много интересного, в том числе и по математике и по алгоритмам 0

@D_in_practice 343 / 343 / 331 Регистрация: 02.10.2014 Сообщений: 666
	28.11.2014, 23:35
	_Ivana, мне кажется этот путь не канает, тк, для: N = 2, период будет = 3 N = 3, период будет = 8 N = 4, период будет = 6 N = 5, период будет = 12+... с чего Вы взяли, что для N = 1 000 000 007, период будет = 2 000 000 016 при n = 1 000 000 007 программа считает уже несколько секунд, что уже плохо интересно что 1 000 000 007 - простое число 0

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	28.11.2014, 23:36 [ТС]
	_Ivana, картинку одну видел)) так там статистика проблем при программирование в процентах. больше всего % на придумывание названия для проги и роботы с чужим кодам)))) 0

@D_in_practice 343 / 343 / 331 Регистрация: 02.10.2014 Сообщений: 666
	29.11.2014, 00:11
	Сообщение было отмечено ridikyu как решение Решение для чисел 3 4 15 100 1 000 1 000 000 006 работает 0

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	29.11.2014, 00:21 [ТС]
	_Ivana, жесть)) буду разбираться. спасиб 0

Число Фибоначчи 10​^18

Решение

Решение

Решение

Число Фибоначчи 10^18