Волшебный квадрат – решите головоломку 3×3, используя C и Python Примеры
Сара Чен
Что такое Магический квадрат?
Магический квадрат — это квадратная матрица со специальным расположением чисел. Эти числа расположены так, что сумма чисел на каждой диагонали, строке и столбце остается одинаковой. Игры «Магические квадраты» — это простые логические головоломки, используемые в развлекательной математике.
Пример магических квадратов:
На приведенной выше диаграмме приведен пример магического квадрата третьего порядка. Сумма каждой диагонали, строки и столбца равна 3.
Как работает Магический квадрат
Магические квадраты — это матрицы n*n, состоящие из n^2 целых положительных чисел. Количество строк или столбцов квадратной матрицы называется порядком матрицы.
Обычно головоломки с магическими квадратами имеют нечетный порядок и содержат целые числа от 1 до n^2. Сумма каждой диагонали, строки и столбца одинакова. Это число называется магической суммой или магической константой. Как правило, эта магическая сумма зависит от порядка матрицы. Формула магических квадратов для магической суммы порядка n:
Давайте возьмем пример магического квадрата с целыми числами 3. Итак, магическая сумма будет:
Почему их называют Магическими?
Древние математики были очарованы природой нескольких интересных комбинаций чисел. Магический квадрат был одним из них. Самые ранние свидетельства существования магических квадратов относятся к Китаю, датированному 190 годом до нашей эры.
Некоторые исследования свидетельствуют о существовании головоломки «Магические квадраты» в древней Японии, Индии и Аравии. На основании некоторых легенд предполагалось, что эти особые числовые образования были связаны с волшебным миром. Поэтому эти квадраты были названы магическими квадратами.
Виды магического квадрата
Существуют разные варианты математики магических квадратов –
- Обычный магический квадрат: Этот тип магического квадрата содержит первые n^2 чисел.
- Полумагический квадрат: В этом типе только строки и столбец суммируются до магической константы.
- Простой магический квадрат: В отличие от предыдущего типа, сумма строк, столбцов и обеих диагоналей дает магическую константу.
- Самый совершенный магический квадрат: Это обычный магический квадрат с двумя особыми свойствами. Здесь каждый подквадрат матрицы размером 2 на 2 в сумме дает 2(n^2+1). И любая пара чисел, которые находятся на расстоянии n/2 квадратов от суммы сетки до n^2+1.
По свойствам существует еще много типов магических квадратов. Но всякий раз, когда мы просто упоминаем магический квадрат, мы предполагаем, что это обычный и простой магический квадрат нечетного порядка.
Алгоритм создания магического квадрата
Алгоритм генерации магических квадратов нечетного порядка:
- Первое число или 1 будет сохранено в (n/2, n-1), где первая координата — это позиция строки, а вторая координата — позиция столбца. Для дальнейших шагов давайте обозначим эту позицию как (x, y).
- Следующие числа будут храниться в (x-1, y+1). Если позиция недействительна, то рассмотрим следующие условия.
- Если позиция строки равна -1, она изменится на n-1. Аналогично, если вычисленная позиция столбца равна n, она изменится на 0.
- Позиция строки будет увеличена на 1, а позиция столбца будет уменьшена на 2, если вычисленная позиция уже содержит число.
- Если позиция строки равна -1, а позиция соответствующего столбца равна n, новая позиция будет (0, n-2.
Примечание: Этот алгоритм генерирует действительные магические квадраты только нечетного порядка. Мы также считаем этот магический квадрат обычным магическим квадратом с первыми числами n^2. Более того, для одного и того же значения n может быть несколько решений.
Давайте возьмем пример и посмотрим, как это работает. Допустим, мы хотим найти магический квадрат третьего порядка. Поскольку это будет простой и обычный магический квадрат нечетного порядка, он будет содержать все числа от 3 до 1^3 или 2.
Как это работает?
По нашим алгоритм, шаги будут следующими:
Шаг 1) Первое число или 1 будет в позиции (3/2, 3-1) или (1, 2). По соглашению, для последующих шагов рассмотрим x= 1 и y= 2.
Шаг 2) Позиция остальных чисел будет рассчитываться следующим образом:
Позиция номера 2:
Следующее число будет в позиции (x-1, y+1) или (0, 3), что не является допустимой позицией. При использовании условия (a) соответствующей допустимой позицией будет (0,0). Итак, х=0, у=0.
Позиция номера 3:
Номер 3 будет в позиции (x-1, y+1) или (-1, 1), что не является допустимой позицией. При использовании условия (a) допустимой позицией строки будет n-1 или 2. Таким образом, номер 3 будет в (2, 1). Для следующего числа x= 2, y= 1.
Позиция номера 4:
Номер 4 должен находиться в позиции (x-1, y+1) или (1, 2), что является допустимой позицией. Но эта позиция уже содержит номер. Согласно условию (b), допустимой позицией будет (1+1, 2-2) или (2,0). Для следующего числа x= 2, y= 0.
Позиция номера 5:
Номер 5 должен находиться в позиции (x-1, y+1) или (1, 1), что является допустимой позицией. Для следующего числа x= 1, y= 1.
Позиция номера 6:
Номер 6 должен находиться в позиции (x-1, y+1) или (0, 2), что является допустимой позицией. Для следующего числа x= 0, y= 2.
Позиция номера 7:
Номер 7 должен находиться в позиции (x-1, y+1) или (-1, 3), что не является допустимой позицией. Согласно условию (c), допустимой позицией будет (0, n-2) или (0, 1). Для следующего числа x= 0, y= 1.
Позиция номера 8:
Номер 8 должен находиться в позиции (x-1, y+1) или (-1, 2), что не является допустимой позицией. При использовании условия (a) допустимой позицией будет (2, 2). Для следующего числа x= 2, y= 2.
Позиция номера 9:
Номер 9 должен находиться в позиции (x-1, y+1) или (1, 3), что не является допустимой позицией. При использовании условия (a) допустимой позицией будет (1, 0).
Псевдо-код
Begin Declare an array of size n*n Initialize the array to 0 Set row = n/2 Set column = n-1 For all number i: from 1 to n*n If the row = -1 and column = n row = 0 column = n-2 Else If row = -1 row = n-1 If column = n column = 0 If the position already contains a number decrement column by 2 increment row by 1 continue until the position is not 0 Else put the number i into the calculated position increment i Increment column value Decrement row value End
C++ Код Магический квадрат
Входной сигнал:
/*
A C/C++ program for generating odd order magic squares
*/
#include <bits/stdc++.h>
using namespace std;
void GenerateMagicSquare(int n)
{
int magic[n][n];
//initializing the array
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
magic[i][j] = 0;
//setting row and column value
int i = n / 2;
int j = n - 1;
for (int k = 1; k <= n * n;)
{
//checking condition (c)
if (i == -1 && j == n)
{
j = n - 2;
i = 0;
}
else
{
//checking condition (a)
if (j == n)
j = 0;
if (i < 0)
i = n - 1;
}
//checking condition (b)
if (magic[i][j])
{
j -= 2;
i++;
continue;
}
else
{
//placing the number into the array
magic[i][j] = k;
k++;
}
//for the next number setting (i-1, j+1)
j++;
i--;
}
//printing the matrix
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << magic[i][j] << " ";
cout << endl;
}
}
int main()
{
//This code works for only odd numbers
int n = 7;
cout<<"The magic sum is " << n*(n*n+1)/2 <<endl;
GenerateMagicSquare(n);
return 0;
}
Вывод примера:
The magic sum is 175 20 12 4 45 37 29 28 11 3 44 36 35 27 19 2 43 42 34 26 18 10 49 41 33 25 17 9 1 40 32 24 16 8 7 48 31 23 15 14 6 47 39 22 21 13 5 46 38 30
Python Код Магический квадрат
def GenerateMagicSquare(n):
#initializing the array
magic = [[0 for x in range(n)]
for y in range(n)]
#setting row and column value
i = n // 2
j = n - 1
k = 1
while k <= (n * n):
#checking condition (c)
if i == -1 and j == n:
j = n - 2
i = 0
else:
#checking condition (a)
if j == n:
j = 0
if i < 0:
i = n - 1
#checking conditon (b)
if magic[i][j]:
j = j - 2
i = i + 1
continue
else:
#placing the number into the array
magic[i][j] = k
k = k + 1
#for the next number setting (i-1, j+1)
j = j + 1
i = i - 1
#printing the matrix
for i in range(0, n):
for j in range(0, n):
print('%2d ' % (magic[i][j]),end='')
if j == n - 1:
print()
#This code works for only odd numbers
n = 7
print("The magic sum is ",n * (n * n + 1) // 2, "\n")
GenerateMagicSquare(n)
Вывод примера:
The magic sum is 175 20 12 4 45 37 29 28 11 3 44 36 35 27 19 2 43 42 34 26 18 10 49 41 33 25 17 9 1 40 32 24 16 8 7 48 31 23 15 14 6 47 39 22 21 13 5 46 38 30
Анализ сложности
- Космическая сложность: Чтобы поддерживать матрицу магического квадрата, нам нужен массив *n. Итак, пространственная сложность будет O(n^2).
- Сложность времени: Код, который мы использовали для создания математических вычислений с магическими квадратами, состоит из двух циклов. Внешний цикл выполняется n раз, и внутренний цикл также выполняется n раз. В конечном итоге временная сложность равна O(n^2).
