Melyik az a legkisebb hatvány, amelyiket nem lehet legfeljebb 8 szorzással előállítani?
Az előzőleg kiszámolt hatványokat felhasználva. Pl.:
1. a^2 = a*a
2. a^3 = a^2*a vagy a^4 = a^2*a^2
...
válasza:Lehet én értem félre a feladatot, de ha az előző szorzatot fel lehet használni, akkor maximum 2 szorzattal mindent meg lehet csinálni.
Pl. a^123=a^122*a
Vagy van valami korlát?
Az a^122 nem egy előzőleg már kiszámolt hatvány.
Csak az 1. hatványt ismerjük, "a"-t, és max. 8 szorzásod van, az 1. mindenképpen: a^2 = a*a
válasza:Nem tudom, hányadikos vagy, mennyire kell általánosan csinálni. Fel lehet írni sorban a hatványokat, nem kell túl sokáig menni. Vagy az általános megoldás ez:
a^2 = a · a : 1 szorzás
a^4 = a^2 · a^2 : 2 szorzás
a^8 = a^4 · a^4 : 3 szorzás
stb, általánosan:
a^(2^k) = k szorzás
a^3 = a^2 · a : 2 szorzás
a^5 = a^4 · a : 3 szorzás
stb.
a^(2^k+1) : k+1 szorzás; írhatjuk úgy is, hogy a^(2^k+2^0) : k+0+(2-1) szorzás
a^6 = a^4 · a^2 : 4 szorzás
stb.
a^(2^k+2^m) : k+m+1 szorzás; k+m+(2-1) szorzás
a^7 = a^4 · a^2 · a : 2+1+1+1 = 5 szorzás
a^(2^k+2^m+1) : k+m+1+1 szorzás; máshogy írva: a^(2^k+2^m+2^0) : k+m+0+(3-1) szorzás
a^(2^k+2^m+2^n) : k+m+n+(3-1) szorzás
Vagyis a^b-hez annyi szorzás kell, amennyi b 2-es számrendszerbeli felírásában a helyiértékek kitevőinek összege, plusz az 1-es bitek számánál eggyel kisebb szám.
3 bites számig még nem érjük el a 8-at: Abból a legnagyobb az 111, vagyis 2^2+2^1+2^0, amihez 2+1+0+(3-1) = 5 szorzás kell.
4 bitesnél a legnagyobb az 1111 kettes számrendszerbeli szám, vagyis a 15 = 2^3+2^2+2^1+2^0 esetén ez 3+2+1+0+(4-1) = 9, már több 8-nál.
14 = 1110: 3+2+1+(3-1) = 8
Az összes többi 4 bites szám, amiben nem a legkisebb helyiértékű bit a 0-ás, 8-nál kevesebb szorzásra jön ki.
Ezért a megoldás a^15
a^15 : 5 szorzással előállítható
1. a^2 = a*a
2. a^3 = a^2*a
3. a^5 = a^3*a^2
4. a^10 = a^5*a^5
5. a^15 = a^5*a^10
válasza:Miért nem folytattad?
6. a^25=a^15*a^10
7. a^40=a^25*a^15
8. a^65=a^40*a^25
a 66. hatványhoz már kell még egy szorzás is.
válasza:257. ???
Már a 127. sem, még 9 szorzással sem. Szerintem.
De a 101.-et sem tudtam 8-cal felírni, tehát max 101, de inkább kisebb.
Egy átgondolt, jó válasz szeretnék, (gyenge) tippek helyett. Köszi.
válasza: válasza:Feltettem a kódot (Python 2.7). Sajnos nem engedi a linket bemásolni, úgyhogy kopiznod kell:
pastebin pont com/71x7DKu1
válasza:Háromtól tíz lépésig: 7, 11, 19, 29, 47, 71, 127, 191.
Le ne futtasd 10 lépésre! Megfőzi a gépedet. Buta algoritmus, erőből számol és azt se okosan. Majd gondolkozom rajta, hogy lehetne szebben. Nem igazán látok a számokban mintát amúgy, binárisan felírva se nagyon.
Fogalmam sincs, hogy számolnám ki mondjuk 15 lépésre, és van egy olyan gyanúm, hogy hasonló lehet ez a probléma a prímszámok kereséséhez: elsősorban izomból megy.
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!