À quelle catégorie appartient l’algorithme classique de rendu de monnaie ?

Réponses :

A- Les algorithmes de classification et d'apprentissage.

B- Les algorithmes de tri.

C- Les algorithmes gloutons.

D- Les algorithmes de mariage stable.

On dispose en quantité illimité de pièces de 1 euro, 2 euros et 5 euros. On veut totaliser une somme de 18 euros.
Quelle est la solution donnée par l’algorithme glouton ?

Réponses :

A- [5, 5, 5, 2, 1].

B- [5, 5, 5, 2, 2, 1].

C- [5, 5, 2, 2, 2, 1, 1].

D- [5, 2, 2, 2, 2, 1, 1, 1, 1, 1].

On dispose de sacs de jetons portant les nombres 10, 5, 3 et 1.
On veut obtenir un total de 21 en utilisant ces jetons.
Si on utilise le principe de l'algorithme glouton, quelle addition va-t-on réaliser pour obtenir ce total de 21 ?

Réponses :

A- 5 + 5 + 5 + 5 + 1.

B- 10 + 5 + 3 + 3.

C- 10 + 5 + 5 + 1.

D- 10 + 10 + 1.

Parmi les phrases suivantes, laquelle est vraie ?

Réponses :

A- Un algorithme glouton fournit toujours une solution optimale.

B- Un algorithme glouton est généralement moins coûteux en temps que d'autres méthodes d’optimisation.

C- Un algorithme glouton étudie tous les cas possibles pour déterminer la solution optimale.

D- Un algorithme glouton peut revenir en arrière en cas de blocage.

Un sherpa doit traverser la montagne pour vendre des marchandises dans le village voisin. Il ne peut transporter plus de 20kg dans son sac à dos et il dispose de 6 objets de poids différents et de valeurs différentes.
Voici cette liste d'objets sous forme d'un dictionnaire dont les clés sont le nom de l'objet nom, la valeur en euros valeur, et la masse en kg masse.

Objets=[{nom:"A", valeur:10, masse:8},{nom:"B", valeur:8, masse:12},
        {nom:"C", valeur:5, masse:3},{nom:"D", valeur:9, masse:6},
        {nom:"E", valeur:7, masse:5},{nom:"F", valeur:6, masse:2}]       

Il se demande quels objets choisir pour transporter la valeur totale maximale dans son sac tout en ne dépassant pas 20 kg.
Quels objets doit-il mettre dans son sac s'il applique un algorithme glouton dans la résolution de ce problème ?

Réponses :

A- Objet "B" puis objet "A"

B- Objet "A" puis objet "D" puis objet "E"

C- Objet "C" puis objet "D" puis objet "E" puis objet "F"

D- Objet "B" puis objet "E" puis objet "C"

Un commerçant vit dans un pays dont le système monétaire est constitué de pièces et de billets ayant pour valeur faciale : 1, 2, 5, 10, 20, 50, 100, 200 et 500. On note euros la liste des valeurs faciales disponibles pour un rendu de monnaie par le commerçant. (le commerçant peut posséder plusieurs pièces ou billets de même valeur)

euros = [1, 1, 1, 1, 1, 2, 2, 2, 5, 10, 10, 10, 20, 50, 100, 100, 100, 200, 500] 

On souhaite écrire un programme qui affiche la monnaie que le commerçant devra rendre.
On note s la somme à rendre en supposant que celle-ci est inférieure ou égale à 1000.
Parmi les 4 programmes suivants, lequel est correct ?

Réponses :

A-

def monnaie(s) :	    	
    i = len(euros)       		
    p = 0                     		
    while s > 0 :
        if s >= euros[i] :    		
            p +=1   	
            s -= euros[i]     	
        else :
            i = i - 1
    return p

B-

def monnaie(s) :	    	
    i = len(euros) - 1        		
    p = 0                     		
    while s > 0 :
        if s >= euros[i] :    		
            p +=1   	
            s -= euros[i]     	
        else :
            i = i - 1
    return p

C-

def monnaie(s) :	    	
    i = len(euros) - 1        		
    p = 0                     		
    while s >= 0 :
        if s >= euros[i] :    		
            p +=1   	
            s -= euros[i]     	
        else :
            i = i - 1
    return p

D-

def monnaie(s) :	    	
    i = len(euros) - 1        		
    p = 0                     		
    while s > 0 :
        if s > euros[i] :    		
            p +=1   	
            s -= euros[i]     	
        else :
            i = i - 1
    return p

On dispose de sacs de jetons portant les nombres 10, 8, 5 et 1.
On veut obtenir un total de 24 en utilisant ces jetons.
Si on utilise le principe de l'algorithme glouton, quelle addition va-t-on réaliser pour obtenir ce total de 24 ?

Réponses :

A- 8+8+8

B- 10+8+5+1

C- 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

D- 10+10+1+1+1+1

Un système monétaire contient les pièces suivantes : 24, 15, 8, 5 et 2 unités. Le nombre de pièces de chaque sorte n'est pas limité.
On souhaite rendre 40 unités.
Quelle est la solution donnée par l'algorithme glouton de rendu de monnaie ?

Réponses :

A- [15, 15, 5, 5]

B- [24, 8, 8]

C- [15, 15, 8, 2]

D- L'algorithme échouera à rendre la somme de 40 unités.

Voici un arbre, on le parcourt en partant du haut (la racine) et en descendant de branche en branche (les noeuds) jusqu'à arriver à une feuille.
Par exemple on peut faire le parcours Racine 4 puis noeud 5 puis noeud 4 puis feuille 6.
Considérons un algorithme Glouton de parcours (racine vers feuille) de cet arbre, Sélectionnant le noeud le plus grand à chaque étape.

Quel chemin cet algorithme Glouton va-t-il parcourir ?

Réponses :

A- 4-->5-->4-->9

B- 4-->7-->2-->10

C- 4-->7-->3

D- 4-->5-->8

Parmi les affirmations suivantes, laquelle décrit correctement un algorithme glouton pour rendre la monnaie ?

Réponses :

A- L'algorithme essaie toutes les combinaisons possibles afin d'utiliser le nombre de pièces minimal quel que soit le système de monnaie.

B- L'algorithme rend la monnaie en utilisant la plus grande pièce possible et en n'utilisant chaque valeur de pièces qu'une seule fois.

C- L'algorithme rend la monnaie en utilisant la plus grande pièce possible et en utilisant le nombre de pièces minimal quel que soit le système de monnaie.

D- L'algorithme rend la monnaie en utilisant la plus grande pièce possible et en utilisant le nombre de pièces minimal pour le système de monnaie européen, mais pas forcément pour d'autres systèmes.

On considère le problème où l’on doit rendre 10 euros de monnaie.
On dispose de pièces de 1,5,8 euros.
Indiquer le rendu de monnaie donné par un algorithme glouton.

Réponses :

A- 5 ; 5

B- 8 ; 1 ; 1

C- 5 ; 1 ; 1 ; 1 ; 1 ; 1

D- L'algorithme glouton échouera à rendre la somme de 10 euros.