Форум программистов, компьютерный форум CyberForum.ru

Первое пятнадцатизначное число Фибоначчи - C++

Восстановить пароль Регистрация
 
Даулет
0 / 0 / 0
Регистрация: 30.09.2012
Сообщений: 4
11.07.2013, 16:33     Первое пятнадцатизначное число Фибоначчи #1
Даны числа Фибоначчи 1 1 2 3 5 8 13 21... Найти первое число Фибоначчи, которое содержит 15 цифр. Никак не можем решить уже. помогите плиз. Вот формула Фибоначчи "fib[i] = fib[i-1]+fib[i-2];" Спасибо заранее)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2013, 16:33     Первое пятнадцатизначное число Фибоначчи
Посмотрите здесь:

C++ Умножить каждое число на первое отрицательное число. Добавив к каждому числу половину последнего отрицательного числа
Найти первое число Фибоначчи, большее N C++
Некоторое число оканчивается на 2. Если же эту его последнюю цифру переставить на первое место, то число удвоится. Найти это число C++
C++ Дано действительно число а.Найти среди чисел 1, 1*1/2, 1*/1/2+1/3, ... первое число, большее а, и его номер в последовательности чисел.
Введенное число делить на второе введенное число пока первое число не станет равным нулю C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
11.07.2013, 16:39     Первое пятнадцатизначное число Фибоначчи #2
А кто мешает сделать например так:
C++
1
2
3
4
while !(fib % pow(10, 15) )
{
   ...
}
P.S. Не стал использовать массивы так как не известно на каком элементе закончиться цикл. Введите две переменные и счетчик и не нужен будет никакой массив.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.07.2013, 16:44     Первое пятнадцатизначное число Фибоначчи #3
C++
1
2
3
4
while (fib < 100 000 000 000 000)
{
   ...
}
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
11.07.2013, 16:45     Первое пятнадцатизначное число Фибоначчи #4
Thinker, красота спасет мир!
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.07.2013, 16:50     Первое пятнадцатизначное число Фибоначчи #5
Цитата Сообщение от Ilot Посмотреть сообщение
C++
1
2
3
4
while !(fib % pow(10, 15) )
{
   ...
}
вопрос не в том, что fib делится на 10^15, а содержит 15 знаков, это разные вещи
Даулет
0 / 0 / 0
Регистрация: 30.09.2012
Сообщений: 4
11.07.2013, 17:13  [ТС]     Первое пятнадцатизначное число Фибоначчи #6
Так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int main()
{
    int a;
    for(int i = 2; i < 100000000000000; i++)
    {
        i = (i-1)+(i-2);
        a = i;
    }
    cout << a << endl;
    system("pause");
    return 0;
}
единицы выходят и всё
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.07.2013, 17:21     Первое пятнадцатизначное число Фибоначчи #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
const long long N = 100000000000000ull;
 
int main()
{
   long long a = 1, b = 1, c = a + b;
   while (c < N)
   {  
      a = b;
      b = c;
      c = a + b;
   }
   std::cout << (long long)c << std::endl;
   return 0;
}
Цитата Сообщение от Даулет Посмотреть сообщение
Так?
...
единицы выходят и всё
конечно, алгоритм неверный. при этом число 10^15 в тип int не влезет...
Даулет
0 / 0 / 0
Регистрация: 30.09.2012
Сообщений: 4
11.07.2013, 17:22  [ТС]     Первое пятнадцатизначное число Фибоначчи #8
Все спасибо тинкер. когда llu он не сработал, написал ull - все отлично! Спасибо!
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
12.07.2013, 07:58     Первое пятнадцатизначное число Фибоначчи #9
Цитата Сообщение от Thinker Посмотреть сообщение
вопрос не в том, что fib делится на 10^15, а содержит 15 знаков, это разные вещи
Эмм... не совсем понял.
Вот эта строчка:
C++
1
while !(fib % pow(10, 15) )
-говорит о том, что как только остаток от деления станет не нулевым выйти из цикла, а это будет только когда число Фибоначчи будет больше 1015.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 08:03     Первое пятнадцатизначное число Фибоначчи #10
Цитата Сообщение от Ilot Посмотреть сообщение
Эмм... не совсем понял.
Вот эта строчка:
C++
1
while !(fib % pow(10, 15) )
-говорит о том, что как только остаток от деления станет не нулевым выйти из цикла, а это будет только когда число Фибоначчи будет больше 1015.
Неужели? На примерах:
1 % 10 = 1
2 % 10 = 2
...
9 % 10 = 9
10 % 10 = 0
11 % 10 = 1
и т.д.
надеюсь, стало понятно
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
12.07.2013, 08:17     Первое пятнадцатизначное число Фибоначчи #11
так то у чисел фиббоначи формула есть через корни: https://ru.wikipedia.org/wiki/%D0%A7...87%D1%87%D0%B8
оттуда поди можно придумать более "правильный" алгоритм решения, а не решение в "лоб". хотя если скорость устраивает то и пофиг
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 08:20     Первое пятнадцатизначное число Фибоначчи #12
Цитата Сообщение от Kukurudza Посмотреть сообщение
так то у чисел фиббоначи формула есть через корни: https://ru.wikipedia.org/wiki/%D0%A7...87%D1%87%D0%B8
оттуда поди можно придумать более "правильный" алгоритм решения, а не решение в "лоб". хотя если скорость устраивает то и пофиг
программа работает доли секунды, а в формуле имеются радикалы.

Не по теме:

надо сначала хорошо подумать, прежде чем что-то предлагать (и меньше всякую каку курить)

Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
12.07.2013, 08:37     Первое пятнадцатизначное число Фибоначчи #13
Каюсь. Всего 66 итераций. Думал там итераций гораздо больше.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 08:57     Первое пятнадцатизначное число Фибоначчи #14
Цитата Сообщение от Kukurudza Посмотреть сообщение
Всего 66 итераций.
вот-вот

Ilot, чтобы уж очень не расстраивались, подскажу, в вашем алгоритме надо было заменить % на / и убрать лишний 0 из pow:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
const long long N = 100000000000000ull;
 
int main()
{
   long long a = 1, b = 1, c = a + b;
   while (!(c / N))
   {  
      a = b;
      b = c;
      c = a + b;
   }
   std::cout << (long long)c << std::endl;
   return 0;
}
только вот нужны ли лишние деления, если без них можно обойтись.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2013, 09:13     Первое пятнадцатизначное число Фибоначчи
Еще ссылки по теме:

Написать программу, которая определяет число Фибоначчи под номером N и проверяет, является ли это число возрастающим C++
Найти первое из чисел Фибоначчи, которое превосходит заданное число M C++
C++ Найти первое число Фибоначчи большее заданного

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
12.07.2013, 09:13     Первое пятнадцатизначное число Фибоначчи #15
Цитата Сообщение от Thinker Посмотреть сообщение
Ilot, чтобы уж очень не расстраивались, подскажу, в вашем алгоритме надо было заменить % на / и убрать лишний 0 из pow:
Да я как бы не расстраиваюсь чего тут. Я общаюсь на этом форуме, что бы поделиться своими знаниями и поучиться у людей которые знают больше чем я. Что там нужен знак простого деления я понял сразу как только вы мне объяснили в чем моя ошибка просто не стал комментировать данный факт, а просто поставил спасибку.
Yandex
Объявления
12.07.2013, 09:13     Первое пятнадцатизначное число Фибоначчи
Ответ Создать тему
Опции темы

Текущее время: 14:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru