Число Фибоначчи 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, жесть)) буду разбираться. спасиб

Новые блоги и статьи Все статьи Все блоги /
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .

Число Фибоначчи 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