Vai al contenuto principale
← OlimpiApp Olimpico

Informatica · Algoritmi

Escursione delle moltiplicazioni tra 130 e 260

Il seguente pseudocodice calcola $a^{b}$ con l'esponenziazione veloce (square-and-multiply):

function power(a, b):
    result = 1
    while b > 0:
        if b is odd:
            result = result * a
        a = a * a
        b = b // 2
    return result

Considera ogni istruzione result = result * a oppure a = a * a effettivamente eseguita come una moltiplicazione, e indica con $m(e)$ il numero totale di moltiplicazioni eseguite quando $b=e$.

Al variare di $e$ con $130 \le e \le 260$, qual è la differenza tra il valore massimo e il valore minimo di $m(e)$?

La tua risposta

Vanno bene sia 3,14 sia 3.14.