Per un esame universitario potrebbe servirvi allenarvi nello scrivere algoritmi divide et impera, prendiamo un esercizio a caso:
Trovare il picco di un array unimodale
Cos’è un array unimodale?
E’ un array di questo tipo:
A[0] < A[1] < A[2] < … < A[p] > A[p+1] > A[p+2] > … > A[N-1]
cioè parte crescendo fino a un punto di stallo (il picco), poi scende senza più invetire l’andamento.
Ecco come trovare il picco:
[java]//Attenzione!
//si assume per ipotesi che l’array sia unimodale
public class array_unimodale {
public static void main(String[] args){
int[] vet={1,2,3,4,7,23,12,11,10,8,7,4,2,1};
System.out.println(trova_picco(vet, 0, (vet.length)/2, vet.length-1));
}
public static int trova_picco(int[] vet, int i, int m, int f){
//Se sono minori sia sx che dx allora m è il picco!
if ((vet[m-1]
//…cerco più a dx
return trova_picco(vet, m, (f+m)/2, f);
else
//altrimenti più a sx
return trova_picco(vet, i, (m+i)/2, m);
}
}
}
[/java]