1)Recherche dichotomique dans un tableau trié
Recherche séquentielle
def rechercher(tab,val):
for nombre in tab:
if nombre==val:
return True
return False
Recherche dichotomique
Tester la fonction ci-dessous
exécuter pas à pas « à la main » ou sur python tutor pour bien comprendre l’algorithme
def dichotomie(tab,val):
debut = 0
fin = len(tab) - 1
while debut <= fin:
m = (debut + fin) // 2
if val== tab[m]:
return True
if val > tab[m]:
debut = m + 1
else:
fin = m - 1
return False
comparaison
import time tab=[i for i in range(100000000)] debut1=time.time() rechercher(tab,10000000) duree1=time.time()-debut1 print(duree1) debut2=time.time() dichotomie(tab,10000000) duree2=time.time()-debut2 print(duree2)
2) Algorithmes gloutons
les algorithmes gloutons sont utilisés dans des problèmes d’optimisation. Un problème d’optimisation consiste à déterminer les valeurs des paramètres permettant de :
- minimiser ou maximiser une fonction objectif ;
- satisfaire une ou des fonctions contraintes (il existe des problèmes avec ou sans contrainte).
Ils correspondent à une solution optimale obtenue en effectuant une suite de meilleurs choix pour chaque étape de l’algorithme (à chaque étape, on fait le milleur choix possible).
Il n’y a pas de retour en arrière : quand un choix est fait à une étape, il n’est pas modifié ultérieurement et il ne modifie pas les choix précédents.
L’autre caractéristiques des algorithmes gloutons est que lorsqu’un choix est fait, on tente de résoudre un problème plus petit. On appelle cela la progression descendante.
Exemple du rendu de monnaie
Le problème du rendu de monnaie est un problème d’algorithmique qui s’énonce de la façon suivante : étant donné un système de monnaie, comment rendre une somme donnée de façon optimale, c’est-à-dire avec le nombre minimal de pièces et billets ?
Dans la zone euro, le système en vigueur, en mettant de côté les centimes d’euros, met à disposition des pièces ou billets de : 1€, 2€, 5€, 10€, 20€, 50€, 100€, 200€, 500€.
On suppose que nous avons à notre disposition un nombre illimité de ces pièces ou billets.
Vous devez rendre 423€
donne une solution sans programmation
Écrire un algorithme en pseudo-code
Implémenter l’algorithme en python
On pourra écrire une fonction rendu_monnaie(somme, systeme) qui prend en entrée la somme à rendre et le système de monnaie contenant les valeurs des pièces et billets et qui renvoie la liste des billets et pièces.
Par exemple rendu_monnaie(97, systeme_euro) doit renvoyer la liste [50, 20, 20, 5, 2]).
L’idée est la suivante : on rend la monnaie avec le plus grand billet, tant que l’on peut, puis on essaye avec le suivante, puis la suivante… Il y a une boucle for et, dans celle-ci, une boucle while.
system_euro=[500,200,100,50,20,10,5,2,1]
def rendu_monnaie(somme,systeme):
liste_pieces=[]
for valeur in systeme:
while somme>=valeur:
liste_pieces.append(valeur)
somme=somme-valeur
return liste_pieces