Генератор магических квадратов - C (СИ)

Узнай цену своей работы

Формулировка задачи:

По лабе задали написать программу которая выводит магический квадрат со стороной n, заполненный числами 1..n^2. Подкиньте идею как сгенерировать магический квадрат.
Условие 1..n^2 не обязательно.
Первая моя идея, это создание квадрата с элементами 1..n(каждое число встречается n раз). Идея решения такова: посимвольно заполняем матрицу элементами, которых еще не было в этом столбце, строке, если это диагональный элемент, то и на диагоналях. Эта идея потерпела крах, в плане реализации(есть некоторые ошибки, которые найти не могу), в плане правильности самого алгоритма(как оказалось, построить магический квадрат из чисел 1..n нельзя). Вот руины моих мыслей:
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
void init(int *boo[], int **a[], int n, int x, int y)
{
    int i, j;
 
    for(i = 0; i < n; i++) (*boo)[i] = 0;
    for(i = 0; i < n; i++)
        if ((*a)[x][i] != 0) (*boo)[(*a)[x][i] - 1] = 1;
    for(i = 0; i < n; i++)
        if ((*a)[i][y] != 0) (*boo)[(*a)[i][y] - 1] = 1;
    if (x == y)
        for(i = 0; i < n; i++)
            if ((*a)[i][i] != 0) (*boo)[(*a)[i][i]- 1] = 1;
    if (x + y - 1 == n)
        for(i = 0; i < n; i++)
            if ((*a)[n - i - 1][i] != 0) (*boo)[(*a)[n - i - 1][i] - 1] = 1;
}
 
void create(int **a[], const int n)
{
    int i, j, k, l, num, *boo;
 
    boo = (int *)malloc(n * sizeof(int));
    *a = (int *)malloc(n * sizeof(int));
    for(i = 0; i < n; i++)
    {
        (*a)[i] = (int *)malloc(n * sizeof(int));
    }
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            (*a)[i][j] = 0;
 
    srand(time(NULL));
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
        {
            num = rand() % (n - j);
            init(&boo, a, n, i, j);
            k = -1; l = 0;
            while (k != num) if (!boo[l++]) k++;
            (*a)[i][j] = l;
        }
    free(boo);
}
 
void printArr(const int *a[], const int n)
{
    int i, j, nn;
    char *s;
 
    nn = n * 4 + 1;
    s = (char*)malloc(nn * sizeof(char));
    strcpy(s, "");
    for(i = 0; i < nn; i++) strcat(s, "-");
    if (n == 0) printf("Пусто...");
    for(i = 0; i < n; i++)
    {
        printf("%s\n|", s);
        for(j = 0; j < n; j++)
        {
           printf("%3d|", a[i][j]);
        }
        printf("\n");
    }
    printf("%s", s);
    free(s);
    printf("\n\n");
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    int **a, n;
    printf("Какого размера магический квадрат?\n");
    scanf("%d", &n);
    create(&a, n);
    printf("Сформирован магический квадрат из %d элементов:\n\n", n * n);
    printArr(a, n);
    free(a);
    return 0;
}
Вторая идея обратиться к википедии, вдруг есть готовое решение моей проблемы. Но и тут не все хорошо, алгоритм построения зависит от конкретного числа n, а это не то, к чему я стремлюсь.
Я довольно сильно нагрел стул, пытаясь придумать решение, и теперь мысль о заполнении всей матрицы числом n возникает все чаще. Подробная формулировка задачи: 'Написать программу, генерирующую магические квадраты заданного пользователем размера.'

Решение задачи: «Генератор магических квадратов»

textual
Листинг программы
int *a,n,nn,sum;
void print()
{
    int r,c;
    for(r=0; r<n; r++,printf("\n"))
        for(c=0; c<n; c++) printf("%3d",a[r*n+c]);
    printf("\n");
}
void sqr(int p)
{
    int i,j,k,s;
    for(i=1; i<=nn; i++)
    {
        for(j=0; j<p; j++)
            if(a[j]==i) break;
        if(j==p)
        {
            a[p]=i;
            if((p+1)%n==0)
            {
                k=p/n*n;
                for(s=j=0; j<n; j++) s+=a[k+j];
                if(s<sum) continue;
                if(s>sum) return;
            }
            else
            if(p/n==n-1)
            {
                k=p%n;
                for(s=j=0; j<nn; j+=n) s+=a[j+k];
                if(s<sum) continue;
                if(s>sum) return;
                if(!k)
                {
                    for(s=0,j=n-1; j>=0; j--,k+=n) s+=a[k+j];
                    if(s<sum) continue;
                    if(s>sum) return;
                }
            }
            if(p+1<nn) sqr(p+1);
            else
            {
                for(s=j=0; j<n; j++) s+=a[j*n+j];
                if(s<sum) continue;
                if(s>sum) return;
                print();
            }
        }
    }
}
void main(int argc,char* argv[])
{   
    int i;
 
    printf("n: ");
    scanf("%d",&n);
    nn=n*n;
    a=(int*)malloc(nn*sizeof(int));
    for(sum=0,i=1; i<=nn; i++) sum+=i;
    sum/=n;
    sqr(0);
    free(a);
    system("pause");
}

Объяснение кода листинга программы

В этом коде реализована функция генерации магических квадратов.

  1. *int a,n,nn,sum;**
    • Объявляются четыре переменные:
      • a - указатель на массив для хранения получившегося магического квадрата;
      • n - количество сторон квадрата;
      • nn - общее количество ячеек в квадрате (n*n);
      • sum - сумма всех чисел от 1 до nn, которая будет использоваться для проверки корректности полученного квадрата.
  2. void print()
    • Функция для вывода полученного магического квадрата на экран.
      • Используется два вложенных цикла:
      • Внешний цикл для прохода по строкам квадрата (от 0 до n-1).
      • Внутренний цикл для прохода по столбцам текущей строки (от 0 до n-1).
      • В каждой ячейке квадрата (a[r*n+c]) выводится значение элемента.
  3. void sqr(int p)
    • Функция для генерации начального фрагмента магического квадрата.
      • Используется рекурсивный подход.
      • Если текущий фрагмент квадрата заполнен (p==nn), то вызывается функция print() для его вывода.
      • Если текущий фрагмент квадрата пуст (p<nn), то вызывается функция sqr(p+1) для генерации следующего фрагмента.
      • Если текущий фрагмент квадрата заполнен (p<nn), но не является корректным магическим квадратом (сумма элементов в строке или столбце больше или меньше ожидаемой), то возвращается из функции, чтобы не портить результат.
  4. *void main(int argc,char argv[])**
    • Главная функция программы.
      • Запрашивается у пользователя количество сторон квадрата (n).
      • Вычисляется общее количество ячеек в квадрате (nn).
      • Выделяется память под массив a.
      • Инициализируется сумма чисел от 1 до nn.
      • Вызывается функция sqr(0) для генерации начального фрагмента магического квадрата.
      • Освобождается память, выделенная под массив a.
      • Программа ожидает нажатия клавиши для выхода. Код генерирует магический квадрат, выводит его на экран и запрашивает у пользователя подтверждение корректности полученного результата. Если пользователь нажимает любую клавишу, программа завершается. Если пользователь нажимает клавишу 'p', программа выводит полученный магический квадрат. Если пользователь нажимает клавишу 's', программа выводит сумму чисел в строке, столбце или магическом квадрате в целом. Если пользователь нажимает клавишу 'm', программа выводит магический квадрат, полученный из суммы чисел в строке или столбце.

Оцени полезность:

12   голосов , оценка 4.167 из 5
Похожие ответы