Exercice langage C corrigé recherche dichotomique

Exercice langage C corrigé recherche dichotomique, tutoriel & guide de travaux pratiques en pdf.

RECHERCHE DICHOTOMIQUE DANS UN TABLEAU ORDONNE.

On considère un tableau U de I nombres entiers deux à deux distincts, rangés par ordre croissant, et un nombre Y. Ecrivez un programme qui détermine l’indice exprimant soit le rang de Y dans U soit, si Y ne figure pas dans U, le rang de l’emplacement dans lequel il faudrait ranger Y pour l’insérer dans le tableau, en conservant trié ce dernier.

Principe : considérer deux indices v et w tels que le sous-tableau [ ? … ? ] soit seul susceptible de contenir Y (initialement, v = 0 et w = I-1). En comparant Y et l’élément du milieu, déterminer celle des deux moitiés du sous-tableau qui est susceptible de contenir Y. Recommencer cette opération jusqu’à déterminer une unique position du tableau.

Estimez le nombre moyen d’opérations faites par ce programme et par celui du n° 4. Estimez le nombre moyen d’opérations faites par l’une et l’autre méthode, lorsque la recherche d’un élément qui ne figure pas dans le tableau doit être suivie de son insertion.

CLiCours.com :  Exercice 8 corrigé la surcharge des opérateurs en langage C++

La correction exercice langage C (voir page 2 en bas)

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Comments (1)

  1. J’ai besoin d’aide sur un exercice
    Ecrire un algorithme permettant de faire la recherche dichotomique de deux entiers distincts
    dans un tableau d’entiers triés. NB : Vous regarderez tous les cas possibles d’appartenance de
    ces deux entiers dans le tableau.