Как умножить матрицы, используя 2D Array на последовательности Фибоначчи? - PullRequest
Новая
       17

Как умножить матрицы, используя 2D Array на последовательности Фибоначчи?

0 голосов
/ 09 апреля 2019

У меня проблема в том, что я не уверен, как я могу умножать матрицы вместе на одни и те же матрицы снова и снова. Я пытаюсь добиться того, чтобы я мог обновлять матрицы. Вот мой код: 

int fib3(int a, int b, int n) {
int num[2][2] = { {0,1}, {1,1} };
const int num2[2][2] = { {0,1}, {1,1} };
int factArray[2][1] = { {0}, {1} };
if (n == 0) {
    return a;
}
else if (n == 1) {
    return b;
}
else {

    for (int i = 0; i <= n; i++) {
        num[0][0] = ((num2[0][0] * 0) + num2[0][1] * 1);
        num[0][1] = ((num2[0][0] * 1) + num2[0][1] * 1);
        num[1][0] = ((num2[1][0] * 0) + num2[1][1] * 1);
        num[1][1] = ((num2[1][0] * 1) + num2[1][1] * 1);
    }


    factArray[0][0] = ((num[0][0] * factArray[0][0]) + num[0][1] * factArray[1][0]);
    factArray[1][0] = ((num[1][0] * factArray[0][0]) + num[1][1] * factArray[1][0]);

    return factArray[0][0];
}

Здесь я бы взял предыдущие матрицы и умножил их на постоянные матрицы, но я не уверен, как обновить матрицы, как я.

Таким образом, матрицы поднимаются до некоторой степени.

Так, например, я хочу найти f (5) 5-ю последовательность Фибоначчи, которая должна быть 5, и я получаю 1 как результат в программировании.

1 Ответ

1 голос
/ 09 апреля 2019

Формула в матричном представлении представляет интерес в основном для теоретического анализа. Хитрость в том, что вы можете всегда иметь два элемента последовательности в векторе, вместо того, чтобы ссылаться на более ранние элементы последовательности. Однако для его реализации я не вижу преимущества по сравнению с использованием рекурсивной формулы. Condsider, что 

 | 1 1 |   | a |    | a+b |
 | 1 0 | * | b | =  | a   |

Следовательно, умножение матриц эффективно делает то же самое: добавьте два последних элемента, запомните текущий (a).

При этом у вашего кода есть некоторые проблемы:

  • вы передаете a и b, но когда-либо используете их только для первого и второго элемента последовательности. Вам не нужны a и b. Начальные значения уже находятся в начальном значении матрицы.
  • у вас есть цикл, но на каждой итерации вы вычисляете одни и те же значения и записываете их в одни и те же элементы массива.
  • Я не могу действительно следовать логике вашего кода. Почему после цикла происходит другое умножение? Матричная формула в двух словах гласит: «Возьми некоторый начальный вектор, примени матрицу n раз, готово». Честно говоря, я не могу найти это нигде в вашем коде;)

Если вы настаиваете на использовании умножения матриц, я бы рекомендовал держаться подальше от массивов в стиле c. Им не нравится, когда их раздают. Вместо этого используйте std::array. У меня есть небольшое отвращение к гнездованию, поэтому я бы предложил использовать 

constexpr size_t N = 2;
using matrix = std::array<int,N*N>;
using vector = std::array<int,N>;

std::array с можно вернуть без боли: 

vector multiply(const matrix& a,const vector& b) {
    vector result;
    auto ma = [&a](size_t row,size_t col) { return a[row*N+col];};    
    result[0] = ma(0,0)*b[0] + ma(0,1)*b[1];
    result[1] = ma(1,0)*b[0] + ma(1,1)*b[1];
    return result;
}

Теперь следует реализовать последовательность Фибоначчи.

Оповещение о спойлере

...