es30

Il Massimo Comune Divisore tra due numeri x e y, secondo l'algoritmo di Eulero si puo' definire ricorsivamente nel seguente modo:

Se y e' 0 allora il MCD e' x.
Altrimenti, il MCD tra x e y e' uguale al MCD tra y e il resto della divisione x / y.




Scrivere una funzione ricorsiva che stampa gli elementi di una fetta di array che inizia all'indice inizio e finisce all'indice fine.




Scrivere una funzione che restituisce la somma, calcolata in modo ricorsivo, degli elementi di una fetta di array di interi che inizia all'indice inizio e finisce all'indice fine.



Ricerca dicotomica ricorsiva.
Scrivere una funzione che restituisca l'indice di dove trova un occorrenza di un numero n all'interno di una fetta di array che inizia all'indice inizio e finisce all'indice fine, eseguendo una ricerca dicotomica ricorsivamente.





















void stampa_array(char arr[], int inizio, int fine) {
  if (inizio <= fine) {
    std::cout << arr[inizio];
    if(inizio < fine)
      stampa_array(arr, inizio + 1, fine);
  }
}

int main() {
  char arr[] = "Francesco Balestrazzi";
  stampa_array(arr, 10, 14);
}






Intuitivamente:

Per trovare un numero all'interno di una fetta di array:
Se la fetta in cui stiamo cercando ha lunghezza 0, allora non lo abbiamo trovato.
Altrimenti,
Calcoliamo la meta' dell'array;
Se il numero che cerchiamo e' piu' piccolo dell'elemento a meta', lo proviamo a cercare nella fetta di array a sinistra.
Altrimenti, se il numero e' piu' piccolo lo proviamo a cercare nella fetta di array a destra.
Se il numero che cerchiamo, invece, e' uguale all'elemento al centro, allora lo abbiamo trovato al centro della fetta.



es: cerco 6 all'interno di {1, 4, 5, 6, 7, 9} (fetta tra 0 e 5)
la meta' e 2.
il mio numero e' piu grande di 5, allora cerco nella fetta a destra (tra 3 e 5).

cerco 6 all'interno di {6, 7, 9} (fetta tra 3 e 5).
la meta' e' 4.
il mio numero e' piu' piccolo di 7, allora cerco nella fetta a sinistra (tra 3 e 3).

cerco 6 all'interno di {6} (fetta tra 3 e 3).
la meta' e' 3.
il mio numero e' uguale a 6, allora lo ho trovato alla posizione 3.




es: cerco 3 all'interno di {1, 4, 5, 6, 7, 9} (fetta tra 0 e 5)
la meta' e 2.
il mio numero e' piu grande di 5, allora cerco nella fetta a sinistra (tra 0 e 1).

cerco 3 all'interno di {1, 4, 5} (fetta tra 0 e 1).
la meta' e' 0.
il mio numero e' piu' grande di 1, allora cerco nella fetta a destra (tra 1 e 1).

cerco 3 all'interno di {5} (fetta tra 1 e 1).
la meta' e' 1.
il mio numero e' piu' piccolo di 5, allora cerco nella fetta a sinistra (tra 1 e 0).

cerco 3 all'interno di {} (fetta tra 1 e 0).
la fetta non ha elementi.
non ho trovato il numero.







int ricerca_dicotomica(int pagliaio[], int ago, int inizio, int fine) {
  if(inizio <= fine) {
    int centro = (inizio + fine) / 2;

    if( pagliaio[centro] < ago )
      return ricerca_dicotomica(pagliaio, ago, centro + 1, fine);
    else if ( pagliaio[centro] > ago )
      return ricerca_dicotomica(pagliaio, ago, inizio, centro - 1);
    else
      return centro;
  }

  return -1;
}