Ez hogyan oldható meg?
Adott egy nxm méretű (0<n,m<100) „betű-mátrix” és egy n+m-1 hosszú karakterlánc, amelyeknek
elemei az angol ABC kisbetűi. Hány (1,1) indexű cellából (n,m) indexű cellába vezető út mentén (az (i,j)
cellából az (i+1,j) vagy (i,j+1) cellák valamelyikébe lehet tovább lépni, amennyiben ezek léteznek)
található meg az n+m-1 hosszú input karakterlánc?
Tehát ha jól gondolom akkor az első betűtől kezdve minden lehet lehetséges esetet ki kellene próbálni.
Addig eljutottam, hogy lépésenként összehasonlítsam a
a keresendő soron következő betüjével, de hogyan érhetem el, hogy minden lehetséges lépéskombinációt kipróbáljon, anélkül, hogy
ugyanazt megcsinálná kétszer.
Ha jól tudom a backtrackingnek az a lényege, hogy ha nem megfelelő a következő , akkor egyet visszalép.Például ha a jobbra lépés(j+1) nem jó,akkor lefelé lép(i+1) és ha az jó akkor arra lép tovább, de hogyan lehet hogy a következő kereséskor ne ugyanazon az útvonalon menjen végig és ne hagyjon ki egy lehetőséget sem?
Egyáltalán így kellene ezt megoldani?
A segítséget előre is köszönöm.
válasza:En egy rekurziv algoritmust irnek erre:
proc vizsgal(i, j):
_ ha rossz betu van az (i,j) cellaban, visszater hamissal
_ ha a sarkon vagyunk (i=n es j=m), visszater igazzal
_ ha van lefele hely es vizsgal(i+1, j) igaz, visszater igazzal
_ ha van jobbra hely es vizsgal(i, j+1) igaz, visszater igazzal
_ egyebkent hamissal ter vissza
Ha az utjara is kivancsi vagy, akkor az utolso n+m-1 visszateres (i,j) poziciojat tarold.
válasza:Le van írva kiscsillió helyen az algoritmus.
Google a barátod.
válasza:Mivel C++-ban kellett programozni, ami objektum orientált nyelv, ezért készítettem egy osztályt (class Matrix).
Ebben az oszályban van tárolva az mátrix (mx) és a string (s).
A fillMatrix() feltölti a mátrixot.
A fillString() feltölti a stringet.
A showMatrix() megjeleníti a mátrixot.
A showString() megjeleníti a stringet.
A mátrix és a string feltöltésénél van egy kis random variáció.
A randomSeed változóval tudod állítani, hogy minden futatásnál más-más mátrixot és stringet genereljon (randomSeed=time(NULL)),
vagy ha a randomSeed változónak egy konstans számot adol, akkor mindig ugyanazt a véletlen mátrixot és stringet fogja generálni (randomSeed=1504880612).
Ajánlom, hogy a "randomSeed=1504880612" parancsot inkább töröld ki.
A getCorrectPathCount() visszaadja, hogy mennyi helyes útvonalon található meg a string a mátrixban.
Ez egy rekurzív fügvénnyel van megvalósítva (countPaths()).
A countPaths() függvénynek 3 bemeneti (i,j,k) és 1 kimeneti (pathCount) paramétere van.
i - A mátrix egyik koordinátája
j - A mátrix másik koordinátája
k - A string indexe
pathCount - Visszaadja, hogy hány darab helyes útvonalon található meg a string a mátrixban a megadott mátrix koordinátától és a megadott string indextől számítva.
void Matrix::countPaths(const int i, const int j, const int k, int & pathCount) const
{
char c;
c = mx[i*m+j]; // Ilyen betű van a megadott matrix koordinátán.
if (s[k] == c) { // Ha a string betűje a megadott indexen egyezik a mátrix betűjével, akkor
if (k == (s.length()-1)) { // Ha a string indexe az utolsó betűre mutat, akkor
pathCount++; // Találtunk még egy helyes útvonalat.
} else {
if ((k+1) < s.length()) { // Ha van még olyan betű a stringben, amit még nem ellenőriztünk, akkor
if ((i+1) < n) { // Ha van még olyan betű a mátrixban, amit még nem ellenőriztünk, akkor
countPaths(i+1, j, k+1, pathCount); // Mennyi helyes útvonalon található meg a string a mátrixban a következő mátrix koordinátától és a következő string indextől számítva.
}
if ((j+1) < m) { // Ha van még olyan betű a mátrixban, amit még nem ellenőriztünk, akkor
countPaths(i, j+1, k+1, pathCount); // Mennyi helyes útvonalon található meg a string a mátrixban a következő mátrix koordinátától és a következő string indextől számítva.
}
}
}
}
}
A countPaths() egy rekurzív függvény.
Hogy hogyan kell rekurzív függvényt készíteni?
Rekurzív függvény készítésnél át kell gondolni, hogy milyen bemeneti és milyen kimeneti értékekre lesz szükségünk.
Valahol a függvényben lesz legalább egy parancs, ami meghívja ugyanazt a függvényt. De más paraméterekkel. Ugyhogy a paramétertervezés fontos.
Arra vigyázni kell, hogy a függvény ne hívja meg saját magát végtelenszer. Vagyis legyen benne egy olyan pont, amikor már nem fogja saját magát többször meghívni.
válasza:Hogy tárolna már egy mátrixot egy charban??
Egy dimenziós tömbben is lehet, csak csúnyább.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!