IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

algorithme de tri


Sujet :

Algorithmes et structures de données

  1. #21
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Donc, si je comprends bien,
    Je peux mettre une boucle et ramener tous les 0 au début du tableau.
    Puis je n'aurais qu'à trier la partie ou finissent les 0, donc trier les 1 et 2.
    c'est en gros ça, où est ce qu'il vaut mieux proceder d'une autre manière?
    Vous savez, j'ai peur de dire des bétises.
    Citation:
    il faut "Diviser pour régner" !

    Quelque chose me dis que tu l'avais vu avant moi
    Moi aussi, je pense.

  2. #22
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par lcfseth Voir le message
    Quelque chose me dis que tu l'avais vu avant moi
    C'est bien possible.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #23
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    oui et non.
    Cela répondrait probablement à la question mais tu manquerais le but même de l'exercice.

    Si tu te rappelle bien, dans le premier algo, on mettait tous les 1 à la fin du tableau. Cela nous laissait les 0 au début. La variable c nous donnait aussi le debut des 1.
    Maintenant si au lieu de mettre les 1 à la fin. On mettait tous les nombres qui ne sont pas 0 (A savoir le 1 et le 2)
    on aurait les 0 au début. Cette fois la variable c nous donne le début de la partie contenant les 1 et les 2. Cette partie n'étant pas triée, on lui applique à nouveau le même algorithm.

    La solution de pseudocode est meilleure car elle utilise 2 curseurs (Droite et Gauche). Tu en aura besoin pour le nouvel algo.

  4. #24
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Oui, voilà, c ça ?
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
     
    tab: tableau [1..n]
    debut
    i:=1
    c:=n
    tantque i<= n et c>=i faire
     
    si tab[i] !=0  alors k := tab[c] //permutation
                        tab[c]:=tab[i]
                       tab[i]:=g
                       c--
                 sinon i++
    finsi
    fintantque
     
    i :=n
    tantque c<= n et i>=c faire
    si tab[c] = 2 alors tab[i] := tab[c]
                        tab[c] := 1
                        i--
                  sinon c++  
    finsi
    fintantque
    fin

  5. #25
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    Ca m'a l'air bon. Maintenant que tu a trouver un solution viable, une bonne idée serait maintenant d'essayer d'optimser ton code. Tu aura rarement l'occasion de faire de la recherche en environnement pro donc profite e.n.

    Bien, la premiére chose à remarque est qu'il y a du code qui se répéte. Géneralement, on devrait pouvoir eviter cela en utilisant une boucle.

    Notre code va appliquer le même code, en recherchant les 0, puis les 1.
    Suffit donc de definir 2 variables Min,Max et de faire un boucle dessus.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
     
    min:=0   // On définit notre ensemble. Vu qu'ici c'est (0,1,2)
    max:=2  // Min = 0 , Max = 2
    left:=1  //  left nous indique le nombre d'elements triés
     
    POUR pluspetit := min à max - 1 FAIRE // si on a trié n-1 élement, le dernier est automatiquement en place
    right:= n // On commence toujours à la fin pour le swap
    TANTQUE left<=right FAIRE
        SI tab[left]=pluspetit ALORS
            left++
        SINON
            tmp:=tab[right] //permutation
            tab[right]:=tab[left]
            tab[left] := tmp
            right --
        FINSI
    FINTANTQUE // A la fin de cette boucle, left nous donne le nombre d'elements en place.
    FINPOUR
    L'inconvenient de ce code, est qui si par exemple on avait ces 3 élements (0 , 1 , 10000 ), la premiere boucle va effecteur 10000 - 1 itérations au lieu de 3. La solution est alors d'utilisé un tableau, ou on stockera l'ensemble de depart.


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    ensemble := tableau ( 0,1,2)
    card := 3 // card(ensemble) = nombre d'elements de l'ensemble 
    left:=1  //  left nous indique le nombre d'elements triés
    
    POUR pluspetit := 1 à card - 1 FAIRE // si on a trié n-1 élement, le dernier est automatiquement en place
    right:= n // On commence toujours à la fin pour le swap
    TANTQUE left<=right FAIRE
        SI tab[left]=ensemble[pluspetit] ALORS
            left++
        SINON
            tmp:=tab[right] //permutation
            tab[right]:=tab[left]
            tab[left] := tmp
            right --
        FINSI
    FINTANTQUE // A la fin de cette boucle, left nous donne le nombre d'elements en place.
    FINPOUR
    Maintenant on a un code à peu prés potable. On appelle ce genre d'algo des algo naif parcequ'on doit lui fournir toutes les données (à savoir l'ensemble de départ). Cette algo n'est applicable que pour un ensemble fini d'elements (réponse à la 3eme question) puisqu'on peut par créer un tableau de taille infini ( Si on vous dis que le tableau contient des entiers naturels, comment faire ? ).

    Y'a sûrement un moyen de détécter le plus petit élément.
    Suite dans le prochain post :p

  6. #26
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    Je vais d'abord ecrire l'algo, je t'expliquerais ensuite l'idée.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
     
    left:=2  //  left nous indique le nombre d'elements triés, puisque nous avons suppose que le premier est le plus petit,on peut dire qu'il est deja trie :)
    pluspetitnontrie := 1
    TANTQUE  left<n // Notre condition de sorti est que left = n, à savoir tout le tableau est trié
    right:= n // On commence toujours à la fin pour le swap
    TANTQUE left<=right FAIRE
           SI tab[left]=tab[pluspetitnontrie] ALORS
               left++
           SINON
               SI tab[left] > tab[pluspetitnontrie] // Apparement notre supposition tient la route
               tmp:=tab[right] //permutation
               tab[right]:=tab[left]
               tab[left] := tmp
               right --
               SINON // ou pas :)
               tmp := tab[pluspetitnontrie]
               tab[pluspetitnontrie] = tab[left] // on suppose que notre nouvelle valeur trouvé est la plus petite
               tab[left] = tab[pluspetitnontrie]
               left := pluspetitnontrie +1  // puisque notre supposition est fausse, le nomre d'elements trie est 1                    
               // on a pas besoin de toucher right. Toutes les valeurs apres right sont superieur à notre ancienne plus petite valeur, qui est elle même superieure à notre plus petite valeur. Ils sont donc automatiquement en place :)
               FINSI
           FINSI
        FINTANTQUE // A la fin de cette boucle, left nous donne le nombre   d'elements en place.
        pluspetitnontrie := left // nous savons que toutes les cases de 1 à left -1contiennent des élements deja triés et que donc le debut de la partie à trier est left 
    FINTANTQUE
    L'idée derriere cette algo est simple. On va supposer que le premier élement de la partie à traiter contient le plus petit élement du tableau. On fait ensuite notre trie comme d'hab. Si par malheur on trouve une valeur plus petite que notre supposé valeur, on la met à jour. A savoir, on swap le premier élement avec cette nouvelle valeur et on recommence à 0.
    Je pense qu'avec un exemple tu comprendra mieux :

    Soit le tablea tab = { 5,8,9,5,0,4,10,4 }

    Dans un premier temps, on suppose que 5 est le plus petit élement
    on fait notre trie comme d'hab, des qu'on trouve un nombre plus petit (ici 4) on swap avec la premiere valeur de la partie( qui est toujours egale à notre min suppose) et on recommence à 0.
    On remarque aussi qu'a la fin de chaque iteration de la boucle exterieur, on detecte le plus petit element et on peut trouver le nombre d'occurences de cet element en faisant simplement left - pluspetitnontrie

    Legende :
    right
    pluspetitelement
    left

    Trace :

    { 5 ,8,9,5,0,4,10,4} => { 5 ,4,9,5,0,4,10,8}
    { 5 ,4,9,5,0,4,10,8} => { 4 ,5,9,5,0,4,10,8} // On retrouve un element plus petit que notre suppose min. Swap et left = pluspetitnontrie +1
    { 4 ,5,9,5,0,4,10,8} => { 4 ,10,9,5,0,4,5,8}
    { 4 ,10,9,5,0,4,5,8} => { 4 ,4,9,5,0,10,5,8}
    { 4 ,4,9,5,0,10,5,8} => { 4 ,4,9,5,0,10,5,8}
    { 4 ,4,9,5,0,10,5,8} => { 4 ,4,0,5,9,10,5,8}
    { 4 ,4,0,5,9,10,5,8} => { 0 ,4,4,5,9,10,5,8} // On retrouve un element plus petit que notre suppose min. Swap et left = pluspetitnontrie +1
    { 0 ,4,4,5,9,10,5,8} => { 0 ,5,4,4,9,10,5,8}
    { 0 ,5,4,4,9,10,5,8} => { 0 ,4,5,4,9,10,5,8}
    { 0 ,4,5,4,9,10,5,8} => { 0 ,4,5,4,9,10,5,8}

    Element 0 Trie, nombre de 0 = 1

    { 0,4 ,5,4,9,10,5,8} => { 0,4 ,5,4,9,10,5,8}
    { 0,4 ,5,4,9,10,5,8} => { 0,4 ,8,4,9,10,5,5}
    { 0,4 ,8,4,9,10,5,5} => { 0,4 ,5,4,9,10,8,5}
    { 0,4 ,5,4,9,10,8,5} => { 0,4 ,10,4,9,5,8,5}
    { 0,4 ,10,4,9,5,8,5} => { 0,4 ,9,4,10,5,8,5}
    { 0,4 ,9,4,10,5,8,5} => { 0,4 ,4,9,10,5,8,5}
    { 0,4 ,4,9,10,5,8,5} => { 0,4 ,4,9,10,5,8,5}

    Element 4 Trie, nombre de 4 = 2

    { 0,4,4,9 ,10,5,8,5} => { 0,4,4,9 ,10,5,8,5}
    { 0,4,4,9 ,10,5,8,5} => { 0,4,4,9 ,5,5,8,10}
    { 0,4,4,9 ,5,5,8,10} => { 0,4,4,5 ,9,5,8,10} // On retrouve un element plus petit que notre suppose min. Swap et left = pluspetitnontrie +1
    { 0,4,4,5 ,9,5,8,10} => { 0,4,4,5 ,8,5,9,10}
    { 0,4,4,5 ,8,5,9,10} => { 0,4,4,5 ,5,8,9,10}
    { 0,4,4,5 ,5,8,9,10} => { 0,4,4,5 ,5,8,9,10}

    Element 5 Trie, nombre de 5 = 2

    { 0,4,4,5,5,8 ,9,10} => { 0,4,4,5,5,8 ,9,10}
    { 0,4,4,5,5,8 ,9,10} => { 0,4,4,5,5,8 ,10,9}
    { 0,4,4,5,5,8 ,10,9} => { 0,4,4,5,5,8 ,10,9}

    Element 8 Trie, nombre de 8 = 1

    { 0,4,4,5,5,8,10 ,9} => { 0,4,4,5,5,8,10 ,9}
    { 0,4,4,5,5,8,10 ,9} => { 0,4,4,5,5,8,9 ,10} // On retrouve un element plus petit que notre suppose min. Swap et left = pluspetitnontrie +1
    { 0,4,4,5,5,8,9 ,10} => { 0,4,4,5,5,8,9 ,10}

    Element 9 Trie, nombre de 9 = 1



    On peut voir comment l'algo detecte automatiquement la plus petite valeur de la partie restante et comment droite converge vers pluspetitelement
    Cette algo n'a aucune contrainte.
    Je te laisse prouver que la complexite temporelle et spatiale ( O(n) et O(1)) est conforme à l'exercice.

    Je te passe aussi le code PHP qui a permit de tester l'algo

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    	function Tri()
    	{
    	$tab = array(5,8,9,5,0,4,10,4);
    		$n = 8;
    		$left = 1;
    		$pluspetitnontrie = 0;
    		while ($left < $n-1)
    		{
    			$right = $n-1;
    			while ($left <= $right)
    			{
    				$this->echoColored($tab,$n,$left,$pluspetitnontrie,$right);
    				echo (" => ");
    				if ( $tab[$left] == $tab[$pluspetitnontrie])
    				{
    					$left++;
    				}
    				else
    				{
    					if ( $tab[$left] > $tab[$pluspetitnontrie])
    					{
    						$tmp = $tab[$right];
    						$tab[$right] = $tab[$left];
    						$tab[$left]=$tmp;
    						$right --;
    					}
    					else
    					{
    						$tmp = $tab[$pluspetitnontrie];
    						$tab[$pluspetitnontrie] = $tab[$left];
    						$tab[$left] = $tmp;
    						$left = $pluspetitnontrie+1;
    					}
    				}
    				$this->echoColored($tab,$n,$left,$pluspetitnontrie,$right);
    				echo('<BR>');
    				
    			}
    			echo ('<br>Element '.$tab[$pluspetitnontrie].' Trie<br><br>');
    			$pluspetitnontrie = $left;		
    		}
    	}
    	
    	function echoColored($tab,$n,$left,$petit,$right)
    	{
    		echo ('{ ');
    		for ($i = 0; $i<$n;$i++)
    		{
    			if ($i>0) echo(',');
    			if ($i == $petit) echo('[ B][ U]');
    			if ($i == $left) echo('[ color="lime"]');
    			if ($i == $right) echo('[ color="red"]');
    			echo ( $tab[$i]);			
    			if ($i == $right) echo('[ /color]');
    			if ($i == $left) echo('[ /color]');
    			if ($i == $petit) echo('[ /U][ /B] ');
    		}	
    		echo ('}');
    	}

  7. #27
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Je te remercie pour tout.
    J'ai renndu mon devoir aujourd'hui.
    Je veux juste te poser une question au sujet d'un exo.
    Je veux savoir si j'ai bien répondu ou non.
    Voilà il s'agit de faire une recherche dichotomiqe sur un tableau qui contient m elements qui sont proches de l'infini. plus precisement, les n premiers elements sont *< infini avec n<m.
    Appliquer un algorithme de rechrche dichotomique pour voir si un element x<infini est dans le tableau ou pas. Mais il faut que la complexité soit logn et pas logm.
    Moi, j'ai appliqué l,algorithme sur le tableau de 1 à n.
    Je ne sais pas si vraiment ça ou non.

  8. #28
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    Pourrais tu me donner l'ennoncé exacte de l'exo. Ca me semble confus. n et m sont des données?

    Sinon pour ta solution, a tu pris en compte le cas ou X appartient au m élement proche de l'infini?

    Ps: x < infini n'a aucun sens mathematique. Tous les nombres sont < infini, sans exception. D'ailleurs l'infini n'est qu'un concept.

  9. #29
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Voilà l'énoncé,
    Étant donné un tableau trié t de n nombres entiers, la fouille dichotomique (binaire) permet de déterminer, en un temps dans O(log n), si un nombre x apparaît dans t ou non. Supposons maintenant que le tableau t (toujours trié) contient m éléments, dont presque tous sont égaux à infini (disons
    le plus grand entier pouvant être stocké dans un mot de mémoire). Plus précisément, supposons que les valeurs finies (< infini) sont stockées aux indices compris entre 1 et n et que n est beaucoup plus petit que m. Dans un tel tableau, la fouille dichotomique prend un temps proportionnel à logm. Décrivez un algorithme semblable qui détermine, en un temps dans O(log n) (et non O(logm)), si un nombre x < infini apparaît dans t ou non.
    Merci à toi.

  10. #30
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    C'est bien ce que je pensais. n n'est pas connu. On sais simplement qu'il est beaucoup plus petit que m. Ceci invalide ton algo . Il faudra ainsi chercher à deviner assez rapidement une approximation de n.
    Je te proposerais bien un solution mais je préfère que t'y réfléchisse avant.

    Petit indice : dans la recherche dichotomique, on divise souvent le tableau en n/2. Mais rien n'empêche de prendre un autre indice. Et n'oublie pas que tu ne cherche pas que x mais aussi n

  11. #31
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Moi je pensais que le n serait donné en entrée, et qu'il ne fallait pas le chercher.

  12. #32
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    n est beaucoup plus petit que m
    Cette information serait inutile si on connaissait n d'entrée.

    Ça me parait trop simple dans ce cas. non? Cela voudrais simplement dire que
    tableau ne contient que n+1 éléments Puisque de n+1 à m, nous avons une seule et même valeur (infini).

  13. #33
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Oui, je comprends, c trop facile pour être la bonne réponse.
    Donc, il faudrait trouvé le n. puis appliquer une recherche dans cette partie là.
    mais le problème est que la complexité devrait dépendre de n et pas de m.
    Mais si on cherche n dans un tableau de m elements, la complexité dependrait de quoi?

  14. #34
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    T'y est pas. Je vais t'expliquer.

    Supposons que m = 100 et que n = 8 (nous le savons pas). tu est d'accord que n est très petit devant m (en physique on parle d'un rapport de 1/1000, mais on va se contenter de 10)
    La recherche dichotomique suppose que nous divisions le t en deux parties.
    Si on divise à 50. on aura 2 partie de 25. après on divise encore pour atteindre 12 puis 6. Tu remarquera qu'on a atteint la plage qui nous intéresse (de 1 à 8 ) qu'après 3 divisions. Ils nous reste encore à chercher x. Bref c'est effectivement du log(m).

    Mais si au lieu de cela on divisait le tableau en 1/10 9/10. Nous savons que m est trés petit par rapport à m. On a donc plus de chance de trouver x dans les 1/10 que dans les 9/10.

    Dans ce cas, on fera une première division du tableau , de 1..10 et 10..100.
    On eliminant la seconde partie, on se retrouve avec un tableau de 10élement.
    Quasiment n. Ainsi on peut dire que notre algo à une complexite de log(n) à une valeur prés dépendant de n/m. Le fait que n<<m fait que cette constante devient négligeable pour des grandes valeurs de n et m.

  15. #35
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    moi, je pensais à trouver où les éléments < infini étaient stocké, et comme ça j'aurai mon n. ça parait stupide ?!

  16. #36
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    du tout. Mais je vois aucun algorithme de recherche qui te donnera le n sans dependre de m. Enfin je peux me tromper.

  17. #37
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Oui je sais, mais je me suis dis que ce qui est demandé c'est que la recherche du X depende du n.
    mais pas la recherche du n.

  18. #38
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par biba1980 Voir le message
    Oui je sais, mais je me suis dis que ce qui est demandé c'est que la recherche du X depende du n.
    mais pas la recherche du n.
    Tu n'as pas besoin de chercher la valeur exacte de "n", mais juste une position à partir de laquelle tu es certain de n'avoir que des valeurs supérieures à la valeur cherchée. C'est à dire un majorant de la valeur cherchée.

    Donc une première exploration (suivant une augmentation geométrique) pour trouver un majorant, puis une recherche dichotomique classique.

    Exemple:

    Recherche de la valeur 89, dans le tableau:
    tab[] = 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,INF,INF,INF,INF,INF,INF,...


    phase 1: recherche de l'indice d'un majorant de 89

    tab[1]=1
    tab[2]=1
    tab[4]=3
    tab[8]=21
    tab[16]=987 <--- majorant #16


    phase 2: recherche dichotomique de 89 dans les elements du tableau entre #8 (plus grand minorant) et #16 (majorant)

    tab[(8+16)/2] = tab[12] = 144 => trop haut => Recherche dans la partie gauche [#8,#11]
    tab[(8+11)/2] = tab[9] = 34 => trop bas => Recherche dans la partie droite [#10,#11]
    tab[(10+11)/2] = tab[10] = 55 => trop bas => Recherche dans la partie droite [#11,#11]
    tab[(11+11)/2] = tab[11] = 89 => trouvé !!
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  19. #39
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Oui, j'ai lu ta réponse.
    De toute façon, j'ai déjà rendu mon devoir, et dès que j'aurais la solution du prof (si toute fois elle nous la donne) je la metterai sur le site pour ceux qui aurait envie de l'avoir.
    Merci à tous. C'est pas ma première expérience dans un forum, mais la première dans ce forum là, et vous m'avez été d'une grande aide.
    En tout cas c'est sûr, ça ne sera pas la dernière.
    Bye.

  20. #40
    Membre à l'essai
    Inscrit en
    Novembre 2009
    Messages
    33
    Détails du profil
    Informations forums :
    Inscription : Novembre 2009
    Messages : 33
    Points : 12
    Points
    12
    Par défaut
    Bonjour tt le monde,
    Je donne la solution de ce problème.
    Pour chercher n (et que ce soit dans log(n)), il faut tout simplement mettre une boucle.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    i:=1
    Tant que T[i] < infini Faire
        i:=i+2
    Fin
    n:=i
    Donc, on retrouve n dans log(n)
    Après, on peut faire une recherche dichotomique sur la valeur x, entre les indice 1 et n.

Discussions similaires

  1. Complexité de l'algorithme de Tri Fusion
    Par judge06 dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 26/03/2007, 23h04
  2. A propos des algorithmes de tri..
    Par Kerwando dans le forum C++
    Réponses: 4
    Dernier message: 19/08/2006, 12h43
  3. Probleme avec mon algorithme de tri
    Par kaygee dans le forum Langage
    Réponses: 6
    Dernier message: 09/01/2006, 22h23
  4. Réponses: 16
    Dernier message: 10/11/2005, 23h51
  5. algorithme de tri tableau :afficher que les éléments unique
    Par sofiane61 dans le forum Algorithmes et structures de données
    Réponses: 19
    Dernier message: 31/03/2005, 20h50

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo