Рубрики

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

Магический квадрат порядка n — это расположение n ^ 2 чисел, обычно различных целых чисел, в квадрате, так что n чисел во всех строках, все столбцы и обе диагонали суммируют одну и ту же константу. Магический квадрат содержит целые числа от 1 до n ^ 2.

Постоянная сумма в каждой строке, столбце и диагонали называется магической константой или магической суммой М. Магическая константа нормального магического квадрата зависит только от n и имеет следующее значение:
M = n (n ^ 2 + 1) / 2

For normal magic squares of order n = 3, 4, 5, ...,
 the magic constants are: 15, 34, 65, 111, 175, 260, ... 

В этом посте мы обсудим, как программно мы можем генерировать магический квадрат размером n. Прежде чем идти дальше, рассмотрим следующие примеры:

Magic Square of size 3
-----------------------
  2   7   6
  9   5   1
  4   3   8
Sum in each row & each column = 3*(3^2+1)/2 = 15


Magic Square of size 5
----------------------
  9   3  22  16  15
  2  21  20  14   8
 25  19  13   7   1
 18  12   6   5  24
 11  10   4  23  17
Sum in each row & each column = 5*(5^2+1)/2 = 65


Magic Square of size 7
----------------------
 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
Sum in each row & each column = 7*(7^2+1)/2 = 175

Вы нашли какой-нибудь шаблон, в котором хранятся числа?
В любом магическом квадрате первое число, то есть 1, сохраняется в позиции (n / 2, n-1). Пусть эта позиция будет (i, j). Следующее число хранится в позиции (i-1, j + 1), где мы можем рассматривать каждую строку и столбец как круговой массив, т.е.

Три условия выполняются:

1. Позиция следующего числа вычисляется путем уменьшения номера строки предыдущего номера на 1 и увеличения номера столбца предыдущего номера на 1. В любое время, если вычисленная позиция строки становится равной -1, она будет округлена до n- 1. Точно так же, если вычисленная позиция столбца становится n, она будет округлена до 0.

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

3. Если вычисленная позиция строки равна -1, а вычисленная позиция столбца равна n, новая позиция будет: (0, n-2).

Example:
Magic Square of size 3
----------------------
 2  7  6
 9  5  1
 4  3  8 

Steps:
1. position of number 1 = (3/2, 3-1) = (1, 2)
2. position of number 2 = (1-1, 2+1) = (0, 0)
3. position of number 3 = (0-1, 0+1) = (3-1, 1) = (2, 1)
4. position of number 4 = (2-1, 1+1) = (1, 2)
   Since, at this position, 1 is there. So, apply condition 2.
   new position=(1+1,2-2)=(2,0)
5. position of number 5=(2-1,0+1)=(1,1)
6. position of number 6=(1-1,1+1)=(0,2)
7. position of number 7 = (0-1, 2+1) = (-1,3) // this is tricky, see condition 3 
   new position = (0, 3-2) = (0,1)
8. position of number 8=(0-1,1+1)=(-1,2)=(2,2) //wrap around
9. position of number 9=(2-1,2+1)=(1,3)=(1,0) //wrap around

Основываясь на вышеуказанном подходе, следующий рабочий код:

C ++

// C ++ программа для генерации магических квадратов нечетного размера
#include <bits/stdc++.h>

using namespace std;

  
// Функция для генерации магических квадратов нечетного размера

void generateSquare(int n) 

    int magicSquare[n][n]; 

  

    // установить все слоты как 0

    memset(magicSquare, 0, sizeof(magicSquare)); 

  

    // Инициализировать позицию для 1

    int i = n/2; 

    int j = n-1; 

  

    // Один за другим помещаем все значения в магический квадрат

    for (int num = 1; num <= n*n; ) 

    

        if (i == -1 && j == n) // 3-е условие

        

            j = n-2; 

            i = 0; 

        

        else

        

            // 1-й помощник условия, если следующий номер

            // выходит из правой стороны квадрата

            if (j == n) 

                j = 0; 

  

            // 1-й помощник условия, если следующий номер

            // это выходит из верхней стороны квадрата

            if (i < 0) 

                i = n - 1; 

        

        if (magicSquare[i][j]) // 2-е условие

        

            j -= 2; 

            i++; 

            continue

        

        else

            magicSquare[i][j] = num++; // установить номер

  

        j++; i--; // 1-е условие

    

  

    // Печать магического квадрата

    cout<<"The Magic Square for n="<<n<<":\nSum of "

    "each row or column "<<n*(n*n+1)/2<<":\n\n"

    for (i = 0; i < n; i++) 

    

        for (j = 0; j < n; j++) 

            cout<<magicSquare[i][j]<<" "

        cout<<endl;

    

  
// Код драйвера

int main() 

    int n = 7; // Работает только когда n нечетно

    generateSquare (n); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для генерации магических квадратов нечетного размера
#include<stdio.h>
#include<string.h>

  
// Функция для генерации магических квадратов нечетного размера

void generateSquare(int n)

{

    int magicSquare[n][n];

  

    // установить все слоты как 0

    memset(magicSquare, 0, sizeof(magicSquare));

  

    // Инициализировать позицию для 1

    int i = n/2;

    int j = n-1;

  

    // Один за другим помещаем все значения в магический квадрат

    for (int num=1; num <= n*n; )

    {

        if (i==-1 && j==n) // 3-е условие

        {

            j = n-2;

            i = 0;

        }

        else

        {

            // 1-й помощник условия, если следующий номер

            // выходит из правой стороны квадрата

            if (j == n)

                j = 0;

  

            // 1-й помощник условия, если следующий номер

            // это выходит из верхней стороны квадрата

            if (i < 0)

                i=n-1;

        }

        if (magicSquare[i][j]) // 2-е условие

        {

            j -= 2;

            i++;

            continue;

        }

        else

            magicSquare[i][j] = num++; // установить номер

  

        j++; i--; // 1-е условие

    }

  

    // Печать магического квадрата

    printf("The Magic Square for n=%d:\nSum of "

       "each row or column %d:\n\n",  n, n*(n*n+1)/2);

    for (i=0; i<n; i++)

    {

        for (j=0; j<n; j++)

            printf("%3d ", magicSquare[i][j]);

        printf("\n");

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int n = 7; // Работает только когда n нечетно

    generateSquare (n);

    return 0;

}

Джава

// Java-программа для генерации магических квадратов нечетного размера

import java.io.*;

  

class GFG 

{

    // Функция для генерации магических квадратов нечетного размера

    static void generateSquare(int n)

    {

        int[][] magicSquare = new int[n][n];

          

        // Инициализировать позицию для 1

        int i = n/2;

        int j = n-1;

   

        // Один за другим помещаем все значения в магический квадрат

        for (int num=1; num <= n*n; )

        {

            if (i==-1 && j==n) // 3-е условие

            {

                j = n-2;

                i = 0;

            }

            else

            {

                // 1-й помощник условия, если следующий номер

                // выходит из правой стороны квадрата

                if (j == n)

                    j = 0;

                      

                // 1-й помощник по условию, если следующий номер

                // выходит из верхней стороны квадрата

                if (i < 0)

                    i=n-1;

            }

              

            // 2-е условие

            if (magicSquare[i][j] != 0

            {

                j -= 2;

                i++;

                continue;

            }

            else

                // установить номер

                magicSquare[i][j] = num++; 

                  

            // 1-е условие

            j++;  i--; 

        }

   

        // распечатать магический квадрат

        System.out.println("The Magic Square for "+n+":");

        System.out.println("Sum of each row or column "+n*(n*n+1)/2+":");

        for(i=0; i<n; i++)

        {

            for(j=0; j<n; j++)

                System.out.print(magicSquare[i][j]+" ");

            System.out.println();

        }

    }

      

    // драйверная программа

    public static void main (String[] args) 

    {

        // Работает только когда n нечетно

        int n = 7;

        generateSquare(n);

    }

}

  
// Предоставлено Прамод Кумар

питон

# Python программа для генерации
# нечетного размера магические квадраты
# Функция для генерации нечетных
# размер магических квадратов

  

def generateSquare(n):

  

    # 2-D массив со всеми

    # слотов установлено в 0

    magicSquare = [[0 for x in range(n)]

                      for y in range(n)]

  

    # инициализировать позицию 1

    i = n / 2

    j = n - 1

      

    # Заполните волшебный квадрат

    # путем размещения значений

    num = 1

    while num <= (n * n):

        if i == -1 and j == n: # 3-е условие

            j = n - 2

            i = 0

        else:

              

            # следующий номер выходит из

            # правая сторона квадрата

            if j == n:

                j = 0

                  

            # следующий номер идет

            # из верхней стороны

            if i < 0:

                i = n - 1

                  

        if magicSquare[int(i)][int(j)]: # 2-е условие

            j = j - 2

            i = i + 1

            continue

        else:

            magicSquare[int(i)][int(j)] = num

            num = num + 1

                  

        j = j + 1

        i = i - 1 # 1-е условие

   

  

    # Печать магического квадрата

    print ("Magic Squre for n =", n)

    print ("Sum of each row or column"

            n * (n * n + 1) / 2, "\n")

      

    for i in range(0, n):

        for j in range(0, n):

            print('%2d ' % (magicSquare[i][j]), 

                                     end = '')

              

            # Для отображения вывода

            # в матричной форме

            if j == n - 1

                print()

  
Код водителя

  
# Работает только когда n нечетно

n = 7

generateSquare(n)     

  
# Этот код добавлен
# Харшит Агравал

C #

// C # программа для генерации магических квадратов нечетного размера

using System;

  

class GFG {

      

    // Функция для генерации магических квадратов нечетного размера

    static void generateSquare(int n)

    {

        int[, ] magicSquare = new int[n, n];

          

        // Инициализировать позицию для 1

        int i = n / 2;

        int j = n - 1;

  

        // Один за другим помещаем все значения в магический квадрат

        for (int num = 1; num <= n * n; )

        {

            if (i == -1 && j == n) // 3-е условие

            {

                j = n - 2;

                i = 0;

            }

            else

            {

                // 1-й помощник условия, если следующий номер

                // выходит из правой стороны квадрата

                if (j == n)

                    j = 0;

                      

                // 1-й помощник по условию, если следующий номер

                // выходит из верхней стороны квадрата

                if (i < 0)

                    i = n - 1;

            }

              

            // 2-е условие

            if (magicSquare[i, j] != 0) 

            {

                j -= 2;

                i++;

                continue;

            }

            else

                // установить номер

                magicSquare[i, j] = num++; 

                  

            // 1-е условие

            j++; i--; 

        }

  

        // распечатать магический квадрат

        Console.WriteLine("The Magic Square for "

                                           + n + ":");

        Console.WriteLine("Sum of each row or column "

                         + n * (n * n + 1) / 2 + ":");

                           

        for(i = 0; i < n; i++)

        {

            for(j = 0; j < n; j++)

                Console.Write(magicSquare[i, j] + " ");

            Console.WriteLine();

        }

    }

      

    // драйверная программа

    public static void Main () 

    {

          

        // Работает только когда n нечетно

        int n = 7;

          

        generateSquare(n);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для генерации нечетного размера
// магические квадраты

  
// Функция для генерации нечетного размера
// магические квадраты

function generateSquare($n)

{

  

    // установить все слоты как 0

    $magicSquare;

    for ($i = 0; $i < $n; $i++)

        for ($j = 0; $j < $n; $j++)

            $magicSquare[$i][$j] = 0;

  

    // Инициализировать позицию для 1

    $i = (int)$n / 2;

    $j = $n - 1;

  

    // Один за другим помещаем все значения в

    // магический квадрат

    for ($num = 1; $num <= $n * $n; )

    {

          

        // 3-е условие

        if ($i == -1 && $j == $n

        {

            $j = $n-2;

            $i = 0;

        }

        else

        {

            // 1-й помощник условия, если

            // следующий номер уходит

            // правой стороны квадрата

            if ($j == $n)

                $j = 0;

  

            // 1-й помощник условия, если

            // следующий номер идет к

            // вне квадрата

            // боковая сторона

            if ($i < 0)

                $i = $n-1;

        }

          

        // 2-е условие

        if ($magicSquare[$i][$j]) 

        {

            $j -= 2;

            $i++;

            continue;

        }

        else

          

            // установить номер

            $magicSquare[$i][$j] = $num++; 

  

        // 1-е условие

        $j++; $i--; 

    }

  

    // Печать магического квадрата

    echo "The Magic Square for n = " . $n

        . ":\nSum of each row or column "

        . $n * ($n * $n + 1) / 2;

          

    echo "\n\n";

    for ($i = 0; $i < $n; $i++)

    {

        for ($j = 0; $j < $n; $j++)

            echo $magicSquare[$i][$j] . " ";

        echo "\n";

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

  
// Работает только когда n нечетно

$n = 7; 

generateSquare ($n);

      
// Этот код предоставлен mits.
?>


Выход:

The Magic Square for n=7:
Sum of each row or column 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.

Ссылки:
http://en.wikipedia.org/wiki/Magic_square

Эта статья составлена Aashish Barnwal и рецензирована командой GeeksforGeeks. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes