Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
костя666674555
-3 / 0 / 2
Регистрация: 02.01.2014
Сообщений: 78
#1

Требуется найти наибольший общий делитель двух чисел Фибоначчи. - C++

09.02.2014, 17:26. Просмотров 1500. Ответов 7
Метки нет (Все метки)

ЗАДАЧА №384

Числа Фибоначчи - 3
(Время: 1 сек. Память: 16 Мб Сложность: 52%)

Последовательностью Фибоначчи называется последовательность чисел F0 = 0, F1 = 1, … , Fk = Fk-1 + Fk-2 (k > 1).

Требуется найти наибольший общий делитель двух чисел Фибоначчи.
Входные данные

Во входном файле INPUT.TXT записаны два целых числа i и j (1 ≤ i, j ≤ 106).
Выходные данные

В выходной файл OUTPUT.TXT выведите остаток от деления НОД чисел Fi и Fj на 10^9.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <fstream>
int G(int a, int b){
    int c;
    while ( b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
main(){
    std::fstream i("input.txt"),o("output.txt", 2);
    __int64 n,k,j=1,a=1,b=0,t;
    for(i>>n>>k; j<G(n,k); j++){
        t=a;
        a=(a+b)%1000000000;
        b=t; }
    o<<a;
}
Размер кода: 211
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.02.2014, 17:26
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Требуется найти наибольший общий делитель двух чисел Фибоначчи. (C++):

Найти наибольший общий делитель двух чисел Фибоначчи
Добрый вечер, решаю задачу, ошибка на шестом тесте. Условии задачи: ...

Найти наибольший общий делитель двух чисел
Задание: найти наибольший общий делитель двух чисел. Сам код: #include...

Найти наибольший общий делитель двух чисел
найти наибольший общий делитель двух чисел с помощью рекурсии и без нее

Найти наибольший общий делитель двух чисел
Задача &quot;Длинный НОД&quot; Даны два числа. Найти их наибольший общий делитель....

Найти наибольший общий делитель двух чисел
Для заданных натуральных целых чисел n и m найти наибольший общий делитель...

Найти наибольший общий делитель двух натуральных чисел
номер 2: Составьте программу определения наибольшего общего делителя двух...

7
KOPOJI
09.02.2014, 23:37
  #2

Не по теме:

Цитата Сообщение от костя666674555 Посмотреть сообщение
Размер кода: 211
честно, задолбали уже с этими "размер кода"... Никому, кроме вас, это уже давно неинтересно :-! Меряйтесь своими "пиписьками", а не чужими.. :-/

1
Amandosov
Знаток
156 / 156 / 185
Регистрация: 18.11.2012
Сообщений: 411
Записей в блоге: 2
10.02.2014, 19:30 #3
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
#include <iostream>
#include <fstream>
using namespace std;
 
int f[200],n,k;
void fibon(int n)
{
f[0]=0;f[1]=1;
for(int i=2;i<=n;i++)
f[i]=f[i-1]+f[i-2];
}
 
int NOD(int a,int b)
{
for(int i=a;i>0;i--)
if(a%i==0&&b%i==0) return i;
}
 
int main()
{
fstream in("input.txt"),out("output.txt", 2);
 
int buf;
in>>n>>k;
if(n<k) 
 {
   buf=k;
   k=n;
   n=buf;
 }
fibon(n);
out<<NOD(f[k],f[n])%1000000000;
 
return 0;
}
0
костя666674555
-3 / 0 / 2
Регистрация: 02.01.2014
Сообщений: 78
12.02.2014, 16:37  [ТС] #4
что это? читайте условие
0
Amandosov
Знаток
156 / 156 / 185
Регистрация: 18.11.2012
Сообщений: 411
Записей в блоге: 2
12.02.2014, 16:51 #5
костя666674555,
это нахождение наибольшего общего делителя двух чисел
а в нашем случае, НОД двух чисел с последовательности фибоначи
0
Croessmah
++Ͻ
14161 / 8086 / 1513
Регистрация: 27.09.2012
Сообщений: 19,926
Записей в блоге: 3
Завершенные тесты: 1
12.02.2014, 16:56 #6
Цитата Сообщение от костя666674555 Посмотреть сообщение
читайте условие
прочитал вопрос
Цитата Сообщение от костя666674555 Посмотреть сообщение
Требуется найти наибольший общий делитель двух чисел Фибоначчи.
1
костя666674555
-3 / 0 / 2
Регистрация: 02.01.2014
Сообщений: 78
13.02.2014, 19:40  [ТС] #7
поработал админ тема была другая
0
KOPOJI
13.02.2014, 19:42     Требуется найти наибольший общий делитель двух чисел Фибоначчи.
  #8

Не по теме:

костя666674555, не гони на админов, заголовок "числа фибоначи 3" (который был здесь до переименования темы) вообще ничего не проясняет.

З.Ы. Публичное обсуждение действий администрации запрещено. Предупреждение.

1
13.02.2014, 19:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.02.2014, 19:42
Привет! Вот еще темы с ответами:

Найти наибольший общий делитель двух целых чисел
Знаю что есть задачи на эту тему, но нужного для себя не нашла. Не могу...

Найти наибольший общий делитель двух чисел используя алгоритм Евклида
Найти наибольший общий делитель двух чисел используя алгоритм Евклида....

Найти наибольший общий делитель и наименьшее общее кратное двух чисел
Даны два натуральных числа m и n. Найти их наибольший общий делитель и...

Найти наибольший общий делитель двух введенных чисел, используя алгоритм Евклида
Тема: Функции2. 6. Найти наибольший общий делитель (ндс) двух введенных чисел,...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru