Proposer un variant
Popo
-
Popo -
Popo -
Bonjour,
Dans un exercice, on me demande de proposer un variant dans un algorithme de tri à bulles.
Voici le programme :
J'ai compris la notion de variant ( permet de s'assurer qu'une boucle se termine) mais je n'arrive pas à le mettre en forme et à l'insérer dans le programme
( j'étudie la NSI par le CNED et les cours ne sont pas clairs du tout !!!)
Merci d'avance pour votre aide
Dans un exercice, on me demande de proposer un variant dans un algorithme de tri à bulles.
Voici le programme :
def tri_bulle(tableau):
permutation=True
passage=0
while permutation:
permutation=False
passage=passage+1
for i in range(0,len(tableau)-passage):
if tableau[i]>tableau[i+1]:
permutation = True
tableau[i], tableau[i+1]=tableau[i+1],tableau[i]
return tableau
J'ai compris la notion de variant ( permet de s'assurer qu'une boucle se termine) mais je n'arrive pas à le mettre en forme et à l'insérer dans le programme
( j'étudie la NSI par le CNED et les cours ne sont pas clairs du tout !!!)
Merci d'avance pour votre aide
Configuration: Windows / Chrome 81.0.4044.122
2 réponses
-
yg_be Messages postés 23437 Date d'inscription Statut Contributeur Dernière intervention Ambassadeur 1 588
bonjour, es-tu certain qu'il s'agisse de variant?
à quoi cela sert-il précisément?
peux-tu donner un exemple dans un cas plus simple?-
def bien_trieeC(liste,indice): trieeC=True i=0 while trieeC and i<indice : if liste[i]>=liste[i+1]: trieeC=False i=i+1 return trieeC def dicho(liste, nbatrouver): Trouve =0 assert bien_trieeC(liste,len(liste)-1) #partie principale de programme dichotomie indNB = -1 a=0 b=len(liste)-1 N=b-a+1-Trouve assert N>0, "l'invariant n'est pas st positif" #en toute rigueur, il faudrait tester aussi que N est entier while Trouve==0 and a<=b : Tampon=N centre=(a+b)//2 if liste[centre]==nbatrouver : Trouve=1 indNB=centre elif liste[centre]>nbatrouver : b=centre-1 else : a=centre+1 N=b-a+1-Trouve assert N>0, "N n'est pas st positif" assert N<Tampon, "N ne decroit pas" #on sépare les deux assert pour mieux analyser quelle est l'erreur if Trouve==1 : return indNB else : return False
dans l'exemple donné par le CNED le variant est N=b-a+1-Trouve
C'est (hélas) le seul exemple qu'ils ont donné.Il faut ajouter le variant N = b – a + 1 – Trouve et un assert qui assure que le variant diminue à chaque tour de boucle.- je ne pense pas que tu puisses maîtriser ce genre de concept à partir d'exemple.
tu écris que tu as compris le concept.
si c'est vrai, peux-tu expliquer le concept, et donner un exemple où tu l'appliques, pour nous montrer que tu l'as compris?
je comprends que tu as choisi de suivre une formation au CNED. ne devrais-tu pas obtenir de l'assistance du CNED pour t''aider dans cette formation?
-
Bonjour,
Au début j'ai pensé qu'il fallait proposer une autre solution, une variante ;-)
Puis en cherchant je suis tombé sur les variant, invariant dans les boucle, pour s'assurer que cela a une fin. J'ai trouvé une explication avec un exemple simple dans cette discussion : https://openclassrooms.com/forum/sujet/question-debutant-invariant-et-variant-de-boucle
Mais cela me laisse toujours perplexe. Je ne suis pas un théoricien, mais un praticien de l'informatique.
-
