рекурсия и хранение информации

[Rekky]

Добрый день
Задача такая...
Есть матрица большой размерности, нужно найти обратную ей матрицу рекурсивным методом...суть в том что основная матрица разделяется на составные части и для части А11 нужно опять таки найти обратную матрицу, чтобы вычислить основную..поскольку А11 будет опять таки матрица большой размерности, она также поделиться и также для 11 элемента нужно найти обратную матрицу..когда элемент 11 станет размерностью 2 на 2, можно применить обычный метод нахождения, через детерминант.
Вопрос в том, как и где хранить все эти матрицы\подматрицы. Причем нужна еще и организация рекурсии..
Если не понятно про деление матрицы на подматрицы то вот пример
Матрица А
А11 А12
А21 А22
Матрица А11
А1111 А1112
А1121 А1122
Вот как примерно я это вижу..
size размер исходной матрицы, в этом коде всегда перезаписываются матрицы A11 A12 A21 A22, описанные до этих функций, как стат массивы. естественно мне не нужно, чтобы они перезаписывались,а возвращаясь с рекурсией в место вызова..были бы сохранены те данные что посылались и плюс вычислена обратная матрица..

void SubMatrixInitialization(int a11[][size], int a12[][size], int a21[][size], 
							 int a22[][size], int m[][size],int n)
{	
	for (int i = 0; i<n;i++)
		for(int j=0; j<n; j++)
		{
			a11[i][j] = m[i][j];
			a12[i][j] = m[i][j+n]; 
			a21[i][j] = m[i+n][j];
			a22[i][j] = m[i+n][j+n];
		}
};
void InversMatrix(int m[][size], int m_1[][size], int s)
{
	SubMatrixInitialization(A11,A12,A21,A22, m, s/2);
	if (s != 2) { InversMatrix(A11, A11_1, s/2);}
        else {код нахождения матрицы 2 на 2}
};
int main ()
{}

Надеюсь более менее понятно описала

[f.hump]

может все таки Гауссом обратную сделать?

потому что описание "рекурсивного метота" мягко говоря не понятно.

[Guy]

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

Рукурсия ()
{
ложим на стек;
Рекурсия()
Метод()
}

Метод()
{
подымаем со стека()
делаем Что то.
ложим обратно
}

[Rekky]

этот метод мне нужен из за того, что он быстрее гаусса..задание такое..реализовать асимптотически более быстрый алгоритм.
Насчет стека подумаю..пока не понятно..как его использовать..сомнительный вариант..
А если я не понятно описала задачу, прошу сказать где конкретно, попробую рассказать лучше

[EUGY]

Если не трудно, дайте блочно алгоритм, который пытаетесь реализовать, некий псевдокод. Чтобы иметь представление в целом. Последний раз я наталкивался на обсуждение обратных матриц на RSDN, но не вникал.

[Rekky]

вот так сказать основная формула:
image079.gif
для вычисления
основная Функция()
{
Выделение блоков основной матрицы А для дальнейших расчетов А11 А12 А21 А22- получим подматрицы размерностью вдвое меньше чем А;
По тому же алгоритму, что будет построен найдем обратную матрицу для А11, необходимую для расчетов, т.е рекурсия к основная Функция;
Вычисляем произведения и суммы необходимые для расчетов
}
Т.е данный алгоритм содержит произведение матриц, сложение вычитание, нахождение рекурсивно обратной матрицы для элемента А11, поскольку А11 будет также матрицей большой размерности, она опять же поделится на подматрицы и для элемента А11 11 надо будет найти еще обратную матрицу. обратная матрица считается таким алгоритмом пока размерность не упадет до 2 на 2. там уже можно обычный алгоритм использовать..
Как будет хранится все это множество матриц..по идее здесь роль играть должны..А А11 А12 А21 А22 и А11-1, с каждым рекурсивным вызовом их размерность будет уменьшатся вдвое..и они будут иметь другие значения..

[f.hump]

и эта мурзилка быстрее Гаусса в общем случае??? не верю.
если честно, то если б мне пришлось закодить такое для общего случая, то у меня мозги поплавились бы.
сори за оффтоп.

[An1ka]

#include <vector>

template<class type>
 // Класс квадратной матрицы
 class matrix
{
		std::vector< type> mat;
		// Вернуть размерность квадратной матрицы
		inline const int GetSize( )const { return static_cast <const int > (sqrt ( static_cast <float >(mat.size( )))); }
		// Удалить 2 линии: строку i и столбец j из матрицы
		void Delete2Line ( const int i, const int j );
	public:
		// Конструктор по умолчанию
		inline matrix ( ) {}
		// Перегрузка оператора присвоения
		const matrix< type>& operator = ( const matrix< type>& m);
		// Перегрузка оператора доступа по индексу
		inline type& operator [] ( const int index) { return mat[index];}
		inline type& operator () ( const int i, const int j) { return mat[i+j*GetSize()];}
		// Перегрузка оператора умножения матриц
		const matrix< type> operator *( const matrix< type>& m)const;
		// Вернуть определитель(детерминант) матрицы
		const type GetDet( ) const;
		// Вернуть матрицу
		inline std::vector< type>& GetMatrix( ) { return mat;}
		// Добавить элементы в матрицу
		void Add( const type ptr);
		void Add( const type* ptr, const unsigned int elem_count);
		// Транспонировать матрицу
		void Transpose( );
		// Найти обратную матрицу; true - если возможно, false если вырожденная матрица
		bool Inverse( );
		// Деструктор по умолчанию
		inline ~matrix ( ) { mat.clear( );}
};
//--------------------------------------------------------------------
template<class type>
 const type matrix< type>::GetDet( ) const
{
	const int size = GetSize( );
	type det =0;
	if ( size == 1) det = mat[0];
	else
	  if ( size == 2) det = mat[0]*mat[3] - mat[1]*mat[2];
	  else
	    for ( int i =0; i < size; i++ )
	   {
	      matrix< type> temp_mat = *this;
	      temp_mat.Delete2Line( i, 0);
	      det += mat[i] * temp_mat.GetDet( ) * (i%2 ? -1 : 1);
	   }
   return det;
}
template<class type>
 const matrix< type>& matrix< type>::operator = ( const matrix< type>& m)
{
	if ( &m != this )
	  mat =m.mat;
  return *this;
}
template<class type>
 void matrix< type>::Add( const type ptr)
{
	mat.insert( mat.end(), ptr);
}
template<class type>
 void matrix< type>::Add( const type* ptr, const unsigned int elem_count)
{
	mat.insert( mat.end( ), ptr, ptr+elem_count );
}
template<class type>
 void matrix< type>::Delete2Line( const int i, const int j )
{
	const int size = GetSize( );
	for ( int el =0; el < size; el++ )
	  mat.erase ( mat.begin( ) + (i + el*size - el)); 
	mat.erase( mat.begin( ) + j*(size-1), mat.begin( ) + (j+1)*(size-1) );
}
template<class type>
 void matrix< type>::Transpose( )
{
	matrix< type> temp_mat;
	const int size = GetSize( );
	 for ( int i =0; i < size*size; i++ )
	   temp_mat.mat.push_back( mat[(i%size)*size + i/size]);
	mat =temp_mat.mat;
}
template<class type>
 bool matrix< type>::Inverse( )
{
	const type det = GetDet( );
	const int size = GetSize( );
	if ( !det ) return false;
	matrix< type> temp_mat;
	 for ( int i =0; i < size*size; i++ )
	{
	   matrix< type> m = *this;
	   m.Delete2Line( i%size, i/size);
	   temp_mat.mat.push_back( m.GetDet( ) /det * ( (i%size + i/size) % 2 ? -1 : 1));
	}
	temp_mat.Transpose( );
	mat =temp_mat.mat;
  return true;
}
template<class type>
 const matrix< type> matrix< type>::operator *( const matrix< type>& m)const
{
	matrix< type> temp_mat;
	const int size = GetSize( );
	temp_mat.mat.insert( temp_mat.mat.begin( ), size * size, 0);
     for ( int i =0; i < size * size; i++)
       for ( int j =0; j < size; j++)
		  temp_mat.mat[i] += this->mat[j+i/size*size] * m.mat[j*size+i%size];
  return temp_mat;
}
//====================================================================
#include <iostream>
#include <iterator>

 matrix< float> mat, mat1, mat2;
 const float fmat[] = {	2, 5, 7,
		        6, 3, 4,
		        5,-2,-3 };
template< class T>
 void print( typename std::vector<T >::iterator it, const int size)
{
	for ( int i =0; i < size; it +=size, i++ )
	{
		std::cout << "|  ";
		std::copy ( it, it+size, std::ostream_iterator<T >(std::cout, "  ") );
		std::cout << "|" << std::endl;
	}
}
//--------------------------------------------------------------------
 int main(int argc, char* argv[])
{	
	mat.Add( fmat, 9);
	std::cout << "Original Matrix: "<< std::endl ;
	print<float>( mat.GetMatrix( ).begin( ), 3);
	std::cout << "Matrix Determinant:  "<< mat.GetDet( ) << std::endl;
	mat.Inverse( );
	std::cout << "Matrix Inverse: "<< std::endl;
	print<float>( mat.GetMatrix( ).begin( ), 3);
	system("pause");

	mat2.Add( fmat, 9);
	mat1 = mat2 * mat;
	std::cout << "Matrix Multiply: "<< std::endl;
	print<float>( mat1.GetMatrix( ).begin( ), 3);
	system("pause");
        return 0;
}

Вот посмотри, всё просто. Только не знаю тем ли это медотом, что ты хочешь или нет Тут тоже есть распиливание матрицы, только не на две, а удаление из матрицы заданой строки и столбца.