Edge Case – megoldás
2013.01.27. 19:55
Az eredeti feladat itt.
Megoldás
Ezt a feladatot bemelegítésnek szántam, ez egy relatíve egyszerű dinamikus programozási példa. Egy trükk kell hozzá, de az is lehet, hogy ez nem trükk, hanem rutin. Mindenesetre érdemes észrevenni, hogy a feladat szimmetrikus, a bemenet is csak egy szám. Jó lenne valahogy visszavezetni kisebb esetekre. Ez ugyan nem fog menni, de valami egészen hasonló igen.
De kezdjük az elején. Számozzuk meg a csúcsokat körbe 1-től n-ig. Hogyan próbálnánk visszavezetni kisebb esetekre? Dinamikus programozásnál az elv az, hogy alkalmazunk valamiféle megkötést (minden szóba jövő módon), és az így kapott, egyszerűbb feladatokat megoldjuk, illetve belőlük összerakjuk az eredeti feladat megoldását. Jelen esetben nézzük meg, hogy tartalmazza-e a párosításunk az 1n élt. Azok a párosítások, amelyek nem tartalmazzák, megfelelnek az n csúcsból álló út párosításainak (egyszerűen kitörölhetjük a gráfból az 1n élt. Azok a párosítások viszont, amelyek tartalmazzák 1n-t, az n-2 csúcsból álló út párosításainak felelnek meg (hozzávéve 1n-t), ugyanis ezt kapjuk, ha az 1 és n csúcsokat töröljük ki.
Ha tehát Fi-vel jelöljük az i csúcsból álló út párosításainak számát, akkor a válasz Fn+Fn-2. És bár valóban nem körökre vezettük vissza a feladatot, hanem utakra, az utakat már ugyanilyen módszerrel kisebb utakból ki tudjuk számolni: Ha az 12 él nincs benne a párosításban, egy n-1 csúcsú út párosításait keressük, ha benne van, akkor egy n-2 csúcsúét. Egyébként ez – meg variánsai – egy viszonylag közismert feladat, mármint az, hogy a párosítások száma pont az n-edik Fibonacci szám. A bizonyítás meg amit az előbb leírtam.
De ha ezt nem vesszük észre, akkor is O(n) időben kiszámolható Fn és Fn-2.
Ajánlott bejegyzések:
A bejegyzés trackback címe:
Kommentek:
A hozzászólások a vonatkozó jogszabályok értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a Felhasználási feltételekben és az adatvédelmi tájékoztatóban.