С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.61
Lord_Voodoo
Супер-модератор
8594 / 2211 / 61
Регистрация: 07.03.2007
Сообщений: 10,766
Завершенные тесты: 1
#1

Остаток деления от числа фибоначчи - C++

11.10.2008, 11:56. Просмотров 2225. Ответов 0
Метки нет (Все метки)

подскажите, как максимально минимизировать такой алгоритм:
Код
#include <iostream>
using namespace std;
const int N = 2;
void mult(long long a[N][N], long long b[N][N], long long res[N][N], long long d){
  long long c[N][N] = {0, 0, 0, 0};
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++){
      c[i][j] = 0;
      for(int k = 0; k < N; k++)
        c[i][j] = (c[i][j] + (a[i][k] % d)*(b[k][j] % d)) % d;
      c[i][j] = c[i][j] % d;
    }
  memmove(res, c, 4 * sizeof(long long));
}
int main()
{
    long long mp[N][N] = {0, 1, 1, 1};
    long long mr[N][N] = {1, 0, 0, 1};
    long long n, d;
    cin>>n>>d;
    if(n <= 2){
      cout<<1 % d;
      return 0;
    }
    while(n > 0){
      if((n & 1) == 0){
        mult(mp, mp, mp, d);
        n >>= 1;
      }
      n--;
      mult(mr, mp, mr, d);
    }
    cout<<mr[0][1]<<endl;
 return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2008, 11:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Остаток деления от числа фибоначчи (C++):

злополучные числа фибоначчи - C++
написал прогу для нахождения очень больших чисел фибоначчи, 1000 - не проблема, но вот бракуют меня, что неверно вычисляют, кто может...

Найти сумму чисел Фибоначчи, меньших заданного числа - C++
1) Задан массив М натуральных чисел, упорядоченный по неубыванию, т.е .: M&lt;=M&lt;=...&lt;=M. Найти первое натуральное число, не представимое...

if else и остаток от деления - C++ Builder
#include &lt;stdio.h&gt; #include &lt;vcl.h&gt; #include &lt;math.h&gt; #pragma hdrstop int main() { double i,a,k; printf(&quot;Enter i: &quot;); ...

Нестандартная обработка чисел. Вычислить остаток от деления b на а. - C++ Builder
В первой строке записано число а от 1 до 1000, во второй - число b от 1 до 10^1000. Вычеслить остаток от деления b на а. Как найти...

Длинная арифметика (С++ Builder XE5) - не выводится остаток от деления - C++ Builder
Помогите пожалуйста с программой, необходимо разработать приложение, реализующие сложение, вычитание, умножение и деление двух целых...

Числа Фибоначчи - C++ Builder
Помогите исправить, по нажатию кнопки числа должны выводятся в Memo1, но выводится только первое число. int k=0, f=0; Memo1-&gt;Clear(); ...

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

Вывести остаток от деления НОД чисел F(i) и F(j) на 10^9. (F - Число Фибоначчи) - C++
Последовательностью Фибоначчи называется последовательность чисел F0 = 0, F1 = 1, … , Fk = Fk-1 + Fk-2, (k &gt; 1). Требуется найти...

Введите два числа и найдите частное от деления нацело первого числа на второе и остаток от деления нацело, используя только операцию вычитания - Turbo Pascal
Введите два числа и найдите частное от деления нацело первого числа на второе и остаток от деления нацело, используя только операцию...

Очень большие числа: узнать, есть ли остаток от деления одного числа на другое - C++
Требуется узнать, есть ли остаток от деления одного числа на другое. Оба числа много больше int64, ~1000 символов и больше. Я попытался...

Определить остаток от деления числа А на 3 - Pascal
Задача 5. Дано целое число А. Определить остаток от деления числа А на 3. (Используем метод последовательного вычитания чисел)


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

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

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