Witam, mam mały problem z optymalizacją mojego kodu na znalezenie magicznego kwadratu. Dla n=3 działa dobrze, ale dla większych n wywala błąd. Już nie mam pojęcia co może być tutaj źle. Byłbym wdzięczny jeśli ktoś rzuciłby na to okiem :).
tab[]- tablica o rozmiarze nn, do której wpisuje kolejne liczby kwadratu
liczby[] - tablica booli o rozmiarze nn, która mówi czy liczba zostałą wykorzystana, np. jeżeli liczby[0]==true, to znaczy, że użyliśmy gdzieś wcześniej liczby 1, liczby[2]==true - uzylismy juz liczby 3 itd.
suma - suma wierszy i kolumn wyznaczana ze wzoru n*(n*n+1)/2
pozycja - aktualnie badana pozycja w tablicy tab (indeks komórki, do której akutalnie wstawiamy liczbę)
liczba - aktualnie badana liczba
Działa to mniej więcej tak dla n=3 idziemy od początku tablicy, bierzemy liczbę 1, potem 2 i 3. 1+2+3!=15, więc bierzemy 1,2,4 potem 1,2,5 itd dojdziemy do 1,2,10, ale 10 jest większe niż 3*3, więc cofamy się pozycje wczęsniej i bierzemy 1,3,2 itd. I tak ciągle dopóki suma wierszy, kolumn i przekątnych nie będzie się zgadzać.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define n 3
void wypisz(int tab[])
{
for(int i=0; i<n*n; i++)
{
if(i%n==0 && i!=0) printf("\n");
printf("%d ", tab[i]);
}
}
int kwadrat(int tab[], bool liczby[], int suma, int pozycja, int liczba)
{
if(liczba>n*n)
{
liczby[tab[pozycja-1]-1]=false;
return kwadrat(tab, liczby, suma, pozycja-1, tab[pozycja-1]+1);
}
if(liczby[liczba-1]==false)
{
tab[pozycja]=liczba;
}
else return kwadrat(tab, liczby, suma, pozycja, liczba+1);
int suma_wiersza=0;
int suma_kolumn=0;
int suma_przekatnej=0;
//suma wierszy
if(pozycja%n==(n-1))
{
suma_wiersza=0;
for(int j=pozycja-(n-1); j<=pozycja; j++) suma_wiersza+=tab[j];
if(suma_wiersza!=suma) return kwadrat(tab, liczby, suma, pozycja, liczba+1);
}
//suma kolumn
if(pozycja>=n*n-n)
{
suma_kolumn=0;
for(int j=pozycja-(n*n-n); j<=pozycja; j+=n) suma_kolumn+=tab[j];
if(suma_kolumn!=suma) return kwadrat(tab, liczby, suma, pozycja, liczba+1);
}
//suma przekatnych
if(pozycja==n*n-n)
{
suma_przekatnej=0;
for(int j=n-1; j<=n*n-n; j+=(n-1)) suma_przekatnej+=tab[j];
if(suma_przekatnej!=suma) return kwadrat(tab, liczby, suma, pozycja, liczba+1);
}
if(pozycja==n*n-1)
{
suma_przekatnej=0;
for(int j=0; j<=n*n-1; j+=(n+1)) suma_przekatnej+=tab[j];
if(suma_przekatnej!=suma) return kwadrat(tab, liczby, suma, pozycja, liczba+1);//roznica);
}
liczby[liczba-1]=true;
if(pozycja==n*n-1)
{
wypisz(tab);
exit(0);
}
return kwadrat(tab, liczby, suma, pozycja+1, 1);
}
int main(int argc, char *argv[])
{
int suma;
suma=n*(n*n+1)/2;
int tab[n*n];
bool liczby[n*n];
for(int i=0; i<n*n; i++)
{
liczby[i]=false;
tab[i]=0;
}
kwadrat(tab, liczby, suma, 0, 1);
return 0;
}