Căutați elementul maxim și minim din listă
Definiția lungimii
Numărul de elemente din listă poate fi calculat folosind predicatele recursive count_list1 și count_list2. count_list1 predicatului ține evidența numărului de elemente din lista de pe cursul direct de recurență, din cap listă, în care primul parametru este un contor de curent de tip octet, iar al doilea - este necesar să se întoarcă rezultatul la ieșirea recurență. count_list2 predicatului ține evidența numărului de elemente din lista de pe cursa de retur recursivitatii, începând cu ultimul element, în care tipul de parametru este contorul de curent octet, iar rezultatul simultan. Două variante de rezolvare a problemei sunt date în Exemplul 39.
Exemplul 39: Determinarea lungimii unei liste.
numerele_list1 ([_ | T], N, M): - N1 = N + 1, count_list1 (T, N1, M).
count_list1 ([_ | T], N): - count_list1 (T, N1), N = N1 + 1.
Găsiți elementul maxim sau minim din listă utilizând predicatele recursive max_list și min_list. Predicatul max_list caută elementul maxim din listă în calea recursivă înainte, pornind de la capul listei, primul parametru al întregului tip fiind maximul curent, iar cel de-al doilea este necesar pentru returnarea rezultatului la ieșirea din recurs. Predicatul min_list caută elementul minim din listă pe cursul invers al recursiunii, începând cu ultimul element, cu parametrul de tip întreg fiind minimul curent și rezultatul în același timp. Două variante de rezolvare a problemei sunt date în Exemplul 40.
Exemplul 40: Căutați elementul minim de maxim m din listă.
max_list (listă, număr întreg, număr întreg)
max_list ([H | T], N, M): - H> N, max_list (T, H, M).
max_list ([H | T], N, M): - H<=N, max_list(T,N,M).
min_list ([H | T], M): - min_list (T, M1), H> M1, M = H.
min_list ([H | T], M): - min_list (T, M1), H<=M1, M=M1.
Sortarea este o reordonare a elementelor din listă într-un mod specific. Scopul de sortare este de a simplifica accesul la elementele necesare. Pentru sortarea listelor sunt de obicei utilizate trei metode:
De asemenea, puteți utiliza combinații ale acestor metode.
Prima metodă de sortare este de a rearanja elementele listei până când este comandată. A doua metodă este implementată prin introducerea repetată a elementelor în listă până când este comandată. Cea de-a treia metodă implică eșantionarea și mutarea mai multor elemente de listă.
A doua metodă, metoda de inserare, este deosebit de convenabilă pentru implementarea pe Prolog.
Exemplul 39: Liste de sortare după metoda de permutare (balon).
Exemplul 40: Sortarea listelor după inserare.
insert_sort (listă, listă)
inserați (întreg, listă, listă)
asc_order (intreg, integer)
insert_sort ([H1 | T1], L2): - insert_sort (T1, T2);
inserați (X, [H1 | T1], [H1 | T2]): - asc_order (X, H1).
introduceți (X, L1, [X | L1]).
asc (X, Y): - X> Y.
insert_sort ([4, 7, 3, 9], L).
Pentru a satisface prima regulă, ambele liste trebuie să fie goale. Pentru a realiza această stare, conform celei de-a doua reguli, apare un apel recursiv la predicatul insert_sort, valorile lui H1 devenind în mod constant toate elementele din lista sursă, care apoi sunt plasate pe stivă. Ca rezultat, lista de surse devine goală, iar prin prima regulă lista de ieșire devine și goală.
După finalizarea cu succes a primei reguli, Prolog încearcă să execute al doilea predicat insert, al cărui apel este conținut în corpul celei de-a doua reguli. Variabila H1 atribuie mai întâi primei valori preluate din stiva la 9, iar predicatul ia forma insert (9, [], [9]).
Întrucât a doua regulă este acum îndeplinită, ea returnează un pas al recursiunii în predicatul insert_sort. Din stivă, se extrage 3 și predicatul asc_order este numit de a treia regulă, adică se face o încercare de a satisface regula a cincea asc_order (3, 9): - 3> 9. Deoarece această regulă eșuează, a treia regulă nu reușește, prin urmare, regula a patra este îndeplinită, iar 3 este introdusă în lista de ieșire din stânga lui 9. inserați (3, [9], [3, 9]).
Apoi, reveniți la predicatul insert_sort. care are următoarea formă: insert_sort ([3, 9], [3, 9]).
La următoarea etapă se extrage recursiunea din stiva 7 și a treia regulă apelează predicatul asc_order în forma asc_order (7, 3): - 7> 3. Din moment ce această regulă se termină cu succes, elementul 3 este aruncat în teanc și inserția se numește din nou recursiv, dar deja cu coada listei - [9]: inserați (7, [9], _). Din moment ce regula asc_order (7, 9): - 7> 9 nu reușește, se execută a patra regulă, se întoarce la etapele anterioare de recursiune, apoi se introduce insert_sort.
Ca rezultat, 7 este plasat în lista de ieșire dintre elementele 3 și 9. introduceți (7, [3, 9], [3, 7, 9]).
Când reveniți încă un pas al recursiunii din stivă, 4 este extras, iar prin a treia regulă, predicatul asc_order este numit în forma asc_order (4, 3): - 4> 3. Deoarece această regulă se termină cu succes, elementul 3 este eliminat în teanc și inserția se numește din nou recursiv, dar deja cu coada listei - [7, 9]: inserați (4, [7, 9], _). Pe măsură ce regula asc_order (4, 7): - 4> 7 eșuează, se execută a patra regulă, se întoarce la etapele recursive anterioare, apoi se introduce_sort.
Ca rezultat, 4 este plasat în lista de ieșire între elementele 3 și 7:
inserați (4, [3, 7, 9], [3, 4, 7, 9]).
insert_sort [4, 7, 3, 9], [3, 4, 7, 9]).
Articole similare
Trimiteți-le prietenilor: