matrix+verem

C/C++

hello!

a kovetkezo dolgot szeretnem tenni: egy matrixban, minden egyes elemhez kulon vermet rendelni. vmi ilyesmire gondoltam:

typedef struct node{
int val;
struct node* next;
} stack_t;

typedef struct tabla_{
int val;
stack_t* pval;
} tabla_t;

tabla_t tabla[9][9];

nem tudom mennyire elegans vagy nem elegans ez a megoldas, de nem teljesen mukodik... amikor inicializalom a vermet, vagy adok push-olok bele, akkor olyan, mintha semmit sem csinalna. szoval szepen lefut a push, csak eppen a verem erteket nem valtoztatja meg tenylegesen. a push fejlece:
void push( stack_t* stack, int e )

meghivasa:
push( tabla_[i][j].pval, k );

nem hiszem, hogy ezzel gond lenne... de viszont, ha en nem eljarason keresztul, hanem kozvelten probalom a tabla[i][j].pval mutato erteket leellenorizni, hogy NULL-e, akkor ezt a hibauzit kapom forditasnal:

error: request for member `pval' in something not a structure or union

gondolom vmi sulyos es buta hibat kovettem el, de nem tudok rajonni, hogy mi lehet az... van valakinek otlete? vagy hogyan celszeru ezt csinalni?
elore is koszonom :)

  • 1507 megtekintés

( NagyZ v | 2007. 02. 18., v – 00:29 )

tabla[9][9] helyett miert nem csinalsz egy tabla_t *tabla = (tabla_t*)malloc(sizeof(tabla_t)*9*9)) -et?
egy fuggvennyel meg bemappolhatsz mindent a helyere, ha akarod.. :)

( imp | 2007. 02. 18., v – 00:34 )


typedef struct node{
  int val;
  struct node* next;
} stack_t;

typedef struct tabla_{
  int val;
  stack_t* pval;
} tabla_t;

tabla_t tabla[9][9];

void push( stack_t* stack, int e )
push( tabla_[i][j].pval, k );

az utolsó két sor rossz, mert gondolom a pval alapesetben NULL;
a jó úgy lenne, ha nem a pval által mutatott címet adnád át a pushnak, hanem - mivel pval-t akarod megváltoztatni - a pval címét, tehát így: 


void push(stack_t**, int);
...
push(&tabla[i][j].pval, k);

( Nyosigomboc v | 2007. 02. 18., v – 02:00 )

Ha C, akkor a masodik struktura tipusat vagy "struct tabla_" neven vagy "tabla_t"-kent erheted el. Ha C++, akkor jo a "tabla_", de akkor mar inkabb hasznalj STL-t (valoszinu sok C fordito elfogadja igy is, lehet, hogy valamelyik ujabb C szabvanyban ez is benne van, ezt nem tudom).

BTW: minek kell neked ket struktura ugyanarra? nem eleg mondjuk a node, es ebbol letrehozni egy matrixot?

Fel tudnad tenni vhova a teljes kodot? Igy nem latom mit kovettel el a tabla[i][j].pval kododdal. Mire kell neked egy ilyen adatszerkezet? Nem lehet, hogy valamit mar a tervezesnel elneztel? (persze boven elkepzelheto, hogy nem)

A hazik beadasi hatarideje mar sztem eleg sok helyen letelt, ugyhogy feltetelezem nem hazi. Ebben az esetben lehet, hogy erdemesebb valami kulso kodot alkalmazni a listara (STL eleg jo C++ eseten, neten is talalsz eleget, de C-re akar en is kuldhetek egyet).
---------------------
Time is like a drug. Too much of it kills you. - Pratchett

sima C... sudoku megoldo programocskat szeretnek kesziteni (tudom van belole ezer db leiras, algoritmus neten, de en sajat magam szeretnek irni egyet... otletem van is ra)
a kodot inkabb elkuldenem emailben.

szerk: ha adsz egy mailcimet... :)

---
"A legjobb dolgok az életben nem dolgok."

Ha mas otleted van, es van egy max. meret, amit a lista ugysem lephet at, akkor is erdemesebb fix statikus tombokkel csinalni ha van memoria (sebessegben kicsit jobb lesz).

(Privi ment)

a vonal alatt tipp egy algoritmusra.. ha inkabb magadtol probalkoznal, ne olvasd el..

---------------------------------------------------
Ezt inkabb (bool-jellegu) tombokkel csinalnam.

int tabla[9][9];
int mimaradt[9][9][9];

tabla[i][j] a sor-oszlop, mondjuk 0 ha meg nem ismert az erteke, 1-9-ig meg ha ismert
mimaradt[i][j][k] pedig hogy az i-edik sor j-edik oszlopaba teheto-e meg k szam (0 vagy 1)
lehetosegek[i][j] hany szam irhato meg be i,j helyre
int maradt 9*9-re inicialicalando, hany cellat kell meg kitoltened (ha 0-ra er, gyoztel)

tabla-t 0-ra inicializalod, mimaradt-ot meg 1-re (lehetosegek ertelemszeruen 9)

Beteszed az ismert tablat, aztan megoldod rekurzivan visszalepeses keresessel ugy, hogy kozben mindig az egyik legkevesebb letegoseggel rendelkezo cellat toltod ki. Redundans az adatszerkezet, konzisztensen kell tartani. A stack-re meg mindig le kell menteni plusz infot, hogy visszalepeskor vissza tudd allitani az allapotot. Mas gond nincs vele, es gyors.

---------------------
Time is like a drug. Too much of it kills you. - Pratchett

wow, egyszer én is pont C-ben írtam sudoku megoldót..
erre viszont nem a legcélszerűbb a stack, hanem amit az elozo kollega irt, inkabb az..

szintén algoritmus, ne olvasd el:

az enyémnek nem a rekurzió volt a lényege, hanem a lehetőségek megszorítása így:
-egy blokkban van 9 mező, ami sor, oszlop, vagy 3x3-as négyzet.
-ezekre a mezőkre fel vannak véve a lehetséges értékek, pl:
1,9 ; 1,9 ; 1,2,3,6 ; 1,2,3,4,6,9 ; 2,3,4,6 ; 1,2,4,6,9 ; 3,4,5,6,7,8 ; 2,5,7,8 ; 4,5,7,8

akkor ebből lesz egy ilyen:
1,9 ; 1,9 ; 2,3,6 ; 2,3,4,6 ; 2,3,4,6 ; 2,4,6 ; 5,7,6,8 ; 5,7,8 ; 5,7,8

mert
- ha egy N elemű mintát pontosan N mezőben talált meg, és a minta egyik eleme sem fordul elő más mezőben az N-en kívül,
akkor az adott mezők elég, ha csak ezt a mintát tartalmazzák (ilyen volt az 5,7,8 háromelemű minta)

-vagy ha N darab olyan N hosszúságú mező van, amik páronként ugyanazt tartalmazzák
akkor más mezők nem vehetik fel ezeket az értékeket (ilyen volt az 1,9 minta)

--

ez úgy hiszem gyorsabb a backtracknél, bár egy menetből nem feltétlenül oldja meg.
a legnehezebb sudokukkal az volt, hogy kétszer kellett lefuttatni, úgy, hogy az első menet tippelni kellett egyet (itt jön be a backtrack) aztán ha nem sikerült megoldania, akkor a másik lehetséges értékkel (tipikusan két lehetőség volt)

A tied is tkepp backtrack, mert visszalep, ha nem tudta kitolteni. Csak van benne egy eleg ugyes plusz optimalizacio, ami le tudja vagni a felesleges probalkozasokat. Igazibol ilyet minden ertelmes algoritmus hasznalhat, mar ha a szerzo rajon a trukkre.
---------------------
Time is like a drug. Too much of it kills you. - Pratchett

hat igen, bar en a backtrack reszet mar meg se irtam, csak arra voltam kivancsi, hogy
papiron meg lehetne-e oldani ugy, hogy nem lepsz vissza. a gyakorlati peldakbol arra jutottam, hogy max egy visszalepes van, szoval ket darab olyan papirra van szukseg,
aminel mind a 81 mezo meg fel van osztva 9 mezore (3x3 praktikusan), szoval 2x (27x27) mezo kell, ez epp rafer egy A4-es matekfüzet lapjára.

( NevemTeve | 2007. 02. 20., k – 16:23 )

Valószínűleg rossz a programod. Tedd ki valamilyen publikus helyre, hátha valaki ránéz.
Megjegyzés: ilyet semmiképp se csinálj: 


typedef struct node {
    int val;
    struct node* next;
} stack_t;

helyette: 


typedef struct stack_t {
    int val;
    struct stack_t* next;
} stack_t;

Valamint a tabla[i][j] -k pval mezőit inicializálni kellene (NULL), és a push-nak valahogy így kinéznie:

void push (stack_t **stack, int e);

tabla[i][j].pval = NULL;
push (&tabla[i][j].pval, value);