algo tableau tri croissant et recherche dichotomique

[balim]

URGENT!!! QUI PEUT MAIDER JE SUIS EN 1ERE ANNEE DE BTS IG ET J AI DEUX ALGOS A FAIRE LE PREMIER:
Declarer un tableau, dire qu'il faut saisir un nombre, chaque fois que l'utilisateur saisi un nombre les nombres du tableau sont rangés par ordre croissant.
LE DEUXIEME:
L orsque l'utilisateur a saisi les nombres, on supprime les doublons et on demande à l'utilisateur de saisir une valeur. On fait une recherche dichotomique de cette valeur.
merci d'avance pour votre aide.

 

[k2]

Salut, quelques indications au piff

URGENT!!! QUI PEUT MAIDER JE SUIS EN 1ERE ANNEE DE BTS IG ET J AI DEUX ALGOS A FAIRE LE PREMIER:
Declarer un tableau, dire qu'il faut saisir un nombre, chaque fois que l'utilisateur saisi un nombre les nombres du tableau sont rangés par ordre croissant.

- déclarer un tableau d'un nbre n d'entiers (n sera par ex. fixé ou entré au début) : int x[n]
- faire une boucle (for k=0 to n-1) dans laquelle l'utilisateur va fournir chacun des n entiers x[k]
- ensuite faire le tri en s'aidant de 2 boucles for imbriquées par exemple (il existe évidemment d'autres méthodes) :

for (k=0; k < n; k++)
for (j=k+1; j<n; j++)
si x[j] < x[k] alors permute les valeurs dans le tableau
pour permuter tu t'aides d'un variable temporaire temp dans laquelle tu mets la valeur x[k]
tu affectes à x[k] la valeur de x[j], puis à x[j] la valeur de temp

par exemple si tu veux trier la suite de n=3 entiers 5 2 7 tu auras (k va de 0 à 2) :
k=0 alors x[k]=x[0]=5
j=0+1=1 alors x[j]=x[1]=2 qui est plus petit q 5 alors tu permutes 5 et 2 =) nvelle suite 2 5 7
(nota: nvelle valeur de x[0]=2)
j=2 alors x[j]=x[2]=7 qui n'est pas plus petit que 2 alors pas de permutation, suite reste identiq

k=1 alors x[k]=x[1]=5
j=1+1=2 alors x[j]=x[2]=7 qui n'est pas plus petit que 5 alors pas de permutation, la suite est rangée

LE DEUXIEME:
L orsque l'utilisateur a saisi les nombres, on supprime les doublons et on demande à l'utilisateur de saisir une valeur. On fait une recherche dichotomique de cette valeur.
merci d'avance pour votre aide.

- pour supprimer les doublons tu pourrais t'aider d'une methode analogue au tri croissant basée sur des boucles imbriquées puisque tu seras obligé de comparer chacun des entiers avec les autres; ainsi ayant déjà un tableau de n entiers possedant d doublons, tu déclareras un 2e tableau de n-d entiers où tu stockeras les entiers non dédoublés.

- recherche dichotomique: soit v la valeur à chercher; le tableau x[] étant rangé, soit min et max les valeurs x[0] et x[n-1] et soit mid=(min+max)/2 l'element central du tableau
- tu compares d'abord v à mid : si v < mid tu limites la recherche à la 1ere moitié du tableau sinon à la seconde moitié; min ou max prend une nvelle valeur : dans le 1er cas max=mid-1, dans le 2e cas min=mid+1
- ensuite tu compares v au mid de la nouvelle moitié, ainsi de suite jusqu'à ce que tu n'aies plus d'intervalle (cette condition pourrait se faire dans une boucle while du genre while(min < max) )

Bonne cogitation A+

 

[morice]

je suis pas sur qu'il demandait l'algo traduit en C... :biggrin:

 

[dununfolette]

on peut avoir la traduction en algo pure ?
parce que là je rame pour comprendre ! ascompris;
(j'en suis à peu près au même point en cours d'algo donc j'aimerais bien voir ce que ça donne ! :biggrin

 

[morice]

Je te l'aurai bien fait mais là j'ai pas le temps...
Je repasserai! :smile:

 

[dununfolette]

Je te l'aurai bien fait mais là j'ai pas le temps...
Je repasserai! :smile:

merciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii ! :wub :kiss: :wub
(bah wé chu un peu folle...et alors ? :biggrin