Problème invariant algorithme drapeau

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour à tous, je bloque depuis hier sur un l'algorithme des drapeaux ,qui consiste à remettre dans l'ordre n boules blanches,rouges et bleues afin d'avoir les bleues en tête ,les blanches au milieu et les rouges à la fin par échanges successifs de boules prises deux à deux ,tout ceci en faisant le moins d'échanges possibles.
Dans cet exercice on doit écrire ce programme qui respecte l'invariant suivant :
- Si 1<=i<r1 alors couleur(i)=bleu
- Si r1<=i<r2 alors couleur(i)=blanc
- Si r3<i<=n alors couleur(i)=rouge
Mon idée de base après avoir un peu cherché était de fixer r1=1 ,r2=1 et r3=n au début puis faire varier r2 jusqu'à ce que r2=r3 ,sauf que cette solution ne respecte pas l'invariant puisque que r1>1 selon l'invariant. et je n'arrive pas à trouver des solutions qui respectent cet invariant ,donc si vous avez des idées je suis preneur. Sur ce bonne après-midi :) .

Édité par Octodex

+0 -0

Vu que tu connais les valeurs $r_1$, $r_2$ et $r_3$, tu connais a l'avance la position des boules. Tu peux donc déterminer, pour chaque boule si elle est bien placée ou non.

Tant qu'il y a des boules mal placées.

  1. Si il existe deux boules mal placées dont l'inversion les placerait1 au bon endroit, faire cette inversion. (ex: Une boule bleue dans la zone blanche et une boule blanche dans la zone bleue.)
  2. Sinon, intervertir deux boules mal placées prise1 au hasard.

J'ai pas la preuve que ça marche. Mais vu qu'on a que 3 catégories, intervertir deux boules a l'étape (2) en place forcément une qui respecte la condition en (1).


  1. Pluriel ? 

+0 -0
Auteur du sujet

Le problème c'est que ta deuxième condition ne respecte pas forcément l'invariant ,et l'on ne connait pas r1,r2,r3 à l'avance il faut les trouver de façon à ce qu'ils respectent l'invariant.Mais merci quand même.
PS : c'est bien "placerait" car c'est "l'inversion" qui est le sujet et "prises" avec "s" ;)

Édité par Octodex

+0 -0

Si tu ne peux pas compter les boules de chaque couleur avant de les trier, il va falloir utiliser un algorithme de tri. Si t'es obligé de n'intervertir que deux boules à la fois, tu vas devoir faire un tri en place.

Le problème c'est que ta deuxième condition ne respecte pas forcément l'invariant

Je suis pas sûr mais, avec la boucle while, je pense que, à la fin, les boules seront triés.

+0 -0
Auteur du sujet

Je pense qu'on peut les compter ,le problème c'est que l'invariant doit être vérifié dès le début du programme. Parce que le problème c'est l'invariant je ne sais pas quelles valeurs je dois affectés à r1,r2,r3 au début du programme pour que l'invariant soit vérifié.

Édité par Octodex

+0 -0
Auteur du sujet

J'ai réussi à résoudre mon problème en posant comme conditions initiales sur r1,r2,r3 que : r1=0
r2=0 r3=n
Le problème est résolu dès que r2=r3
De là j'ai décidé de déplacer mon index r2 entre 0 et r3 (puisque c'est la zone qui n'est pas triée ) avec une boucle.
Du coup je met le code si ça peut servir on ne sait jamais ;) . Après grâce à l'invariant j'ai déduit les conditions pour les déplacements et les permutations.

 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
import random
Taille=10
def retour_liste_initialise():
    type_boules={0:"Bleu",1:"Blanc",2:"Rouge"}
    liste=[]
    for i in range(Taille):
        liste.append([type_boules.get(random.randint(0,2))])
    return liste

#On échange les valeurs (valeur_1=valeur_2 et valeur_2=valeur_1)
def echanger_valeur(valeur_1,valeur_2):
    valeur_temporaire=valeur_1[0]
    valeur_1[0]=valeur_2[0]
    valeur_2[0]=valeur_temporaire


liste=retour_liste_initialise()
#Valeurs initialisées r1,r2,r3
r1,r2=0,0
r3=len(liste)-1
while r2!=r3:
    if liste[r2][0]=="Blanc":
        r2+=1
    elif liste[r2][0]=="Bleu":
        echanger_valeur(liste[r2],liste[r1])
        r1,r2=r1+1,r2+1
    else:
        echanger_valeur(liste[r2],liste[r3])
        r3-=1
    print(liste)

Merci quand même à ceux qui m'ont aidé :)

Édité par Octodex

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte