Nyolc Queens - oldja meg a problémát a nyolc dáma együtt!
Feltételek
A fórum tilos:
Szabálysértőket fogják szigorúan bünteti adminisztrátor vagy egy moderátor, és lesznek teljesen férhetnek hozzá a fórumon.
Ezzel a fórum segítségével:
Ebben a cikkben, beszéljünk a híres logikai feladvány úgynevezett „nyolc dáma”. A probléma lényege abban rejlik, hogy meg kell tudni helyezni a sakktábla (8 × 8) nyolc dáma, hogy azok nem egymás alatt harc (ne feledjük, hogy a királynő (Queen) egy előre átlósan). Azt fogja mondani, hogy van több lehetőség az elhelyezés, hanem, hogy megtaláljuk azokat manuálisan nem mindig könnyű, különösen nehéz fel az utolsó királynője. Az egyik megvalósítási mód beállítások királynők nézd az alábbi 1. ábra
Annak érdekében, hogy megoldja a problémát a nyolc dáma problémája, akkor írj egy programot, a programozási nyelv C ++, amely meghatározza a királynők. Azt javaslom, hogy kövesse az ilyen taktika:
1. sakktábla képviseletében a kétdimenziós tömb mérete 8 × 8.
2. Minden sejt tömböt adjon meg egy számot, amely megmondja, hogy hány a sejteket a királynő lehet verni a többi sejt. Lásd a 2. ábrát
Mint látható, ha tesz a királynő helyzetéről szóló x = 2, y = 1, akkor a harc lesz 23 sejtekben. Ezt az eljárást meg kell tenni minden téren a sakktábla (kétdimenziós tömb). Ennek eredményeként, megkapjuk éppen egy ilyen képet, amint azt az alábbiakban a 3. ábra
3. Ha a prioritásokat az, jelölje ki a cellát a minimális prioritás (az egyik, amely kevesebb, mint dobogó többi sejt board), és tedd rá a királyné. Úgy gondolom, hogy minden világos. mert ha tesz királynők azokat a sejteket, amelyekkel verni más sejtek helyezés előtt nyolc királynők nem érjük el. Mi továbbra is beszélni. Ha a minimális számú kiemelt sejteket találtak (mint az elején elrendezés lesz így), majd válassza ki a appropriate'll véletlenszerűen. Mivel logikailag indokolt megszervezni? Ehhez először is meg kell találni a minimális prioritás (például 21 -, hogy ez a legkisebb az első iteráció - lásd a 3. ábrán), majd számolja meg a kiemelt sejteket (ebben az esetben a 21 ugyanezek a sejtek már 28), a továbbiakban: generál egy véletlen számot az 1-től a számú, azonos sejtek (28), és, a kapott a generáció száma, tegye a queen, hogy a kívánt helyre. A ketrec, ahol fel a királyné, valahogy meg kell jelölni, például hozzárendeli értéke 100. köszönhetően abszolút semmilyen értéket, kivéve, hogy úgy van megválasztva, hogy nem meghatározott minimális prioritás.
4. A beállítás után a királyné el kell távolítani őket verték sejtek jelölése őket bármilyen számot. Tegyük fel, hogy fogom jelölni ezeket a sejteket a kényelem száma 99.
Egy kis magyarázat. Amikor az alapvető algoritmus elrendezése királynők fog működni, és mi marad a táblán (kétdimenziós tömb, amely emulálja a sakktábla) egy sejtet a számok 100 (ez a királynő), és 99 - Sérült sejtek, mi származik az eredményt a képernyőre, azzal a feltétellel, hogy ha találkozunk szám 100 -, hogy felhívják a királynő (vagy konzol - a hópehely, grill, stb), egyébként csak, hogy a cella üres (vagy konzol világosság, akkor jelölni azokat kötőjellel, pontok, stb.)
5. Ezután minden ismétlődik lépésben 2-4, amíg az elválás minden dáma, ami nyolc lehet. Aztán ott van egy másik pontja: az első kísérlet, még az úgynevezett „intelligens” megközelítés a feladatok végrehajtásának, a fenti algoritmus nem tudja rendezni mind a nyolc dáma. De van egy kiút ebből a helyzetből. Elhelyezése után ellenőrizni fogjuk: lesz-e tenni a királynők. Ha nem, ismételje meg a műveletet.
A következő negyedik alak hozok hatályba a fenti algoritmusnak szemléltetés céljából. Képes különböző változatai szabályokat, de ehhez meg kell indítani a weboldal ( „Frissítés” gomb a böngésző vagy F5), és akkor az eredmény meg fog változni. Sajnos, web-technológia Ajax, nem tudom, mi mást, így kap egy új képet újra be kell töltenie az oldalt.
Ez a fajta program (eddig csak idézni a fő rész - main () függvény), amely végrehajtja az algoritmus
Mint látható, ez rájött, hogy már említettük
1) állapítsa egy kétdimenziós tömböt board. dimenziója 8 x 8-sejtek - ez lesz a sakktáblán. Is, akkor kell a változókat tárolja a pont koordinátái (x, y), és a mutatók nekik (ptrX és ptrY). Inicializálása egy sor nullák, mi szolgálja a funkciót resetBoard ().
2) Matrix bejelentett, inicializálja. Most belenézel a hurok. és hogy mi lesz, hogy hajtsa végre a beállítás a nyolc dáma. Ahogy azt már a fenti 2. pontban, akkor be kell állítani a prioritást minden mátrixpont. Ez teszi a funkció updateBoard ().
4) A beállítás után a királyné jelölni azokat az elhalt sejteket. Vajon ez deleteCell () függvényt.
Ez a folyamat ismétlődik nyolcszor pontosan meghatározott feltételek a for ciklus. Ha, mint írtam fent, nem fog működni az első kísérlet, hogy helyezze nyolc dáma, a végeredmény folyamatot kitörölni resetBoard () és elhelyezését a ciklus kezdődik elölről. Tájékoztatni minket arról, hogy mind a nyolc dáma kerülnek-e vagy sem, egy olyan funkció checkQueens (). false. ha ez nem sikerül elhelyezni, és az igazság. Ha az illesztés sikeres volt.
Itt elvileg, és minden, amit akartam mondani ebben algoritmus. Teljes a program végrehajtásának idézik alább.
A program eredményeként
Ui Szintén az oldalon lehet találni egy másik alkalmazása az algoritmus „Nyolc Queens”, amelyet a programozó Alexey és írt a fórum. amelyre sok köszönet neki.