Генератор магических квадратов

@Хадукен · Регистрация: 01.08.2016

Author24 — интернет-сервис помощи студентам

По лабе задали написать программу которая выводит магический квадрат со стороной n, заполненный числами 1..n^2. Подкиньте идею как сгенерировать магический квадрат.

Добавлено через 2 минуты
Условие 1..n^2 не обязательно.

Добавлено через 6 минут
Первая моя идея, это создание квадрата с элементами 1..n(каждое число встречается n раз). Идея решения такова:
посимвольно заполняем матрицу элементами, которых еще не было в этом столбце, строке, если это диагональный элемент, то и на диагоналях.
Эта идея потерпела крах, в плане реализации(есть некоторые ошибки, которые найти не могу), в плане правильности самого алгоритма(как оказалось, построить магический квадрат из чисел 1..n нельзя).
Вот руины моих мыслей:

C

#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;
}

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

Добавлено через 5 минут
Я довольно сильно нагрел стул, пытаясь придумать решение, и теперь мысль о заполнении всей матрицы числом n возникает все чаще.

Подробная формулировка задачи: 'Написать программу, генерирующую магические квадраты заданного пользователем размера.'

@~~MansMI~~ · 17.09.2016, 17:03

при n=3;4 считает, при 5 терпения не хватает(а может и жизни)

C

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");
}

@Хадукен · 17.09.2016, 17:30 **[ТС]**

MansMI, думаю все же заполнить матрицу числом n. Почитал в различных источниках и сделал вывод: создать магический квадрат заданного размера программным способом нельзя...

@gazlan · 17.09.2016, 21:00

ЕЩЁ ДВА МЕТОДА ПОСТРОЕНИЯ ЛАТИНСКИХ КВАДРАТОВ

Второй метод из указанной книги применим для построения латинского квадрата любого порядка.

@TheCalligrapher · 17.09.2016, 21:24

Сообщение от gazlan

латинского квадрата

В вопросе идет речь о магических квадратах, а не о латинских квадратах.

@gazlan · 17.09.2016, 23:52

Не по теме:

Действительно, попутал.

@ata · 18.09.2016, 07:17

Я почитал в Википедии, что такое магический квадрат и у меня родилось подозрение, что можно тупо заполнить квадрат случайными числами, а подбирать только те, что в углах.

@TheCalligrapher · 18.09.2016, 08:43

Сообщение от ata

можно тупо заполнить квадрат случайными числами, а подбирать только те, что в углах.

И каким же это образом, "подбирая только те, что в углах", вы собираетесь обеспечить равенство сумм во всех столбцах и строках?

@ata · 18.09.2016, 10:27

Сообщение от TheCalligrapher

И каким же это образом, "подбирая только те, что в углах", вы собираетесь обеспечить равенство сумм во всех столбцах и строках?

Действительно... Ну, значит, подбирать надо на краях.

@~~MansMI~~ · 18.09.2016, 10:32

Сообщение от Хадукен

По лабе задали написать программу

и что же будет предъявлено?

@Хадукен · 18.09.2016, 16:22 **[ТС]**

MansMI, понадеюсь на снисходительность, если не прокатит, то буду пытаться доказать что построить магический квадрат размера N нельзя.

C

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
 
void create(int **a[], const int n)
{
    int i, j;
 
    *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] = n;
}
 
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;
}

Добавлено через 1 минуту
В этом решении вся матрица заполняется числом n.

@LFC · 19.09.2016, 06:55

Хадукен, для нечетных N

C

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int N, M, Q, i, j, x = 1, pir, **a = NULL;
    puts("Enter an odd number greater than 1:");
    if(1 != scanf("%d", &N) || !(N & 0x01) || N < 3){
        puts("Error enter!");
        exit(3);
    }
    M = 2 * N - 1;
    a = malloc(M * sizeof(a));
    if(!a){
        puts("Error!");
        exit(1);
    }
    for(i = 0; i < M; i++){
        a[i] = malloc(M * sizeof(int));
        if(!a[i]){
            puts("Error!!!");
            exit(2);
        }
    }
    for(i = 0; i < M; i++)
        for(j = 0; j < M; j++)
            a[i][j] = 0;
    for(Q = N - 1; Q < M; Q++)
        for(i = Q, j = Q - (N - 1); j <= Q && i >= Q - (N - 1); i--, j++, x++)
            a[i][j] = x;
    pir = (M - N) / 2;
    for(i = 0; i < pir; i++)
        for(j = 0; j < M; j++)
            if(a[i][j] != 0)
                a[i + N][j] = a[i][j];
    for(i = M - 1; i > M - 1 - pir; i--)
        for(j = 0; j < M; j++)
            if(a[i][j] != 0)
                a[i - N][j] = a[i][j];
    for(j = 0; j < pir; j++)
        for(i = 0; i < M; i++)
            if(a[i][j] != 0)
                a[i][j + N] = a[i][j];
    for(j = M - 1; j > M - 1 - pir; j--)
        for(i = 0; i < M; i++)
            if(a[i][j] != 0)
                a[i][j - N] = a[i][j];
    for(i = pir; i < M - pir; i++){
        for(j = pir; j < M - pir; j++){
            if(a[i][j] != 0)
                printf("%4d", a[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

@Хадукен · 20.09.2016, 11:42 **[ТС]**

LFC, благодарствую.

Добавлено через 4 минуты
Как оказалось, строить магический квадрат заоблочных размеров не требуется(в условии, конечно же, об этом не сообщили). Нужно что бы программа работала хотя бы для 3 - 4.

Добавлено через 4 минуты
MansMI, можете пояснить идею вашей программы?

@~~MansMI~~ · 20.09.2016, 13:05

которую? я вот в отличие от предыдущей все пытался ускорить, но у мя комп старый, он если надолго 100% то вылетает
, а эта при n=4 норм считает

C++

int *a,n,nn,ns,sum;
void sqr(int p);
void sqrh(int p);
void sqrv(int p);
void sqrf(int p);
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 sqrh(int p)
{
    int i,j,h,k,s,sm;
    void(*f)(int);
    if((p+1)/n==n-1) f=sqrv;
    else f=sqr;
    k=p/n*n;
    for(sm=i=0; i<n-1; i++) sm+=a[k+i];
    for(i=1; i<=nn; i++)
    {
        for(j=0; j<p; j++)
            if(a[j]==i) break;
        if(j==p)
        {
            s=sm+i;
            if(s==sum)
            {
                a[p]=i;
                if(p>n+n)
                    for(s=j=0; j<n; j++,s=0)
                    {
                        for(h=0; h<=k; h+=n) s+=a[h+j];
                        if(s>=sum)return;
                    }
                f(p+1);
                return;
            }
            if(s>sum) return;
        }
    }
}
void sqrv(int p)
{
    int i,j,k,s,sm;
    void(*f)(int)=sqr;
    if(p+2==nn) f=sqrf;
    else f=sqrv;
    k=p%n;
    for(sm=i=0; i<nn-n; i+=n) sm+=a[i+k];
    for(i=1; i<=nn; i++)
    {
        for(j=0; j<p; j++)
            if(a[j]==i) break;
        if(j==p)
        {
            s=sm+i;
            if(s==sum)
            {
                a[p]=i;
                if(!k)
                {
                    for(s=i,j=n-1; j; j--,k+=n) s+=a[k+j];
                    if(s!=sum) return;
                }
                f(p+1);
                return;
            }
            if(s>sum) return;
        }
    }
}
void sqrf(int p)
{
    int i,j,s;
    for(i=1; i<=nn; i++)
    {
        for(j=0; j<p; j++)
            if(a[j]==i) break;
        if(j==p)
        {
            a[p]=i;
            for(s=i,j=0; j<n-1; j++) s+=a[j*n+j];
            if(s!=sum) return;
            print();
            //_getch();
            ns++;
            return;
        }
    }
}
void sqr(int p)
{
    int i,w,m=nn-p;
    int *pa,*pp=a+p;
    void(*f)(int)=sqr;
    if((p+2)%n==0) f=sqrh;
    else f=sqr;
    for(w=0,i=1; w<m; i++)
    {
        for(pa=a; pa<pp; pa++)
            if(*pa==i) break;
        if(pa==pp)
        {
            w++;
            *pp=i;
            f(p+1);
        }
    }
}
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;
    ns=0;
    sqr(0);
    printf("%d\n",ns);
    free(a);
    system("pause");
}

@Хадукен · 20.09.2016, 13:24 **[ТС]**

MansMI, мне интересен Ваш принцип заполнения матрицы. Как его реализовать?

@~~MansMI~~ · 20.09.2016, 13:28

да, тупо числами от 1-n*n , но ни строка, ни столбец, диагональ в сумме не могут не дать "магического" числа sum

@yvp · 13.02.2017, 13:23

Сообщение от Хадукен

MansMI, ... Почитал в различных источниках и сделал вывод: создать магический квадрат заданного размера программным способом нельзя...

Ну, почему нельзя? Именно программным и можно! Вот здесь http://sportloto.pp.ru/compone... Itemid,14/ - генератор и база программно-сгенерированных квадратов. Принцип построения тоже простой - http://sportloto.pp.ru/content... comment-69

@Cratas_Thymos · 08.02.2021, 04:53

те ссылки которые здесь выложили на сервис формирования магического квадрата полная дичь! теперь вопрос существует ли код создания магического квадрата?

Добавлено через 37 минут

Сообщение от Хадукен

По лабе задали написать программу которая выводит магический квадрат со стороной n, заполненный числами 1..n^2. Подкиньте идею как сгенерировать магический квадрат.

Добавлено через 2 минуты
Условие 1..n^2 не обязательно.

Добавлено через 6 минут
Первая моя идея, это создание квадрата с элементами 1..n(каждое число встречается n раз). Идея решения такова:
посимвольно заполняем матрицу элементами, которых еще не было в этом столбце, строке, если это диагональный элемент, то и на диагоналях.
Эта идея потерпела крах, в плане реализации(есть некоторые ошибки, которые найти не могу), в плане правильности самого алгоритма(как оказалось, построить магический квадрат из чисел 1..n нельзя).
Вот руины моих мыслей:

C

#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;
}

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

Добавлено через 5 минут
Я довольно сильно нагрел стул, пытаясь придумать решение, и теперь мысль о заполнении всей матрицы числом n возникает все чаще.

Подробная формулировка задачи: 'Написать программу, генерирующую магические квадраты заданного пользователем размера.'

ну вы справились с лабой? просто это совсем не просто, я научился делать в эксель квадраты с нечетным количеством сторон, может научусь с четным, но это совсем не просто. и еще условие "1..n^2 " оно вообще не выполнимо, это не решенная задача математики.

@zeroalef · 08.02.2021, 18:48

Сообщение от Cratas_Thymos

это не решенная задача математики

Студентам всегда дают известные нерешенные задачи. Где еще искать их решения как не среди молодых дарований? Одно дело когда преподаватель опишет проблему, покажет известные попытки ее решения, а потом предложит студентам самостоятельно подумать над проблемой. И совсем другое -- завуалированно предложить доказать гипотезу Римана.

@Хадукен 1 / 1 / 5 Регистрация: 01.08.2016 Сообщений: 71
	20.09.2016, 13:24 [ТС]	15
	MansMI, мне интересен Ваш принцип заполнения матрицы. Как его реализовать? 0

@Хадукен 1 / 1 / 5 Регистрация: 01.08.2016 Сообщений: 71
	17.09.2016, 17:30 [ТС]	3
	MansMI, думаю все же заполнить матрицу числом n. Почитал в различных источниках и сделал вывод: создать магический квадрат заданного размера программным способом нельзя... 1

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	17.09.2016, 21:00	4
	ЕЩЁ ДВА МЕТОДА ПОСТРОЕНИЯ ЛАТИНСКИХ КВАДРАТОВ Второй метод из указанной книги применим для построения латинского квадрата любого порядка. 1

@TheCalligrapher Вездепух 11691 / 6370 / 1723 Регистрация: 18.10.2014 Сообщений: 16,052
	17.09.2016, 21:24	5
	Сообщение от gazlan латинского квадрата В вопросе идет речь о магических квадратах, а не о латинских квадратах. 2

@gazlan
	17.09.2016, 23:52 #6
	Не по теме: Действительно, попутал. 0

@ata 269 / 253 / 186 Регистрация: 28.10.2015 Сообщений: 723
	18.09.2016, 07:17	7
	Я почитал в Википедии, что такое магический квадрат и у меня родилось подозрение, что можно тупо заполнить квадрат случайными числами, а подбирать только те, что в углах. 1

@TheCalligrapher Вездепух 11691 / 6370 / 1723 Регистрация: 18.10.2014 Сообщений: 16,052
	18.09.2016, 08:43	8
	Сообщение от ata можно тупо заполнить квадрат случайными числами, а подбирать только те, что в углах. И каким же это образом, "подбирая только те, что в углах", вы собираетесь обеспечить равенство сумм во всех столбцах и строках? 1

@ata 269 / 253 / 186 Регистрация: 28.10.2015 Сообщений: 723
	18.09.2016, 10:27	9
	Сообщение от TheCalligrapher И каким же это образом, "подбирая только те, что в углах", вы собираетесь обеспечить равенство сумм во всех столбцах и строках? Действительно... Ну, значит, подбирать надо на краях. 0

@~~MansMI~~ Заблокирован
	18.09.2016, 10:32	10
	Сообщение от Хадукен По лабе задали написать программу и что же будет предъявлено? 0

@Хадукен 1 / 1 / 5 Регистрация: 01.08.2016 Сообщений: 71
	20.09.2016, 11:42 [ТС]	13
	LFC, благодарствую. Добавлено через 4 минуты Как оказалось, строить магический квадрат заоблочных размеров не требуется(в условии, конечно же, об этом не сообщили). Нужно что бы программа работала хотя бы для 3 - 4. Добавлено через 4 минуты MansMI, можете пояснить идею вашей программы? 0

@~~MansMI~~ Заблокирован
	20.09.2016, 13:28	16
	да, тупо числами от 1-n*n , но ни строка, ни столбец, диагональ в сумме не могут не дать "магического" числа sum 0

@yvp 0 / 0 / 0 Регистрация: 13.02.2017 Сообщений: 1
	13.02.2017, 13:23	17
	Сообщение от Хадукен MansMI, ... Почитал в различных источниках и сделал вывод: создать магический квадрат заданного размера программным способом нельзя... Ну, почему нельзя? Именно программным и можно! Вот здесь http://sportloto.pp.ru/compone... Itemid,14/ - генератор и база программно-сгенерированных квадратов. Принцип построения тоже простой - http://sportloto.pp.ru/content... comment-69 0

@zeroalef 200 / 236 / 33 Регистрация: 29.03.2019 Сообщений: 667
	08.02.2021, 18:48	19
	Сообщение от Cratas_Thymos это не решенная задача математики Студентам всегда дают известные нерешенные задачи. Где еще искать их решения как не среди молодых дарований? Одно дело когда преподаватель опишет проблему, покажет известные попытки ее решения, а потом предложит студентам самостоятельно подумать над проблемой. И совсем другое -- завуалированно предложить доказать гипотезу Римана. 0

Генератор магических квадратов

Решение