Eccoci.

In cammino verso l'unità

Dato un numero \(n\) qualunque, sottraetegli 1 se è dispari, mentre dividetelo per 2 se è pari. Quanti passi sono necessari per arrivare a 1?

Per capire meglio il problema prendete come riferimento gli esempietti che seguono.

function show_steps(n::Integer)
    steps = 0
    while n>1
        if n%2 == 0
           n = n÷2
        else
           n = n-1
        end
        steps += 1
        print("→ $n ")
    end
    print("(steps=$steps)")
end

2 → 1 (steps=1)
3 → 2 → 1 (steps=2)
4 → 2 → 1 (steps=2)
5 → 4 → 2 → 1 (steps=3)
10 → 5 → 4 → 2 → 1 (steps=4)
20 → 10 → 5 → 4 → 2 → 1 (steps=5)
30 → 15 → 14 → 7 → 6 → 3 → 2 → 1 (steps=7)

Simulare tutti questi passaggi (sottrarre 1 o dividere per 2) può diventare dispendioso per numeri molto alti: vorremo quindi trovare un modo che, dato un numero \(n\), ci dia una risposta più immediata riguardo al numero di passi necessari per arrivare a 1. Esiste quindi una "formula" generale, in funzione di \(n\), che calcoli direttamente la soluzione?

Soluzione