Consignes

Vous devrez utiliser l'interface TPLab pour envoyer vos TP aux encadrants de TP.

La note ne valide pas seulement le résultat de votre programme, mais également son style :

Vérifiez ces points avant de demander à votre intervenant de valider votre code.

Liens utiles

Vous aurez également besoin du fichier boulet.py.

Objectifs du TP

Le but de ce TP est de revoir certains concepts vu au premier semestre (boucles, conditionnelles, fonctions) en insistant sur la qualité du code écrit. Pour ceci, il faudra suivre les règles vues en cours concernant :

Après quelques exercices préliminaires, nous allons modéliser (et dessiner) la trajectoire d'un boulet de canon en fonction de l'angle de tir, de la vitesse initiale du boulet et de sa masse. Nous chercherons ensuite à ajuster automatiquement l'angle de tir pour essayer d'atteindre une cible précise.

1. Préliminaires : recherche dichotomique

Le principe de la recherche dichotomique (Wikipedia) est de chercher une solution d'un problème en coupant l'ensemble des solutions possible en deux parties égales à chaque étape. Au bout d'un moment, soit la solution est trouvée, soit l'ensemble devient vide et il n'y a pas de solution.

Par exemple, pour trouver un nombre entre 0 et 100 par questions oui/non successives, les stratégies suivantes ne sont pas très efficaces :

  1. on pose les questions
    • Est-ce que le nombre est 0 ?
    • Est-ce que le nombre est 1 ?
    • Est-ce que le nombre est 2 ?
    • Est-ce que le nombre est 3 ?
    • ...
    jusqu'à obtenir la réponse oui. Il faut poser 50 questions en moyenne, et au pire, il faudra en poser 100 !
  2. on cherche les unités et les dizaines séparément en posant :
    • Est-ce que le chiffre des dizaines est 0 ?
    • Est-ce que le chiffre des dizaines est 1 ?
    • Est-ce que le chiffre des dizaines est 2 ?
    • ... puis celui des unités en posant :
    • Est-ce que le chiffre des unités est 0 ?
    • Est-ce que le chiffre des unités est 1 ?
    • Est-ce que le chiffre des unités est 2 ?
    • ...
    Il faut poser en moyenne 10 questions, et au pire, il faudra en poser 20 !

La strategie optimale est de séparer l'ensemble des nombre en 2 parties égales (ou presque) à chaque question. On peut poser par exemple :

Si on représente les questions sur un dessin, on a :

Avec cette stratégie, il ne faudra jamais plus de 7 questions pour arriver à trouver le nombre !

Le principe est le suivant : pour chercher un nombre entre a et b, on demande s'il est entre a et m, où m est la moyenne de a et b. Si la réponse est oui, on recommence à chercher entre a et m, et si la réponse est non, on recommence à chercher entre m+1 et b.

La procédure suivante implémente la stratégie qui pioche des nombres au hasard jusqu'à tomber sur le nombre choisi par l'utilisateur : 

from random import randint

def strategie_naive():
    """implémentation de la stratégie naïve qui cherche un nombre entre
0 et 100 choisi par l'utilisateur."""

    print("Pensez à un nombre entre 0 et 100 puis appuyez sur 'Enter'...")
    input()

    nombre = -1 # nombre cherché. Il passera à une valeur positive
                # quand on l'aura trouvé
    nb_questions = 0

    while nombre < 0:
        nb = randint(0,100)
        # on demande si le nombre est égal à nb :
        question = "Est-ce que le nombre est égal à " + str(nb) + " ? [o/n]  "
        nb_questions = nb_questions+1
        reponse = ""
        while reponse not in ["o", "n"]:
            reponse = input(question)
            if reponse == "o":
                print("oui !")
                nombre = nb
            elif reponse == "n":
                print("non...")

    print("Le nombre choisi est égal à", nombre,
          "et il a fallu", nb_questions, "questions pour le trouver")

Lisez ce programme pour comprendre comment il fonctionne, puis écrivez une procédure sur le même modèle qui implémente la recherche dichotomique...

Combien de questions sont nécessaires pour trouver un nombre entre 1 et 100 ? Entre 1 et 1000 ? Entre 1 et 10000 ?

2. Le boulet de canon...

2.1. Modélisation de la trajectoire

La trajectoire d'un objet inerte est régie par les lois de la mécanique. Nous allons utiliser une approximation de ces lois pour modéliser de manière discrète la trajectoire d'un boulet de canon.

À un instant t donné, le boulet a

et il est soumis à la force d'attraction terrestre. Au temps t + ε, la position du boulet ainsi que sa vitesse est modifiées en suivant les formules

Pour que la modélisation ressemble à la réalité physique, il faut que ε soit assez petit.

Écrivez une fonction "trajectoire_boulet" qui prend en argument les valeurs suivantes :

La valeur de retour de la fonction est la distance parcourue par le boulet avant qu'il touche le sol. (Il s'agit donc de la dernière valeur de x.)

Votre fonction devra afficher (en utilisant la procédure dessine_boulet(x,y)) le boulet aux positions intermédiaires appropriées (argument freq).

  1. Vous devez écrire votre fonction dans le fichier à trous boulet.py.
  2. Le fichier fourni comporte une ligne 

    from math import sin,cos,pi
    Vous pouvez donc utiliser les fonctions sinus et cosinus, ainsi que la constante π. Attention, les fonctions trigonométriques de Python utilisent des angles en radians, alors que votre fonction utilise un angle en degrés...
  3. Pour tester votre fonction, il suffit de lancer Python sur le fichier (menu "Run" -> "Run Module F5") et d'utiliser la petite interface.

2.2. Recherche dichotomique de l'angle pour atteindre une cible

Nous cherchons maintenant à atteindre une cible, avec une précision de 1 mètre. Pour ceci, il faudra tirer des boulets (avec la fonction trajectoire_boulet) et modifier l'angle en fonction de la distance parcourue par le boulet : on commence par tirer un boulet à 45° pour obtenir la distance maximale que l'on peut atteindre.

Écrivez la fonction dichotomie, qui prend en argument :

Votre fonction appellera la fonction précédente trajectoire pour calculer et afficher les trajectoires du boulet.

Commencez par essayer de « en cloche » en choisissant des angles entre 45° et 90°. Une fois que vous y arrivez, essayer de tirer « ras le sol » en choisissant des angles entre 0° et 45°.