Главная

Перестановка строк матрицы(размером m * n) по невозрастанию максимальных элементов ее строк.

Опубликовано Мазинов Осман в Вс, 10/04/2009 - 15:03

Дана действительная матрица размером m * n; упорядочить (пе­реставить) строки матрицы по невозрастанию максимальных элемен­тов строк матрицы. Разрешается использовать дополнительный массив. Задание №4(Сортировка массивов) (см. "Сборник задач для начинающего программиста").

Алгоритм:
1. Заводим двумерный массив для матрицы и массив указателей на строки матрицы, а также массив, который будет хранить максимальные элементы из каждой строки матрицы.
2. Инициализируем матрицу псевдослучайными числами и выводим ее на экран.
3. С помощью функции max_in_line находим максимальные элементы в каждой строке и записываем их в соответствующий массив.
4. Выводим на экран номер строки матрицы и максимальный элемент из этой строки.
5. Выполняем сортировку максимальных элементов из каждой строки по невозрастанию методом обмена и соответствующих этим элементам строк(указателей на эти строки). Для сортировки указателей используем вспомагательную переменную tmp.
6. Выводим на экран преобразованную согласно условию матрицу.

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
 
#include <iomanip>
using std::setw;
 
#include <cstdlib>
#include <time.h>
 
int max_in_line(int *, int); // Находит максимальный элемент в строке матрицы
 
 
int main()
{
 
   const int m = 5, n = 6; // Указываем размеры матирцы
   int a[m][n]; // Массив, который будет хранить матрицу
   int *p[m]; // Массив указателей на строки матрицы
   int s[m]; // Массив, хранящий максимальные элементы
   int i, j; 
   int *tmp;
   time_t t;
 
   srand((unsigned) time(&t));
 
   cout << "Here is the initial matrix (" << m << " * " << n << "):\n" << endl;
 
   // Инициализируем матрицу и тут же ее выводим
   for(i = 0; i < m ; i++)
   {
 
	  for(j = 0; j < n; j++)
      {
         a[i][j] = rand() % 100;
		 cout << setw(4) << a[i][j]; 
      }
	  p[i] = &a[i][0];
      cout << endl;
   }
 
   cout << endl;
 
   cout << "Line # / Largest element\n" << endl; 
 
   // Поиск и вывод максимальных элементов в каждой строке матрицы
 
   for(i = 0; i < m; i++)
      s[i] =  max_in_line(&a[i][0], n);
 
   for(i = 0; i < m; i++)
      cout << setw(4) << i << setw(13) << s[i] << endl;
 
 
   // Сортировка максимальных элементов из каждой строки по невозрастанию методом обмена 
   // и соответствующих этим элементам строк (указателей на эти строки)
 
   for(i = 0 ; i < m - 1 ; i ++)
       for(j = 0; j < m - 1 - i ; j ++)
          if(s[j] < s[j+1])
          {
                  s[j]^=s[j+1];
                  s[j+1]^=s[j];
                  s[j]^=s[j+1];
 
		  tmp = p[j];
		  p[j] = p[j+1];
		  p[j+1] = tmp;
          }
 
 
   cout << endl;	  
 
   // Вывод на экран максимальных элементов из каждой строки, упорядоченных по невозрастанию
 
   cout << "Here is the largest elements in nonincreasing order:\n" << endl;
 
   for(i = 0; i < m; i++)
      cout << setw(4) << s[i] << endl;
 
   cout << endl;
 
   // Матрица, преобразованная согласно условию 
 
   cout << "Transformed matrix:\n" << endl;
 
   for(i = 0; i < m; i++)
   {
      for(j = 0; j < n; j++)
	     cout << setw(4) << *p[i]++;
	  cout << endl;
   }
 
 
 
   return 0;
}
 
// Передаем функции указатель на каждую строку матрицы, которая является одномерным массивом.
 
int max_in_line(int *p, int n)
{
	int max = 0;
        for(int i = 0 ; i < n ; i++)
	{
		if(*p > max)
			max = *p;
		p++;
	}
 
	return max;
}

Ключевые слова: 
массив, список, поиск максимального элемента