Complète la fonction indice_min qui prend en paramètre un tableau non vide de nombres et qui renvoie l'indice de la première occurrence du minimum de ce tableau.
Les tableaux seront représentés sous forme de liste Python.
La fonction tri_selection qui prend en paramètre un tableau tableau de nombres entiers et qui trie ce tableau en place (c'est-à-dire que le tableau est modifié) par ordre croissant des valeurs.
On utilisera l'algorithme suivant :
On parcourt le tableau de gauche à droite :
on recherche le minimum du tableau entre cette position courante et la fin du tableau
D'après Le Larousse : « En logique, place occupée par un symbole dans une formule. »
Le nombre d'occurrences du caractère "o" dans "bonjour" est 2 ;
le nombre d'occurrences du caractère "b" dans "bonjour" est 1 ;
le nombre d'occurrences du caractère "B" dans "bonjour" est 0 ;
le nombre d'occurrences du caractère " " dans "Bonjour à tous !" est 3.
On souhaite stocker les nombres d'occurrences dans un dictionnaire dont les clés sont les caractères de la phrase et les valeurs le nombre d'occurrences du caractère.
Écrire une fonction occurrence_caracteres prenant comme paramètre une chaine de caractères phrase. Cette fonction doit renvoyer un dictionnaire des nombres d'occurrences des caractères présents dans phrase.
On s'intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d'une liste donnée de valeurs de pièces et de billets.
Le système de monnaie est donné sous forme d'une liste de valeurs décroissantes définie de façon globale et qui peut être utilisée dans les fonctions sans être donnée en paramètre.
On suppose qu'il n'y a pas de limitation quant au nombre de pièces et billets disponibles.
On souhaite, étant donnée une somme à rendre, déterminer la plus petite liste de pièces dont la somme est égale à celle-ci.
L'algorithme utilisé est le suivant :
On regarde les valeurs possibles en partant de la plus grande;
Si on peut rendre la valeur considérée, on le fait.
Sinon on passe à la valeur inférieure.
On continue tant que l'on n'a pas tout rendu.
La fonction rendu_monnaie prend en paramètre un entier a_rendre qui correspond à la somme à rendre et renvoie la liste des valeurs rendues, dans l'ordre décroissant.
Cette fonction utilise une fonction récursive rendu_monnaie_rec qui implémente l'algorithme ci-dessus.
Les deux façons d'écrire rendu_monnaie_rec
On propose 2 façons d'écrire la fonction rendu_monnaie_rec :
Dans cette version, la fonction rendu_monnaie_rec prend 2 paramètres :
a_rendre : un entier qui correspond à la somme à rendre.
i : un entier qui correspond à l'indice de la valeur considérée dans PIECES.
Elle renvoie la liste des valeurs rendues, dans l'ordre décroissant.
Si on peut rendre PIECES[i], on concatène cette valeur devant la liste obtenue par l'appel récursif.
Cette version est plus simple à écrire, mais la concaténation nécessite de recopier toutes les valeurs de la liste à chaque fois, ce qui donne un coût quadratique à cette implémentation.
On souhaite se diriger à l'intérieur d'une ville, et notamment savoir s'il est possible de tourner en rond.
On représente la circulation dans une ville par un graphe orienté, où chaque sommet correspond à un lieu de la ville et chaque arête au sens de circulation entre deux lieux.
Exemple de plan de circulation
flowchart LR
A([Lycée]) --> B([Mairie])
B --> A
B --> E([Médiathèque])
C([Port]) --> B
B --> C
D([Ecole]) --> G([Maison])
E --> B
E --> D
G --> E
E --> F([Stade])
F --> G
Pour aller au Stade depuis le Lycée, on pourra emprunter le chemin Lycée - Mairie - Médiathèque - Stade.
Il est à noter que depuis la Médiathèque, on peut revenir à la Médiathèque en passant par l'Ecole puis la Maison.
Imaginons maintenant qu'il y a des travaux sur certaines routes qui sont désormais fermées. La circulation devient alors :
flowchart LR
A([Lycée]) --> B([Mairie])
B --> E([Médiathèque])
C([Port]) --> B
D([Ecole]) --> G([Maison])
E --> D
E --> F([Stade])
F --> G
Dans ce nouveau graphe, il n'y a plus de chemin possible depuis la Maison vers le Port.
De plus, quel que soit le lieu, il n'existe pas de chemin qui part de ce lieu et qui y revient.
On représente ce graphe par un dictionnaire dans lequel :
les clés sont les chaînes de caractères correspondant aux noms des lieux,
les valeurs associées sont des listes de chaînes de caractères représentant les lieux vers lesquels on peut se diriger.
1. Fonction existe_chemin
On se demande si, connaissant un plan de circulation, il est possible de se rendre d'un point de départ à un point d'arrivée.
Vous devez donc d'écrire une fonction existe_chemin qui :
prend en paramètre un dictionnaire graphe représentant une telle circulation, une chaîne de caractères
depart qui représente le lieu de départ et une chaîne de caractères arrivee qui représente le lieu d'arrivée ;
renvoie True si un chemin existe entre le lieu de départ et le lieu d'arrivée, False sinon.
Un promeneur se demande s'il est possible, connaissant le plan de circulation, de faire au moins une promenade débutant et se terminant au même endroit de la ville : une promenade allant du Lycée au Lycée ou une autre allant du Port au Port, etc.
Si au moins une telle promenade existe, on dit que le graphe représentant le plan de circulation contient un cycle.
Vous devez donc d'écrire une fonction contient_cycle qui :
prend en paramètre un dictionnaire graphe représentant une telle circulation ;
renvoie True si le graphe contient un cycle, False sinon.
La fonction existe_chemin de la question précédente est déjà importée dans cet éditeur.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)