Recherche du maximum dans un tableau trié décalé
Vous avez vu en cours le principe de la recherche d'un élément
dans un tableau trié, faite de manière dichotomique.
Une implémentation de la recherche dichotomique vous est proposée
ci-dessous. Ce programme calcule en outre le nombre de
comparaisons effectuées avec des éléments du tableau. On ne compte
pas les comparaisons entre indices (telles que (droite>=gauche)),
mais les comparaisons, soit entre x et un élément du tableau,
soit entre deux éléments du tableau. L'idée étant que,
même si dans le cas présent nous avons affaire à un tableau
d'entiers, dans le cas général les éléments sont des
objets complexes et la comparaison entre deux éléments est une opération
coûteuse. Ce sont donc ces opérations que nous comptons.
#include <stdio.h>
#define N 1024
typedef enum {
false,
true
} boolean;
/** t[0..taille-1] est un tableau trie dans l'ordre croissant, valeur est l'element
a rechercher dans t; cette fonction retourne true ssi "valeur" est dans t,
et dans ce cas elle modifie la valeur sur laquelle pointe nbcomp_ptr en lui
ajoutant le nombre de comparaisons effectuees avec des elements de t.**/
boolean RechercheDichotomique (int t[], int taille, int valeur,
int *resultat_ptr, int *nbcomp_ptr)
{ int gauche=0, droite=taille-1, milieu;
boolean fini=false, succes;
while (!fini)
{ milieu=( gauche + droite)/2;
(*nbcomp_ptr)++;
if (valeur == t[milieu])
{fini=true; succes=true; *resultat_ptr=milieu;}
else {(*nbcomp_ptr)++;
if ( valeur < t[milieu])
droite = milieu-1;
else
gauche = milieu+1;
if (droite < gauche)
{fini=true; succes=false;}
}
}
return (succes);
}
main()
{ int t[N];
int i, taille, valeur, resultat, nbcomp=0;
boolean trouve;
/** Entree du programme pourcorrection automatique (aucun test d'erreur)**/
scanf("%d", &taille);
for (i=0; i<taille; i++)
scanf("%d", &t[i]);
scanf("%d", &valeur);
/** Calcul **/
trouve = RechercheDichotomique(t, taille, valeur, &resultat, &nbcomp);
/** Affichage pour correction automatique **/
if (trouve)
{printf("%d %d\n", resultat, nbcomp);}
else
{printf("%d n'est pas dans le tableau.\n",valeur);}
}
Nous vous demandons de résoudre par une méthode
similaire le problème suivant.
Votre programme sera corrigé automatiquement, il est donc
important de satisfaire aux spécifications ci-dessous.
Entrée. On se donne un tableau d'entiers t[0..n-1], qui représente le décalage circulaire d'un tableau trié : autrement dit, il existe une valeur k telle que
t[k+1 mod n] < t[k+2 mod n] < ... < t[k mod n].
Par exemple, le tableau 3,4,6,8,1,2 satisfait à cette condition avec k=3 et n=6. On ne connaît pas la valeur de k. Le format d'entrée consiste en un premier entier donnant n, suivi par une suite de n entiers qui sont les n éléments du tableau, t[0] t[1] ... t[n-1]. Par exemple voici une entrée possible : 5 30 40 10 20 30Sortie.
Le but de votre programme est de déterminer la valeur de l'élément
maximum du tableau. Le programme doit également donner le
nombre de comparaisons effectuées entre éléments du tableau.
Le format de sortie consiste en un premier entier donnant la valeur
de l'élément maximum
du tableau, suivi d'un deuxième entier donnant le nombre de
comparaisons effectuées entre éléments du tableau. Par exemple:
40 2
Contrainte d'efficacité. L'algorithme de recherche dichotomique fait au plus log2(n) comparaisons avec des éléments du tableau. Votre solution pour le problème du maximum décalé doit également satisfaire à cette propriété.
Jeu de tests. Sur les données ci-dessous, le programme du corrigé donne les réponses suivantes.
| Données d'entrée | Sortie |
| 1 5 | 5 0 |
| 10 10 20 30 40 50 60 70 80 90 100 | 100 4 |
| 10 20 30 40 50 60 70 80 90 100 10 | 100 4 |
| 10 30 40 50 60 70 80 90 100 10 20 | 100 3 |
| 10 40 50 60 70 80 90 100 10 20 30 | 100 3 |
| 10 50 60 70 80 90 100 10 20 30 40 | 100 3 |
| 10 60 70 80 90 100 10 20 30 40 50 | 100 4 |
| 10 70 80 90 100 10 20 30 40 50 60 | 100 4 |
| 10 80 90 100 10 20 30 40 50 60 70 | 100 3 |
| 10 90 100 10 20 30 40 50 60 70 80 | 100 3 |
| 10 100 10 20 30 40 50 60 70 80 90 | 100 3 |