Devine un nombre

L'ordinateur choisit un nombre, l'humain devine

L'ordinateur "choisit" un nombre entier "au hasard" entre 1 et 1000.

Vous devez deviner ce nombre en faisant le moins de propositions possibles et pour chaque proposition faite l'ordinateur vous "dit" si votre proposition est, plus petite ou plus grande que le nombre du départ

Voici un algorithme possible

 
 nombre_inconnu <- entier_aléatoire(1,1000)
 proposition    <- entrer("Entrez un nombre entier entre 1 et 1000")
 Tant que proposition est différent du nombre_inconnu
 début
     si proposition < nombre_inconnu 
        afficher("Votre nombre est plus petit que celui de l'ordinateur")
     sinon si proposition > nombre_inconnu
        afficher("Votre nombre est plus grand que celui de l'ordinateur")
     findesi
     proposition    <- entrer("Entrez un nombre entier entre 1 et 1000")
 fin
 afficher("Bravo, Vous avez trouvé le nombre : ",nombre_inconnu)
          
 
 

Commentaires:

  1. Nous découvrons une nouvelle façon de répéter une suite d'instructions, "la boucle Tant que"

    La répétition des instructions de la boucle dépend d'une condition ici "proposition est différent du nombre_inconnu"

  2. Il est important que cette condition soit vraie "au bout d'un certain moment" pour que la boucle s'arrête !

On traduit en python le jeu "Devine un nombre" par

 
from random import *

nombre_inconnu = randint(1,1000)
proposition    = int(input("Entrez un nombre entier entre 1 et 1000 -> "))
while proposition != nombre_inconnu:

    if proposition < nombre_inconnu :
        print("Votre nombre est plus petit que celui de l'ordinateur")
    elif proposition > nombre_inconnu:
        print("Votre nombre est plus grand que celui de l'ordinateur")
    proposition= int(input("Entrez un nombre entier entre 1 et 1000 -> " ))
    
print("Bravo, Vous avez trouvé le nombre : ",nombre_inconnu)
 
 

Exercices

  1. Introduire une variable nb_essais qui compte le nombre de propositions effectuées. Modifier l'affichage de fin de programme pour afficher le contenu de la variable nb_essais
  2. Si on remplace elif par if, qu'est ce que cela change dans l'exécution de la boucle ? (Si vous ne voyez pas utilisez pythontutor)

L'humain choisit un nombre, l'ordinateur devine

Maintenant on échange les rôles

Comment aider l'ordinateur avec un algorithme pour que ce dernier réussisse à trouver le nombre choisit par l'humain ?

L'ordinateur va mémoriser un intervalle de possibilités [choix_min; choix_max] au début cet intervalle est [1;1000], puis en fonction de la réponse faite par l'humain on va diviser par deux la taille de cet intervalle (dichotomie)

La taille de l'intervalle diminuant on finira par "tomber" sur la bonne valeur

On convient que si la proposition de l'ordinateur est plus petite que le nombre choisi par l'humain, ce dernier doit entrer -1, à l'inverse si la proposition de l'ordinateur est plus grande que le nombre choisi par l'humain, ce dernier doit entrer 1, et en cas d'égalité il doit entrer 0

Voici un algorithme possible

 
choix_min <- 0
choix_max <- 1000
proposition_ordinateur    <- (choix_min + choix_max)//2
Tant que Vrai :
    afficher("je propose ", proposition_ordinateur)
    afficher(" Si ma proposition est plus petite que votre nombre entrez -1")
    afficher(" Si ma proposition est plus grande que votre nombre entrez 1")
    afficher(" Si ma proposition est égale à votre nombre entrez 0")
    reponse_humain = entrer(" ---> ")
    si reponse_humain = -1:
        choix_min <- proposition_ordinateur
        proposition_ordinateur    <- (choix_min + choix_max)//2
        
    sinon si reponse_humain = 1:
        choix_max <- proposition_ordinateur
        proposition_ordinateur    <- (choix_min + choix_max)//2
    sinon:
        sortir de la boucle
print("Trouvé !")    
          
 
 

Commentaires:

  1. Nous avons utilisé une boucle "infinie" Tant que Vrai, qui à priori ne se termine jamais, mais ce type de boucle peut être "cassé" par une instruction de sortie de boucle
  2. Pour diviser la taille de l'intervalle par deux on réutilise la formule de la moyenne avec la division euclidienne // pour obtenir une valeur entière

On traduit en python le jeu "Devine un nombre" deuxième version par

 
from random import *

choix_min = 0
choix_max = 1000
proposition_ordinateur    = (choix_min + choix_max)//2
while True :
    print("je propose ", proposition_ordinateur)
    print(" Si ma proposition est plus petite que votre nombre entrez -1")
    print(" Si ma proposition est plus grande que votre nombre entrez 1")
    print(" Si ma proposition est égale à votre nombre entrez 0")
    reponse_humain = int(input(" ---> "))
    if reponse_humain == -1:
        choix_min = proposition_ordinateur
        proposition_ordinateur    = (choix_min + choix_max)//2
        
    elif reponse_humain == 1:
        choix_max = proposition_ordinateur
        proposition_ordinateur    = (choix_min + choix_max)//2
    else:
        break
print("Trouvé !")    
 
 

Exercices

  1. Transformer la boucle while True en une boucle while "normale"

L'algorithme de Syracuse

 
 Soit un nombre entier N
 Tant que ce nombre N est différent de 1
 début
     si N est pair 
        N <- N/2
     sinon
        N <- 3*N + 1
 fin
          
 
 

Commentaires:

  1. Si N est une puissance de 2 par exemple 32 alors N deviendra successivement 16, puis 8 puis 4 puis 2 et enfin 1
  2. Si N n'est pas une puissance de 2 par exemple 6 alors N deviendra successivement 3 puis 10 puis 5 puis 16 puis la suite 8,4,2 et 1
  3. Nous découvrons une nouvelle façon de répéter une suite d'instructions Tant qu'une expression est vraie, ici l'expression est N est différent de 1
  4. Est on sûr qu'étant donné n'importe quel entier N > 0 la répétition se terminera au bout d'un certain temps c'est à dire N deviendra égal à 1 ?

    On conjecture que cette propriété est vraie (Conjecture de Syracuse). Cette conjecture n'est pas encore prouvée. Voir ici

On traduit en python l'algorithme de Syracuse

 

 
N = int(input(" Entrez un nombre entier "))
while N != 1:
    if N % 2 == 0:
        N = N//2
    else:
        N = 3*N + 1

 
 

Commentaires

  1. On traduit "un nombre N est pair" par son reste par la division euclidienne par 2 est 0.( N % a donne le reste de la division euclidienne par a)
  2. Quelle est la différence entre / et // ? Faire des essais

Exercice

  1. On définit la suite de Syracuse de N comme étant la suite de nombres engendrée par l'algorithme de Syracuse commençant par N et se terminant par 1

    Par exemple pour N = 5, la suite est 5, 16, 8, 4, 2, 1

  2. Par exemple pour N = 6, la suite est 6, 3, 10, 5, 16, 8, 4, 2, 1

  3. On définit le temps de vol de la suite comme étant égal au nombre de répétitions de la boucle. Dans l'exemple ci-dessus le temps de vol est 8 pour N = 6 et 5 pour N = 5
  4. On définit l'altitude maximale comme étant la valeur la plus grande prise par N, pour N=5 et pour N = 6 l'altitude maximale est 16
  5. On définit le temps de vol en altitude comme étant égal au plus petit nombre de répétitions au bout duquel la valeur de N devient inférieur ou égale à la valeur initiale de N

    Par exemple pour N = 5 le temps de vol en altitude est de 3 et pour N = 6 il vaut 1

  6. Introduire trois variables temps_vol, temps_vol_altitude et altitude_max et compléter le programme ci-dessus pour que soit affiché à la fin du programme le temps de vol , le temps de vol en altitude et l'altitude maximale
  7. Quel est le nombre inférieur ou égale à 100, ayant le temps de vol le plus grand et l'altitude maximale la plus grande ?

Pour la prochaine fois

  1. Quel est le nombre entier inférieur à 100 ayant l'altitude maximale la plus élevée ? et quelle est cette altitude ?
  2. Même question pour inférieur à 1000

Que retenir ?

  1. Si on connaît le nombre de répétitions d'une boucle on utilise l'instruction for ....
  2. Si le nombre de répétitions dépend d'une condition d'arrêt de la répétition ...