Algorithmique - TP1

1 Introduction au rendu de monnaie

Dans cet exercice, on cherche à résoudre le problème algorithmique suivant: on a une somme d’argent de N centimes à rendre, on dispose de pièces de 1,2,5,10 centimes, et le but est de rendre la somme exacte d’argent en utilisant le moins de pièce possible.

L’algorithme classique est le suivant : Commencer par rendre le nombre maximum de pièces de 10 possible, puis passer aux pièces de 5, etc.

  • Ecrire un programme python qui demande à l’utilisateur ou l’utilisatrice combien de centimes d’euros il faut rendre et qui affiche combien de pièces il faut rendre. Tester le programme sur plusieurs entrées différentes.

  • On suppose maintenant qu’on remplace les centimes par des cents américains. Il y a des pièces de 1,5,10, et 25. Testez votre nouveau programme sur plusieurs entrées différentes. Est-ce qu’il rend à chaque fois le nombre de pièces minimum ? (On ne demande pas de preuve, juste de regarder ça marche sur les exemples que vous avez choisi)

  • On suppose maintenant qu’on remplace les centimes par des pennies anglais. Il y a des pièces de 1,5,20,25. Testez votre nouveau programme sur plusieurs entrées différentes et trouvez un exemple où votre programme ne marche pas.

  • On revient au problème initial avec les euros. Modifier le programme en supposant qu’on dispose seulement de 5 pièces de 2, 5, et 10 centimes, et une infinité de pièces de 1 centimes.

2 Complexité de la multiplication

2.1 Introduction

Avant d’expliquer le but de l’exercice, tester le petit programme suivant:

import matplotlib.pyplot import plt

xlist = [1,2,3]
ylist = [1,4,9]

plt.plot(xlist, ylist)
plt.show()

Vérifiez que vous comprenez ce qu’il affiche.

2.2 Multiplication

Le petit programme suivant donne une approximation du temps nécessaire pour calculer le produit de 2 nombres de 5 chiffres:

import math
from random import randrange
from time import perf_counter_ns as clock


s = 0
for i in range(100):
    x = randrange(10000,100000)
    y = randrange(10000,100000)
    fst = clock()
    z = x * y
    snd = clock()
    s = s + snd - fst

print(s/100)

L’instruction randrange permet de choisir un nombre aléatoire dans l’intervalle considéré. L’instruction clock permet de savoir l’heure qu’il est, exprimé en nanosecondes. En faisant snd - fst, on capture donc le temps nécessaire pour l’opération z = x * y. Le temps de choisir un nombre aléatoire (les instructions randrange) est un peu long, donc il faut faire très attention de ne pas le compter dans le calcul.

  • Modifier le programme pour qu’il affiche une courbe affichant, pour \(n <= 10000\), le temps qu’il faut pour calculer le produit de deux nombres de \(n\) chiffres. Attention, pour aller plus vite, ne faites pas toutes les valeurs de \(n\), mais par exemple uniquement \(100, 200, 300 \dots 10000\).

  • On a vu en cours que le calcul du produit de deux nombres de \(n\) chiffres mettant un temps de l’ordre de grandeur de \(n^\alpha\) pour une certaine valeur de \(\alpha > 1\). Essayez de produire une courbe qui permettrait de connaître la valeur de \(\alpha\)

2.3 Exponentiation

  • Ecrire un programme qui calcule \(x^{15}\) en multipliant \(x\) par \(x\) 14 fois, et un autre programme qui calcule \(x^{15}\) avec le moins de multiplications possible. Vérifiez avec la fonction clock que le deuxième programme est plus rapide.

3 Tri

3.1 Trois nombres

  • Ecrire une fonction sort3(x,y,z) qui prend en argument trois entiers x,y,z et qui les renvoie triés du plus petit au plus grand.

On peut renvoyer 3 nombres à la fois en renvoyant un triplet:

def sort3(x,y,z):
    ????
    ????
    return (x,y,z)

qu’on peut tester ainsi:

(a,b,c) = sort3(2,5,3)
# devrait afficher 2,3,5
print(a,b,c)

  • Ecrire une procédure test_sort3(x,y,z,a,b,c) qui prend 6 arguments et qui affiche "OK" si le résultat de sort3 sur l’entrée (x,y,z) est (a,b,c), et qui affiche "FAIL" sinon.

  • En utilisant la procédure test_sort3(x,y,z,a,b,c), trouvez tous les tests qu’il faut essayer pour s’assurer que votre fonction sort3 renvoie bien le bon résultat.

  • En regardant attentivement votre code pour sort3, déterminez dans quel cas est-ce que votre algorithme est le plus rapide, et dans quel cas il est le plus lent. Vérifiez-le expérimentalement avec clock (faites 1 million d’essais)

3.2 Médiane

  • Ecrire une fonction mediane(x,y,z) qui prend en argument trois entiers x,y,z et qui renvoie l’entier médian, c’est à dire le deuxième une fois trié. Testez-là abondamment.

3.3 Quatre nombres

  • Ecrire une fonction sort4(x,y,z,w) qui prend en argument quatre entiers x,y,z,w et qui les renvoie triés du plus petit au plus grand. Testez-là abondamment.

4 Traversée

(L’énoncé vient de wikipedia).

Il était une fois un fermier qui alla au marché et acheta un loup, une chèvre et un chou. Pour rentrer chez lui, le fermier loua une barque pour traverser une rivière. Mais la barque ne pouvait contenir que le fermier et l’un de ses achats: le loup, la chèvre ou le chou. S’ils étaient laissés sans surveillance, le loup allait dévorer la chèvre ou la chèvre allait manger le chou. Le défi du fermier fut d’arriver de l’autre côté de la rivière avec ses achats intacts. Comment a-t-il fait ?

Pour modéliser le problème, on introduit 4 variables, en supposant qu’il faut traverser la rivière de la gauche vers la droite.

  • pos_ferm qui vaut 0 si le fermier est du côté gauche de la rivière, et 1 si le fermier est du côté droit de la rivière.
  • pos_loup qui vaut 0 si le loup est du côté gauche de la rivière, et 1 si le loup est du côté droit de la rivière.
  • pos_chevre, pos_chou qui sont définis de la même façon.

On utilise des entiers plutôt que des booléens pour faciliter l’écriture du programme.

Au départ, on a donc l’égalité pos_ferm=pos_loup=pos_chevre=pos_chou=0 et le but est d’avoir pos_ferm=pos_loup=pos_chevre=pos_chou=1

Voici un début de programme

pos_ferm=0
pos_loup=0
pos_chevre=0
pos_chou=0


while True:
    print("*** Positions ***")
    if pos_ferm==0:
        print("* fermier")
    else:
        print("                  * fermier")
    if pos_loup==0:
        print("  loup")
    else:
        print("                    loup")
    if pos_chevre==0:
        print("  Chevre")
    else:
        print("                    Chevre")
    if pos_chou==0:
        print("  chou")
    else:
        print("                    chou")
    question = input("Qui voulez-vous emporter avec vous de l'autre côté de la rivière ? (L pour loup, C pour chevre, c pour chou, R pour rien)")

    if question == "L":
        #TODO
        pass
    elif question == "C":
        #TODO
        pass
    elif question == "c":
        #TODO
        pass
    else:
        # rien, on change juste la position du fermier
        pos_ferm = 1 - pos_ferm

  • Complétez le programme pour qu’il traite tous les déplacements. Attention ! Dans tous les cas, le fermier doit bouger, et il ne peut emporter la chèvre (par exemple) que si elle est initialement du même côté que le fermier.

  • Trouvez la condition à mettre dans la boucle while pour que le programme s’arrête si tout le monde a traversé correctement, si la chèvre est mangée, ou si le chou est mangé.

  • Testez le programme et trouvez la solution.

5 Billiards

Dans cette première partie, on s’intéresse à faire résoudre à l’utilisateur ou l’utilisatrice le problème de logi(sti)que suivant: On dispose de deux bouteilles, de contenance 7 et 4 litres, et on veut obtenir 1 litre d’eau. Au départ, les deux bouteilles sont vides. Les 6 opérations suivantes sont possibles:

  • Remplir la première bouteille au puits;

  • Remplir la deuxième bouteille au puits;

  • Vider la première bouteille au puits;

  • Vider la deuxième bouteille au puits;

  • Transvaser la première bouteille dans la deuxième. Si on ne peut pas tout mettre, on laisse le reste dans la première bouteille;

  • Transvaser la deuxième bouteille dans la première. Si on ne peut pas tout mettre, on laisse le reste dans la deuxième bouteille.

  • Ecrire un programme qui permet d’interagir avec l’utilisateur ou l’utilisatrice, jusqu’à ce qu’une des deux bouteilles contienne exactement 1 litre d’eau. Le programme affichera le nombre de coups utilisés.

Attention: pour cet exercice, il faut évidemment utiliser une boucle while pour s’arrêter lorsque on a obtenu un volume d’1 litre. Mais aucune autre boucle n’est nécessaire. En particulier il n’est pas nécessaire (il est même déconseillé) d’utiliser une boucle pour transvaser d’une bouteille à l’autre.