Hogy lenne érdemes megcsinálni ezt a feladatot?
Adott egy szám N.
1 <= N <= 10^9.
Két műveletet végezhetünk ezen a számon:
- szorzás 2-vel
- osztás 6-tal
Az a kérdés, hogy minimum hány lépésből csökkenthetjük 1-re a számot.
Ha nem lehetséges, akkor -1 legyen az eredmény.
Ezt valami backtracking megközelítéssel kéne megoldani?
Ha igen, akkor mikor kell megállni pl. a 2-vel való szorzásnál, hogy ne fussak túlcsordulásba de mégis eljussak az eredményhez?
válasza:Lehet még nekem van nagyon reggel és félreértem, de szerintem a feldat annyi, hogy:
N -t osztod hattal, amíg osztható maradék nélkül. Ha nem, akkor beszorzod kettővel, majd megint megpróbálod osztani.
Ezeket a lépéseket kell megszámolni.
Az pedig hogy kiszámolható-e, azt megtudod abból hogy az adott szám, előállítható-e a 6 prímtényezőiből.
Azt hiszem.
válasza:várj. eszembe jutott egy egyszerűbb megoldás.
bontsd fel prímtényezőkre.
ha 2-es és 3-as számokból előállítáható akkor kell tovább foglalkozni vele.
megszámolod hány 3-ast kaptál és hány 2-est.
pl:2916
2 2 3 3 3 3 3 3
(x db 2-es és y db 3-as)
akkor y*2-x lépés.
szerintem ez kevesebb lépés/feltétel vizsgálat
válasza:Ezt a feladatot, szvsz hibásan írtad ki.
Így, ezt értelmezve, ha n = 1 akkor 0 művelettel meg van oldva a feladat. Ha n > 1 akkor a műveletszám annak lineáris függvénye, hogy mennyire esik közel 10^9-hez.
válasza:Hármas, nem igazán értem, hogy mit mondasz.
Ha N == 1, akkor valóban 0 a megoldás.
Ha N > 1, akkor meg valóban növekedni fog a műveletszám N növekedésével. Ez mind igaz.
De az a kérdés, hogy adott N esetén konkrétan mennyi a minimális műveletszám, amivel N 1-re csökkenthető.
válasza:Nem tudom, hogy a törzstényezőkre bontás-e a feladat célja, de nem írtam el, így van kiírva a feladat ez copy+paste konkrétan:
1 <= N <= 10^9
De amúgy ha ez probléma, akkor ez nem csak egy egyszerű if vizsgálat?
if (N == 1) return 0 else { logika 1-től nagyobb N esetére }
Egyébként köszönöm az eddigi válaszokat, már el tudok indulni legalább valamerre.
válasza: válasza:"Az pedig hogy kiszámolható-e, azt megtudod abból hogy az adott szám, előállítható-e a 6 prímtényezőiből."
Ellenpélda: 9.
Lépések: 9->18->36->6->1
válasza:#9 Pontatlanul fogalmaztam.
a #2 válaszban kicsit jobban kifejtettem mire gondolok.
pontosítva: legalább 1db 3-asnak kell lennie a prímtényezők között és csak 2-es és 3-as lehet közöttük.
viszont a számítás ott is stimmel.
3*3 = 9
Tehát y*2-x (lásd #2) = 4 lépés
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!