C ++: cum să găsească toate punctele șaua în matricea
Conceptul de matrice punct de șa este utilizat pe scară largă în teoria jocurilor și în altă parte. Un punct de șa este numit un element de matrice, care în același timp este elementul minim în șirul corespunzător al matricei și elementul maxim în coloana corespunzătoare a matricei, sau că același element al matricei, care în același timp este elementul maxim în coloana corespunzătoare a matricei și elementul minim în rândul.
Rețineți că, dacă matricea are un număr de puncte de șa, toate valorile sunt egale. Dacă toate numerele din matrice sunt diferite, punctul de șa și nu mai mult de unul. Dacă toate numerele din matrice sunt identice, numărul punctelor de șa egal cu numărul de elemente.
Prima listare a unei abordări „totale de căutare-brainer“.
Șaua Funcția int (int n, int m, int ** a, int este, int js) verifică dacă o celulă este [este] [js] o matrice de dimensiune n * m punctul de șa. Întoarcere 1 (da) sau 0 (nu).
Functia int * saddle_points (int n, int m, int ** a, int k) găsește toate punctele șa ale matricei. Acesta utilizează prima funcție. Returnează numărul de puncte de șa cu parametrul-link k. iar valoarea principală de retur - dimensiunea vectorului de 2 * k. cuprinzând rând și coloană coordonatele tuturor punctelor șa ale matricei. De exemplu, dacă matricea 2 puncte de șa situate la pozițiile (0,1) și (3,2). vector va consta din numere (0,1,3,2) (numerotate de la zero).
Interesul principal ca metodă de a rescrie vectorul (n m *) de elemente într-o matrice rând de dimensiune n * m:
Verificați dimensiunea matricei 8 * 2 se presupune a fi de ordinul a 4 * 4 - ca și noi,
Codul este prezentat în listă ar trebui să funcționeze, indiferent de setările de turnare de tip.
Pentru a găsi toate punctele șaua în matricele de dimensiuni mari, nu este necesar să se ia în considerare fiecare element separat.
Luați în considerare un algoritm mai „cultural“ pentru a găsi toate punctele șa ale matricei. Va arăta activitatea sa ca un exemplu.
Doriți să găsiți toate punctele sale de șa.
Va colecta la cele mai mici valori ale tuturor rândurilor, obținem vectorul A = (- 4, 2, 2, -3).
Va colecta cele mai mari valori în toate coloanele, obținem un vector B = (7, 2, 7, 2).
Verificarea: maxim al primului set nu poate fi niciodată mai mult decât minimul de-al doilea.
În cazul în care maximul a primului set este mai mică decât minimul de-al doilea, șa niciun punct.
Dacă valoarea maximă este mai întâi egală cu minimul celei de a doua (în acest caz, numărul 2), am găsit valoarea S a punctului de șa.
Acum, uita-te la ce poziții în vectorii A și B sunt valorile S.
Când numerotarea cu unitatea. în primul set este poziția 2 și 3, în timp ce al doilea - 2 și 4 poziții.
Pe produsul acestor seturi este în cazul în care toate punctele de șa. În cazul nostru = <, , ,> - coordonează în matricea punctelor de șa, din nou, atunci când numerotate de la unu.
Una dintre posibilele implementări ale algoritmului (nu a verificat)