Potenza col metodo del contadino russo

Il "metodo del contadino russo" è un procedimento efficiente per il calcolo della potenza a^b (a elevato alla potenza di b).

NOTA: nel seguito, per chiarezza i numeri verranno scritti con notazione anglosassone, ovvero usando il punto per separare i decimali e la virgola per separare le migliaia (es. 1,564,373.03).

Il metodo consiste nell'avere una variabile risultato inizializzata pari a 1. Dopodichè, si realizza un ciclo nel quale

  • la variabile risultato viene moltiplicata per a solo se b è dispari.
  • successivamente, si aggiorna il valore di a calcolandone il quadrato, mentre b viene dimezzato, arrotondando per difetto

Il ciclo termina quando b si annulla.

Esempio

Si supponga di voler calcolare la potenza 3^12 (3 elevato a 12). I passi dell'algoritmo determinerebbero la seguente sequenza di valori (risultato è abbreviato in r, mentre le "freccette" servono a indicare la valutazione delle espressioni):

r     <- 1
a     <- 3
b     <- 12

r non viene modificato perché b è pari
a = a * a    <- 3 * 3     <- 9
b = b / 2    <- 12 / 2    <- 6

r non viene modificato perché b è ancora pari
a = a * a    <- 9 * 9    <- 81
b = b / 2    <- 6 / 2    <- 3

r = r * a    <- 1 * 81     <- 81 (in questo caso b è dispari)
a = a * a    <- 81 * 81    <- 6,561
b = b / 2    <- 3 / 2      <- 1

r = r * a    <- 81 * 6,561       <- 531,441 (in questo caso b è dispari)
a = a * a    <- 6,561 * 6,561    <- 43,046,721
b = b / 2    <- 1 / 2            <- 0

A questo punto il procedimento termina, in quanto b si annulla, e il risultato è 531,441.

Richiesta

Si scriva un programma in linguaggio C (chiamiamolo potenza.c) che legga da terminale la base a, anche non intera, e l'esponente b (deve essere intero positivo) e che calcoli la potenza a^b utilizzando il metodo appena descritto.

La stampa del risultato dovrà essere preceduta da uno specifico marcatore POTENZA scritto tra parentesi quadre. Ad esempio, a fronte della sequenza di input 2.5 e 3 il programma dovrà stampare le righe:

[POTENZA]
15.625

Si compili il programma con il comando

gcc -Wall potenza.c

e lo si esegua per verificarne la correttezza.

Verifica automatica

Scarica una versione eseguibile di pvcheck.

I casi di test sono descritti nei file potenza.test. Si verifichi la correttezza del programma scritto precedentemente tramite il comando

./pvcheck -f potenza.test ./a.out

Si corregga il programma finché non fornisce la risposta corretta.

NOTA: l'opzione -f potenza.test è necessaria in quanto il nome del file differisce da quello predefinito pvcheck.test. Infatti, se pvcheck viene invocato come segue

./pvcheck ./a.out

non bisogna specificare l'opzione -f perché pvcheck cerca automaticamente un file di test chiamato pvcheck.test.

Indicazioni per la soluzione

  • scrivi la funzione main (vedi S2.1)
  • dichiara le variabili necessarie a contenere i dati del problema (es., a, b e risultato)
  • leggi il valore delle variabili necessarie da tastiera usando fgets, atoi e atof (ricorda di dichiarare la stringa "di supporto") (vedi S4.1
  • utilizza il costrutto iterativo while per effettuare il ciclo (vedi S4.7 per la sintassi)
  • utilizza vari costrutti if (vedi S4.3 per la sintassi)

Suggerimenti

  • il programma deve considerare il caso in cui l'utente inserisca un valore di b negativo, nel qual caso stampi la stringa non calcolabile nella riga successiva al marcatore
  • potrebbe servire l'impostazione di condizioni logiche "complesse" nei costrutti condizionali; gli operatori logici necessari sono descritti in S4.5;
  • non dimenticare di includere stdlib.h per l'uso di atoi e atof (e, come già sai, di stdio.h per printf e fgets)
  • dal momento che serve individuare la condizione per cui b è dispari, si può usare l'operatore % oppure il metodo del troncamento della divisione intera (vedi gli esempi in S4.3 e S4.4)

ATTENZIONE: l'espressione a^b può essere fuorviante:

  • anche se viene usata spesso in informatica per indicare l'elevamento a potenza, in C non ha questo significato: non indica l'elevamento a potenza!
  • si tratta comunque di una espressione valida in linguaggio C, perché l'operatore ^ viene usato per l'operazione di XOR binario (è illustrato in S11.6.3)
  • in C non esiste un operatore specifico per l'elevamento a potenza, quindi questa operazione va svolta esplicitamente con dei cicli (come in questo esercizio)

Nella prossima pagina potrai esaminare un esempio di soluzione dell'esercizio.