C, hogyan kell megtalálni a nyereg pont a mátrixban
C ++: hogyan találjuk meg a nyereg pont a mátrixban
A koncepció egy nyereg pont mátrix széles körben használják a játékelmélet és valahol máshol. A nyereg pont nevezzük mátrixelem, amely egyidejűleg a minimális eleme a megfelelő sorban a mátrix és a maximális elem a megfelelő oszlop a mátrixba, vagy, hogy ugyanazt az elemet a mátrix, amely egyidejűleg a maximális elem a megfelelő oszlop a mátrix és a minimális elem a sorban.
Megjegyezzük, hogy ha a mátrix számos nyereg pontot, minden érték egyenlő. Ha az összes számot a mátrix különböző, a nyereg pont és nem több, mint egy. Ha az összes telefonszám a mátrixban azonosak, száma nyereg pontok számával megegyező elemek.
Első lista „teljes search-agy” megközelítés.
A funkció int nyereg (int n, int m, int ** egy, int, int JS) ellenőrzi, hogy egy cella [van] [js] mátrix n dimenziós * m annak nyeregpont. Return 1 (igen) vagy 0 (nem).
A függvény int * saddle_points (int n, int m, int ** a, int k) megállapítja a nyereg pont a mátrix. Akkor az első funkciót. Számát adja nyereg pont paraméter-link k. és a fő visszatérési értéke - a vektor mérete 2 * k. tartalmazó sor és oszlop koordinátái minden nyereg pontot a mátrix. Például, ha a mátrix 2 nyereg pont pozíciókban található (0,1) és (3,2). vektor áll számok (0,1,3,2) (számozott nulla).
A fő érdeke, mint módszert átírni a vektor (n * m) elemeinek egy sorban mátrix dimenzió n * m:
Ellenőrizze dimenziója a mátrix 8 * 2 állítólag a sorrendben egy 4 * 4 - mint mi,
A kód lista mutatja működnie kell bármilyen típusú casting beállításokat.
Ahhoz, hogy megtalálja a nyereg pont a mátrixok nagyméretű nem szükséges vizsgálni az egyes elemek külön-külön.
Tekintsük egy „kulturális” algoritmust megállapítás minden nyereg pont a mátrix. Megmutatja munkája példaként.
Meg akarja találni annak minden nyereg pont.
Összegyűjti a legalacsonyabb értékeket az összes sort, megkapjuk a vektor A = (- 4, 2, 2, -3).
Összegyűjti a legmagasabb értékeket az összes oszlopot, megkapjuk a B vektor = (7, 2, 7, 2).
Ellenőrzés: legfeljebb az első szettet nem lehet több, mint a minimum a második.
Ha a legnagyobb az első készlet kevesebb, mint a minimális második, a nyereg nem pont.
Ha a maximális első beállításakor egyenlő a minimum a második (ebben az esetben a 2-es szám), azt találtuk, az s érték a nyereg pont.
Most nézzük meg, mi pozíciók az a és b vektorok azok az értékek, S.
Amikor számozás az egységet. az első készlet összesen 2 és 3, míg a második - 2 és 4-helyzetben.
A terméket ezen halmazok, ahol az összes nyereg pont. Esetünkben = <, , ,> - koordináták mátrix nyereg pont, ismét, amikor számozott egyet.
Az egyik lehetséges megvalósítási algoritmus (nem ellenőrzött)