| Feladat: | Sz.4 | Korcsoport: 14-15 | Nehézségi fok: átlagos |
| Füzet: | 1982/április, 168. oldal |  PDF | MathML |
|
| Témakör(ök): | Programozási feladatok, Nehezebb feladat | ||
| Hivatkozás(ok): | Feladatok: 1981/november: Sz.4 | ||
|
A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Megoldás. A programban a sakktáblát oszlopok sorozatának tekintjük. Minden oszlopban egyetlen királynőt helyezünk el, az elsőt az első oszlopban. Ezután végigmegyünk az oszlopokon és az aktuális oszlopba próbáljuk az új királynőt elhelyezni. Ha sikerült az elhelyezés akkor a következő oszlopra lépünk, ha nem ‐ az előzőre. Ha van még hátra oszlop, akkor folytassuk az eljárást, ha nincs, akkor kész a megoldás. Ha az első oszlop elé lépünk, akkor nincsen (több) megoldás. Egy megtalált megoldás után keressük a többi megoldást is. (1 blokkdiagram).  Az algoritmus első lépése: Ha kilépnénk a táblából, akkor nem sikerült az elhelyezés. Ha az aktuális sor megfelelő hely, akkor sikerült elhelyezni, különben eggyel feljebb toljuk a királynőt . (3. blokkdiagram). Jelölés: ‐ az aktuális oszlopban levő királynő aktuális oszlopszáma.  Az algoritmus második lépése: Tegyük a királynőt az eggyel feljebb levő sorba. Ha jó helyre került, akkor lépjünk a következő oszlopba és tegyük a következő királynőt az első sor elé , különben lépjünk vissza az előző oszlopra . (2. blokkdiagram).  A megoldó ABC 80 BASIC program lényeges része:  100 I=1 : V(1)=0 110 IF I<1 THEN 500 : REM VÉGE 120 IF I<=N THEN 200 : REM LÉTEZŐ OSZLOP 130 REM AZ EREDMÉNY KIIRÁSA 190 I=I‐1 : REM AZ UTOLSÓ KIRÁLYNŐ HELYÉT VÁLTOZTATJUK 200 REM KIRÁLYNŐELHELYEZÉS 210 V(I)=V(I)+1 220 IF V(I)> N THEN 400 : REM NEM SIKERÜLT ELHELYEZNI 230 REM JÓ HELYEN VAN-E 240 K=1 250 IF K=I THEN 350 : REM JÓ HELYEN VAN 260 IF V(I)=V(K) OR ABS(V(I)‐V(K))=I‐K THEN 300 : REM ÜTI EGY ELŐZŐ 270 K=K+1 280 GOTO 250 300 REM HA NEM JÓ HELYRE TETTÜK 310 V(I)=V(I)+1 320 GOTO 220 : REM AZ ÚJ HELY VIZSGÁLATA 350 REM JÓ HELYET TALÁLTUNK 360 I=I+1 370 IF I<=N THEN V(I)=0 380 GOTO 110 : REM ÚJ KIRÁLYNŐ ELHELYEZÉSE 400 REM AZ AKT. OSZLOPBA NEM SIKERÜLT ELHELYEZNI 410 I=I‐1 420 GOTO 110 : REM UJ KIRÁLYNŐ ELHELYEZÉSE 500 REM BEFEJEZÉS A megoldások szimmetria-tulajdonságai miatt (felező egyenesre, átlóra való tükrözés, 90 fokos elforgatás) gyorsabb megoldást is lehet készíteni. Zsakó László |