Hogyan tudom meghatározni max. O (n^2) -es futási idővel egy sztring összes egyszeres zárójelezését?
Figyelt kérdés
pl. abc --> (a)(b)(c), (a)(bc), (abc), (ab)(c)
Előre is köszönöm!
2016. szept. 25. 00:30
1/17 A kérdező kommentje:
Nem a számuk szükséges, hanem a kiíratás, a rekurzió sajnos exponenciális...
2016. szept. 25. 00:30
2/17 2*Sü 
válasza:
válasza:Nézzük mi is történik. Van egy x karakterből álló stringed. Ezek között x-1 hely van, ahova be lehet szúrni egy )( párost. Kvázi olyan, mintha kettes számrendszerben számolnál. (Persze az elejére, végére is kell tenni egy egy zárójelet.)
000 → abcd → (abcd)
001 → abc)(d → (abc)(d)
010 → ab)(cd → (ab)(cd)
011 → ab)(c)(d → (ab)(c)(d)
100 → a)(bcd → (a)(bcd)
101 → a)(bc)(d → (a)(bc)(d)
110 → a)(b)(cd → (a)(b)(cd)
111 → a)(b)(c)(d → (a)(b)(c)(d)
Remélem ez az elv segít.
3/17 A kérdező kommentje:
Köszi szépen! Örök hálám! Én valahogy táblázatokkal próbálkoztam eddig. :)
2016. szept. 25. 00:56
4/17 anonim válasza:
válasza:Azt szögezzük le, hogy a zárójelezések száma egy n hosszú stringre 2^(n-1), tehát négyzetes futási idővel akarsz exponenciálisan növekvő zárójelezést megadni.
5/17 A kérdező kommentje:
Ezért szeretném táblázattal megoldani, hisz akkor rekurzió nélkül vissza tudnám vezetni a korábbiakra, és a táblázat dimenziója miatt csak négyzetes lenne.
2016. szept. 25. 09:18
6/17 A kérdező kommentje:
Bár egyelőre ezzel is meg vagyok akadva...
2016. szept. 25. 10:06
7/17 2*Sü válasza:
válasza:Mire kell egyébként a dolog? Mekkora stringet kell így feldolgozni? Valóban érdemes vesződni vele?
8/17 A kérdező kommentje:
Házi feladat. Nem tudni milyen méretűt, de szerintem nem nem lesz azért több ezres... Valamilyen viszonylag "egyszerű" megoldása csak van, amely nem exponenciális...
2016. szept. 25. 15:16
9/17 anonim válasza:
válasza:> Valamilyen viszonylag "egyszerű" megoldása csak van, amely nem exponenciális...
Ld. #2
10/17 anonim válasza:
válasza:A #2-es megoldása is exponenciális. Nem fogsz tudni meghatározni 2^N megoldást N^2 lépésből. Ha 2^N megoldása van a feladatnak akkor minimum 2^N lépés kell hogy meghatározd az összeset.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!