Magiczny kwadrat

Odpowiedz Nowy wątek
2011-07-21 00:02
eryk
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

edytowany 1x, ostatnio: madmike, 2016-12-13 18:26

Pozostało 580 znaków

2011-07-21 00:47
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)


Pół giga extra na dropboxie? Pół giga extra na dropboxie! Tyle wygrać! >>Klik here<<
edytowany 2x, ostatnio: unikalna_nazwa, 2011-07-21 00:51

Pozostało 580 znaków

2011-07-21 08:50
eryk
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

Pozostało 580 znaków

2011-07-21 12:26
0

Rekurencyjnie z powrotami sprawdzaj wszystkie możliwości.

edytowany 1x, ostatnio: Afish, 2011-07-21 12:26

Pozostało 580 znaków

2011-07-21 17:05
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

Pół giga extra na dropboxie? Pół giga extra na dropboxie! Tyle wygrać! >>Klik here<<
edytowany 1x, ostatnio: unikalna_nazwa, 2011-07-21 17:14

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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