Koneessa on näyttöruutu, jossa on alussa luku 1. Lisäksi koneessa on kaksi nappia: vasen nappi lisää lukuun 3 ja oikea nappi kertoo luvun 2:lla.
Tavoitteesi on saada aikaan luku x nappeja painamalla. Mikä on pienin mahdollinen painallusten määrä?
Esimerkiksi kun x=17, paras ratkaisu on seuraava:
- Luku on alussa 1.
- Painat vasenta nappia, jolloin luvusta tulee 4.
- Painat vasenta nappia, jolloin luvusta tulee 7.
- Painat oikeaa nappia, jolloin luvusta tulee 14.
- Painat vasenta nappia, jolloin luvusta tulee 17.
Tässä tapauksessa pienin mahdollinen painallusten määrä on 4.
Toteuta tiedostoon machine.py funktio min_steps, joka etsii pienimmän painallusten määrän luvulle x. Jos ratkaisua ei ole olemassa, funktion tulee palauttaa -1.
Funktion tulee toimia tehokkaasti, kun x on välillä 1 \dots 1000.
def min_steps(x):
# TODO
if __name__ == "__main__":
print(min_steps(1)) # 0
print(min_steps(2)) # 1
print(min_steps(3)) # -1
print(min_steps(4)) # 1
print(min_steps(5)) # 2
print(min_steps(17)) # 4
print(min_steps(42)) # -1
print(min_steps(100)) # 7
print(min_steps(1000)) # 13