Prima Esercitazione in Laboratorio


In questa esercitazione si richiede di risolvere alcuni problemi tramite metodi ricorsivi.
In caso di difficolta', e' possibile consultare lo svolgimento guidato degli esercizi proposti.

Potenze

Per calcolare la potenza , con e , invece di eseguire moltiplicazioni e' possibile sfruttare la seguente osservazione:

Si richiede di:

  1. Scrivere un metodo double potenza(double x, int n) che restituisca il valore , facendo uso dell’osservazione precedente. Usare la ricorsione.
  2. Effettuare opportuni test di funzionamento del metodo.
  3. Determinare la complessita' computazionale del metodo potenza in funzione:
    1. di n;
    2. della dimensione dell’input.

Potenza - Stima sperimentale del costo

Modificare il codice del calcolo della potenza in modo da poter valutare il numero di volte in cui la istruzione predominante viene eseguita.
In particolare:

Potenza - Confronto sperimentale dei costi con l'algoritmo "banale"

Realizzare una implementazione iterativa classica del calcolo della potenza (moltiplicazioni ripetute) ed individuarne la complessita in funzione di n (esponente)

Permutazioni

Scrivere un metodo void permutazioni(int[] arr) che, ricevuto in input un array di interi distinti, stampi tutte le permutazioni dell’array.
Per esempio se arr = {1, 2, 3} un possibile output e' il seguente:

{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}

Testare estensivamente il metodo, e determinarne la complessita' computazionale.

Esercizio per casa: Fibonacci

La successione di Fibonacci è una sequenza di numeri interi naturali definibile assegnando i valori dei due primi termini, F0:= 0 ed F1:= 1, e chiedendo che per ogni successivo sia Fn := Fn-1 + Fn-2.
Il termine F0 viene aggiunto nel caso si voglia fare iniziare la successione con 0; storicamente il primo termine della successione è F1:= 1. Si richiede
Incrementare l'efficienza dell'algoritmo evitando di computare uno stesso valore f(i) piu' volte: Si raccomanda di tabellare i valori calcolati e il numero di chiamate ricorsive effettuate.