Длинная арифметика
Доброго времени суток! Прошу обьянить как можно сделать длинную арифметику (слаживание) на матрицах.
|
Prof, тебе нужна теория или что?
|
Сложение двух чисел, по определению, дает +1 разряд в лучшем случае, вполне укладывающимся в разряд переноса.
Или арифметика сложения на матрицах "длиннее" обычной?
Ну это так, пальцем в небо.
Prof, еще раз четко и внятно напиши, что тебе надо? Желательно с примером, а то по коротким фразам гадать можно долго. |
Ребята, простите за такой вопрос. Сам понимаю что написал бред просто заходил с телефона, спешил и небыло при себе примера.
И так, нормальный вопрос:
Есть такая программка:
Код:
#include<stdafx.h>
#include<iostream>
#include<vector>
#include<fstream>
#define dvec vector<vector<int> >
using namespace std;
dvec mul(dvec a, dvec b) //умножение матриц
{
dvec ans (a.size(),vector<int>(b.size()));
int tmp = 0;
for(int i = 0; i<a.size(); ++i)
{
for(int j = 0; j<b.size(); ++j)
{
for(int k = 0; k<a[0].size(); ++k)
ans[i][j]+=a[i][k]*b[k][j];
}
}
return ans;
}
int main()
{
int n,q;
ifstream inp ("input.dat");
ofstream out ("output.sol");
dvec vec(2,vector<int>(2)); //матрица
vec[0][0] = 0;
vec[0][1] = vec[1][0] = vec[1][1] = 1;
dvec mnoj = vec; //таже матрица, будет использована как множитель для возведения в степень
inp >> q;
n = q-3;
for(int i = 0; i<n; ++i) //возведение в степень
{
vec = mul(vec,mnoj);
}
out<<(vec[1][0]+vec[1][1])<<"\n";
return 0;
}
Суть её в том чтоб считать 30к+ число фибоначчи менее чем за секунду, но для этого нужно переделать её под длинную арифметику и заменить возведения матриц в степень на бинарное возведение в степень. Сам недавно начал учить C++, так что со своими знаниями ещё не до конца понимаю как это реализовать. |
Время: 20:57.
© OSzone.net 2001-
