Milyen módszerrel kell megoldani?
Kapok egy P és F betűkből álló stringet amik piros és fekete golyókat jelentenek sorban egymás mellett. Vehetek ki (mintha törölném) golyókat a sorból de mindig csak a 2 legszélső golyó valamelyikét. Az a kérdés hogy hány golyót kell minimum elvennem ahhoz hogy egyenlő számú piros és fekete golyó maradjon a sorban. Például ha "PPFP" a sor akkor 2 a megoldás. Ha "PPP" akkor 3. Ha "PPFPFF" akkor 0.
Hogy döntsem el hogy melyik oldalról érdemes elvenni az aktuális golyót?
válasza:#28 vagyok, ha belegondolok, logikusnak tűnik hogy csak egyszer fordulhat elő, hogy "irányt váltunk", pl. a bal vágások, váltás, utána jobb vágások jönnek a végéig. Utána már nem váltunk. 0 vagy 1 irányváltás szükséges. Persze vannak határesetek, PPPPPP esetén mindegy hogy merről megyünk, PPPPFPP esetén több irányváltással is meg lehet oldani, de felesleges. Ezt beépítve abba a bruteforce keresőbe gyorsítható az algoritmus.
Amúgy lelkes amatőr vagyok, szóval szívesen veszem ha valaki kijavít, aki otthon van ezekben az algoritmizálási feladatokban.
válasza:32: A különbségre érdemes építeni.
Persze nem csak egyetlen megoldás létezik. Akár Backtrack, vagy mohó is lehet. BF adja a legtökéletesebb eredményt, de az jár a legnagyobb költséggel is.
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
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!