Двумерни масиви – магически квадрат

Продължаваме с втора част от решенията и този път на прицел са две задачки от областта на двумерните масиви. В тази статия ще търсим магически квадрат, а в следващата – седлови точки.

Звучи забавно!

Задача 1: Да се провери дали въведен от клавиатурата двумерен масив представлява магически квадрат. Една матрица е магически квадрат, когато сумите по редове, колони и по двата диагонала са равни.

Решение:

#include <iostream>
#define ARRA 3
using namespace std;

int main(){

	int arr[ARRA][ARRA];
	int i, j;

	int sum = 0;
	int newsum = 0;

	bool fail = false;

	cout << "Въведете двумерен масив (" << ARRA << " на " << ARRA << "):\n";
	for(i=0; i<ARRA; i++)
		for(j=0; j<ARRA; j++){
		cin >> arr[i][j];
	}
	cout << "[Готово]\n" << endl;

	for(i=0; i<ARRA; i++) sum+= arr[i][i];
	for(i=(ARRA-1); i>=0; i--) newsum += arr[i][ARRA-1-i];

	if(!(fail = sum != newsum)){
		for(i=0; (i<ARRA) && !fail; i++){
			for(j=0; j<ARRA; j++){
				if(!j){
					if(i && (sum != newsum)) fail = true;
					newsum = 0;
				 }
				newsum += arr[i][j];
			}
		}
		cout << "\n";
		for(i=0; (i<ARRA) && !fail; i++){
			for(j=0; j<ARRA; j++){
				if(!j){
					if(i && (sum != newsum)) fail = true;
					 newsum = 0;
				 }
				newsum += arr[j][i];
			}
		}
	}
	cout << "Квадратът ";
	if(!fail) cout << "е магически!\n";
	else cout << "не е магически!\n";

	return 0;

}

Този код може и да ви се стори леко объркващ, така че смятам да обясня какво се случва ред по ред. Причината да не правя това в коментари е, че смятам, че в случая това би направило четенето по-трудно.

Същинското действие започва от (22). Преди това сме декларирали променливи и прочели числата от клавиатурата.

Първо намираме сумите по главния (22) и по вторичния (23) диагонал.
Променливата, с която отбелязваме дали условието е било нарушено, fail, приема за стойност „различава ли се сумата по главния от тази по вторичния диагонал?“ (25). Ако разлика не е налице, можем да продължим.

В следващия for (26), където търсим сумите по редове и ги сравняваме, като условие вписваме и „докато fail не е истина“, с което предодвратяваме ненужните изчисления, които биха възникнали при обхождане на целия масив.

Ето какво се случва: четем един по един елементите от всеки ред (26-27) и когато j е нула (28-и ред) (т.е. сме в началото на всеки следващ ред от матрицата), правим сравнениe между sum и newsum (29). Нямаме необходимост да правим подобна съпоставка, когато сме на първия ред (т.е. този с нулев индекс) и указваме това си желание в условието. Веднъж направили сравнението, нулираме newsum, за можем да приютим вътре поредната стойност от реда. Това се случва на ред 32.

Следва да повторим напълно същата процедура и за колоните на матрицата. Любителите на кратките описания биха могли да вместят двете неща в един алгоритъм.

Накрая (46) остава само да оповестим присъдата – магически ли е или не квадратът.

Висящ е единствено въпросът как да тестваме програмата си (освен въвеждайки матрица изцяло с еднакви стойности), затова и ще споделя един бърз метод за съставяне на триредови магически квадрати наум.

  1. Изберете си число, от което да започнете. Например 1.
  2. Представете си квадратна матрица, 5 на 5.
  3. По диагонал, започвайки от първата позиция на третия ред и вървейки нагоре, нанасяйте последователно числата – това, от което сте решили да започнете и поредните му. Например 1, 2, 3.
  4. Следващият диагонал започва от четвъртия ред и от втората му позиция.
  5. Това важи и за последния диагонал – той върви нагоре и надясно от петия ред и третата му позиция.
  6. Досега получихме 5 на 5 матрица с някои празни позиции. Искаме обаче квадратът ни да е с размери 3 на 3. Имаме нанесени точно девет числа или всичко, необходимо за нашия магически квадрат, е налице.
    Затова правим следното – пренасяме всяко число, падащо се извън 3 на 3 матрицата (т.е. на някой от крайните редове и колони) три полета в посока матрицата.
    Резултатът е един прекрасен магически квадрат.

Например

Магически квадрат

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.