Algorithmique
Mina
-
Mina -
Mina -
Bonjour,
Quelqu'un pourrais m'aider à résoudre ce question.
J'ai un tableau trié de [1..n] entiers distincts, ll manque un et un seul entier dans le tableau. je dois trouver un algorithme en O(log n) qui trouve l 'entier manquant.
Merci d'avance
Quelqu'un pourrais m'aider à résoudre ce question.
J'ai un tableau trié de [1..n] entiers distincts, ll manque un et un seul entier dans le tableau. je dois trouver un algorithme en O(log n) qui trouve l 'entier manquant.
Merci d'avance
1 réponse
-
'lut, il ne manque qu'un seul et unique entier dans ce tableau trié? Les entiers, il sont consécutifs de 1?
Si c'est le cas ça peut se faire en O(n); voilà une idée de comment faire:tableau = [1, 2, 3, ... , n]
Pour i de 0 à longueur (tableau)-1:
Si tableau[i]+1 != tableau[i+1] Alors
// Discontinuité
Afficher "Il manque l'entier" + (tableau[i]+1)
FinSi
FinPour-
Mina : "je dois trouver un algorithme en O(log n)"
gravgun : "ça peut se faire en O(n)"
Oups ^^'
Pour faire du O(log n) tu as la recherche par dichotomie.
Cependant la question de gravgun est pertinente, qu'est-ce que tu entends par "ll manque un et un seul entier dans le tableau". Les entiers existent en nombre infinis, alors quel est le sous ensemble que tu manipules ? -
-
-
Alors réponds à notre question, quel est le sous ensemble que tu manipules ?
Si tu as par exemple tous les entiers entre 1 et n (sauf celui qui manque) tu sais déjà où chaque entier doit se placer. Par dichotomie tu regardes à partir de quand c'est décalé.
En gros :
j = n/2
k = n/2
Tant Que j != 1
j = j/2
Si tab[k] == k
k = k-j
Sinon
k = k+j
Fin Si
Fin Tant Que
Afficher "Il manque" k -
gravgun thnx pour l'idée KX thnx for you too.
l ensemble est de [1..n], par exemple si j ai un tableau qui contient : 0 1 2 3 4 6 7 l'algorithme doit retourner 5.
Avec la dichotomie ça me semble pas mal comme idée mais je trouve pas comment je pourrais faire exactement.....
Par exemple , utilisant la même tableau , si je dévisse le tableau en deux je trouve que m=3 et t[m]=3 si je fais la comparaison
je trouve que t[m-1]+1 = t[m]
t[m+1] -1= t[m]
donc je vais me déplacer ou après ??!!!!
-
