Magiczny kwadrat

0

Witam!
Mam magiczny kwadrat 3x3, w nim maksymalnie 3 pola są nieuzupelnione i muszę je uzupelnić. Latwo widac, że jesli puste pola nie sa po przekatnej, to jest jeden taki wiersz bądź kolumna, w której nie ma żadnego nieuzupelnionego pola. Moge wiec obliczyc te maksymalna sume w wierszu/kolumnie, a potem tak uzupelnic pozostale pola, aby sie wszystko zgadzalo.

Nie wiem niestety jak uzupelniac te pola? Zalozmy ze przy wczytywaniu zapamietuje sobie gdzie sa puste pola, trzymam te pozycje w jakiej tablocy. Jak odpowiednio uzupelnic te pola?

eryk

w c++
eryk

0

nie rób tablicy nieuzupełnionych pól tylko tablicę reprezentującą magiczny kwadrat

najpierw znajdź sumę, a potem przeleć po wierszach / kolumnach szukając tych w których brakuje jednej cyfry i uzupełnij odejmując wiadome od znalezionej sumy, powtarzaj aż całość będzie uzupełniona

środkowe pole w kwadracie 3x3 to zawsze 1/3 sumy
suma w kwadracie 3x3 to zawsze 3/2 * (dowolne_pole_oprócz_środkowego + dowolne_pole_naprzeciwko)

0

Mam taki kod:

#include <iostream>
#include <limits.h>

using namespace std;

int tab[3][3];
bool wiersze[3];
bool kolumny[3];

int main()
{
    ios_base::sync_with_stdio(0);
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
        {
            cin >> tab[i][j];
            if(tab[i] == 0)
            {
                wiersze[j] = true;
                kolumny[i] = true;
            }
        }
    int maxx;
    for(int i=0; i<3; i++)
        if(!wiersze[i])
        {
            maxx = tab[i][0] + tab[i][1] + tab[i][2];
        }
    for(int i=0; i<3; i++)
        if(!kolumny[i])
        {
            maxx = tab[0][i] + tab[1][i] + tab[2][i];
        }

Znajduje nim maxymalna sume w kwadracie. No dobra, ale nie wiem jak to dalej zrobic? Bo leciec po wierszach i tam gdzie puste wstawiac cos to okej, ale jak np. mam 2 zera w wierszu?

eryk

0

Rekurencyjnie z powrotami sprawdzaj wszystkie możliwości.

0

Standardowo - niesprawdzone:

#include <iostream>
#include <limits.h>

using namespace std;

int tab[3][3];
int wiersze[3];
int kolumny[3];
int brakuje;

int main()
{
    ios_base::sync_with_stdio(0);
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
        {
            cin >> tab[i][j];
            if(tab[i][j] == 0)
            {
                wiersze[j] ++; // liczba brakujących pól w wierszu
                kolumny[i] ++; // w kolumnie
                brakuje ++; // w kwadracie
            }
        }
    int maxx = 0;
    // obliczenie sumy magicznego kwadratu
    for(int i=0; i < 3 && maxx == 0; i++)
    {
        for(int j = 0; j < 3 && maxx == 0; j ++)
        {
            if(i == 1 && j == 1) continue; // pomiń środkowe pole

            int x = 2 - i; // znalezienie przeciwnego pola
            int y = 2 - j; // -(j - 1) + 1
            if(tab[i][j] && tab[x][y]) // jeśli oba pola są uzupełnione (różne od 0)
            {
                maxx = (3 / 2.) * (tab[i][j] + tab[x][y]); // obliczenie sumy ze wzoru
            }
        }
    }

    while(brakuje)
    {
        for(int i = 0; i < 3; i ++) // lecimy po kolumnach
        {
            if(kolumny[i] != 1) continue; // jeśli liczba brakujących pól w tej kolumnie jest różna od 1 to nie mamy co tu robić
            for(int j = 0; j < 3; j ++)
            {
                if(!tab[i][j])
                {
                    tab[i][j] = maxx - tab[i][(j + 1) % 3] - tab[i][(j + 2) % 3]; // odjęcie od sumy dwóch sąsiednich pól z kolumny
                    kolumny[i] --;
                    wiersze[j] --;
                    brakuje --; // zmniejszenie liczby brakujących pól
                }
            }
        }
        for(int j = 0; j < 3; j ++) // to samo po wierszach
        {
            if(wiersze[j] != 1) continue;
            for(int i = 0; i < 3; i ++)
            {
                if(!tab[i][j])
                {
                    tab[i][j] = maxx - tab[(i + 1) % 3][j] - tab[(i + 2) % 3][j];
                    kolumny[i] --;
                    wiersze[j] --;
                    brakuje --;
                }
            }
        }
    } // TODO: DRY, poprawić warunki bo prawdopodobnie istnieją dane dla których powstanie nieskończona pętla

    // kwadrat uzupełniony

1 użytkowników online, w tym zalogowanych: 0, gości: 1