БлогNot. Проверка матрицы на магический квадрат

Проверка матрицы на магический квадрат

Дана целочисленная квадратная матрица a размерности n. Определить, является ли она магическим квадратом, то есть, такой, в которой суммы элементов во всех строках, столбцах и на обеих диагоналях одинаковы. Все данные вводятся с консоли.

На самом деле магический квадрат должен ещё и состоять из элементов со значениями 1,2,...,n2, а по нашему определению "магична", например, и матрица из всех одинаковых элементов. Тем не менее, вот простейший учебный код для этой задачи.

#include <iostream>
using namespace std;

int main () {
 int n,i,j,result,sum,sum0;
 int **a;
 //Ввод допустимой размерности матрицы
 do {
  cout << "Input matrix size (from 2 till 100) ";
  cin >>n;
  if (n>1 && n<=100) break;
 } while (1);
 //Выделение памяти
 a = new int * [n];
 for (i=0; i<n; i++) a[i] = new int [n];
 //Поэлементный ввод данных
 for (i=0; i<n; i++) for (j=0; j<n; j++) {
  cout << "Input a[" << i << "," << j << "]=";
  cin >> a[i][j];
 }
 result = 1;
 //Контрольная сумма элементов первой строки
 sum0 = 0;
 for (j=0; j<n; j++) sum0 += a[0][j];
 //Суммы по строкам
 for (i=1; i<n; i++) {
  sum = 0;
  for (j=0; j<n; j++) sum += a[i][j];
  if (sum != sum0) { result = 0; break; }
 }
 //Суммы по столбцам
 if (result) {
  for (j=0; j<n; j++) {
   sum = 0;
   for (i=0; i<n; i++) sum += a[i][j];
   if (sum != sum0) { result = 0; break; }
  }
 }
 //Главная диагональ
 if (result) {
  sum = 0;
  for (i=0; i<n; i++) sum += a[i][i];
  if (sum != sum0) result = 0; 
 }  
 //Побочная диагональ
 if (result) {
  sum = 0;
  for (i=0; i<n; i++) sum += a[i][n-1-i];
  if (sum != sum0) result = 0; 
 }
 //Вывод
 cout << (result == 1 ? "Yes" : "No");
 system ("pause>nul"); return 0;
}

Проверить, что квадратная целочисленная матрица размерности n * n в любом порядке заполнена значениями 1, 2, ..., n2 и только ими можно в простейшем случае следующим кодом (показан для размерности 3x3):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool goodNumbers (const int n, int **a) {
 vector <int> cnt(n*n);
 fill(cnt.begin(), cnt.end(), 0);
 for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) if (a[i][j] > 0 && a[i][j] <= n*n) cnt[a[i][j]-1] = 1;
 }
 bool good = true;
 for (int i = 0; i < n*n; i++) {
  if (cnt[i] == 0) { good = false; break; }
 }
 return good;
}

int main() {
 const int n=3;
 int i, j;
 int** a;
 a = new int* [n];
 for (i = 0; i < n; i++) a[i] = new int[n];
 for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
  cout << "Input a[" << i << "," << j << "]=";
  cin >> a[i][j];
 }
 if (goodNumbers(n,a)) cout << "Yes";
 else cout << "No";

 cin.get(); return 0;
}

Просто поиск суммы по формуле (n2*(n2+1))/2 и сравнение её с суммой элементов матрицы здесь не подойдёт, ведь не только 1+2+3+4 = 10, но и, например, 1+1+4+4 :)


теги: числа c++ алгоритм

13.07.2014, 23:54; рейтинг: 10909