Un exemplu de realizare oarecum diferită a circuitului de sortare abstract cu întoarcere poate fi aplicată la alte probleme cunoscute de dipozitive dimensiune checkerboard cal n „n. Presupunem că rândurile și coloanele sunt numerotate în mod corespunzător de bord de sus în jos și de la stânga la dreapta numerele de la 0 la n - 1, și se mută de cai în jurul valorii de bord în conformitate cu normele obișnuite de șah. Pentru a găsi o placă dintr-un anumit câmp este să obțineți o secvență de poziții pentru deplasarea unui cavaler astfel încât fiecare câmp să fie vizitat exact de o dată. Pentru comanda 8 '8 această problemă a fost ridicată pentru prima oară de L. Euler.
4. Închideți tabla cu un cal. Pe o tablă de șah cu dimensiunea n 'n în poziție (x, y) există un cal (vezi figura 2). Creați o funcție de program recursivă, care se găsește prin metoda forței brute, cu returnarea bypassing board-ul, dacă există. Dacă nu există soluție, ar trebui să se emită un mesaj corespunzător.
Soluția. Figura 2 prezintă un fragment al plăcii. Calul K se află în poziție (x, y). Celulele cu numere în jurul K - este un domeniu căruia un cavaler poate trece de la (x, y) (0 £ x, y £ n - 1) într-o singură tură. Denumim setul acestor câmpuri prin M (x, y). Pentru un câmp fix (x, y), mulțimea M (x, y) poate conține de la două la opt elemente. Să încercăm să sortăm aceste seturi. Luați în considerare matricea auxiliară de creșteri:
Pentru câmpul (x, y) construim o secvență de câmpuri
și alegeți de la ei pe cei pentru care
Fig. 2. Schema de ordonare a setului de mișcări posibile ale calului
Aceste câmpuri compun setul M (x, y). Fiecare element (a, b) Î M (x, y) atribuie coloana număr k D. elemente care, în conformitate cu punctul (2) - (3) definesc axele pentru deplasări incrementale ale calului (x, y), în (a, b). Astfel, mișcările posibile ale cavalerului de la (x, y) sunt ordonate în funcție de numerele pe care le-au obținut. În figura 2, aceste numere sunt prezentate în celulele corespunzătoare. Rețineți că alte variante ale lui D. și toate dintre ele 8! = 40320, oferă alte moduri de a comanda M (x, y).
Prin rezolvarea sarcinii folosind schema generală 3 backtracking, am genera in mod constant un vector de lungime n 2. Este convenabil să se construiască nu un vector, și matricea de dimensiune n „n. menționând în celula numărul ei cavaler se mută de la un an și până la n 2. Puteți face acest lucru cu ajutorul principale () și Ktour) (funcții.
Parametrii principalei funcții a capului (n, x, y) sunt dimensiunea plăcii (n) și punctul de pornire (x, y) cu care se deplasează cavalerul. În principiu () este inițiată de zerouri ale matricei de bord H a mărimei n 'n și se efectuează prima mișcare. Apoi, funcția recursivă Ktour () este invocată, iar după calcul, matricea H este afișată cu turul complet al calului sau cu mesajul despre absența soluțiilor.
Parametrii recursive funcția Ktour (n, x, y, H, boo, j) - este mărimea plăcii (n), punctul (x, y), cu care cursul normal al bord cal (H), adâncimea apelurilor recursive (j) și variabila auxiliară boo. Funcția Ktour () returnează matricea curentă H și valoarea boo. care este egală cu zero sau una, în funcție de faptul că mișcarea cavalerului a avut succes sau nu în circulația recursivă actuală.
În fiecare apel recursiv de adâncime j, se face o încercare de a plasa calul în următorul câmp j. Poziția de la care calul nu poate fi mișcat mai departe se numește sfârșit de capăt. Un blocaj duce la finalizarea apelului recursiv curent, adică revenirea la câmpul anterior și continuarea lucrului cu acesta. Alte cazuri de încheiere a apelurilor recursive nu există. Prin urmare, baza de recursiune, ca în Problema 1, trebuie să luăm în considerare totalitatea tuturor scopurilor. Nu sunt cunoscute elemente ale bazei de date înaintea calculelor. Dacă următorul recursiv cal promovare apel reușește (Boo = 1), apoi se trece la următorul apel recursiv. Dacă este posibil, pentru a promova calul ultima celulă neocupată din N. transportate revine succesive la primul nivel recursive (j = 0), și se întoarce soluția (H). În cazul în care a efectuat o revenire la primul nivel atunci când o placă martor recursiv și la acest nivel testat deja toate mișcările valide, atunci mesajul cu privire la absența unor soluții.
Notă. Încercările de a rezolva problema 2 pentru n ³ 8 cu ajutorul programelor main () și Ktour (), implementate în limba de programare Mathcad. se confruntă cu dificultăți din cauza lipsei de memorie sau a duratei calculelor. Nu salvează implementarea acestor programe în niciun limbaj de programare de tip compilator. Accelerarea minimă a calculelor poate oferi o tranziție la versiunea non-recursivă a funcției Ktour (). Prin urmare, pentru rezolvarea problemei 2, chiar și pentru o tablă de șah convențională (n = 8), sunt necesare alte abordări. Unul dintre acestea va fi discutat în secțiunea următoare.
Articole similare
Trimiteți-le prietenilor: