Table des matières
⌫ Exercices sur la récursivité
Numériques
Calcul de puissance
En utilisant : $x^{2p} = \left({x^p}\right)^2$ et $x^{2p+1} = x\times x^{2p}$ proposez un algorithme de calcul de $x^p$ récursif (et efficace).
Pgdc
Proposez un algorithme récursif de calcul du pgcd
Rendre la monnaie
On dispose de pièces de 1, 2, 5, 10, 20, et 50 (en infinité). De combien de façons peut-on réaliser une somme donnée S avec ces pièces ?
Par exemple pour S = 2, la réponse est 2 (1+1 ou 2). Pour S = 5, la réponse est 4 (5 ou 1 + 1 + 1 + 1 + 1 ou 2 + 1 + 1 ou 2 + 2 + 1).
Le choix du voleur
Un voleur est face à une rue. Chaque maison peut potentiellement être cambriolée, et il sait combien chaque cambriolage lui rapportera. Il sait aussi qu'il doit impérativement éviter de cambrioler deux maisons voisines, pour ne pas donner l'alerte. Quelles maisons doit-il cambrioler pour maximiser son gain ?
Exemple : si les maisons rapportent respectivement 100, 120, 20, 20, 100, 170, 160, 40, alors il gagnera à visiter les maisons 2, 5 et 7 qui rapporteront : 120, 100 et 160.
Maximiser un score
On dispose d'une série de $n$ nombres entiers positifs (scores) ($n$ est pair), écrits sur des morceaux de papier, disposés en ligne.
Le jeu se joue à deux joueurs. Chacun son tour chaque joueur doit prendre le score à l'une ou l'autre extrémité de la ligne. Lorsque tous les scores sont ramassés, le joueur qui gagne est celui qui a le score le plus haut.
Entrée : la liste des nombres Sortie : le numéro du joueur qui a une stratégie gagnante et l'ordre de ramassage des scores si tout le monde joue de façon optimale
On pourrait penser qu'un algo qui marche bien est : Faire le total des scores 0, 2, 4, 6…. puis le total des scores 1, 3, 5, 7… commencer par jouer le total supérieur. Cet algo limite les dégâts (il assure le match nul) mais ne maximise pas le gain.
Par exemple, pour ce tirage : `[18, 3, 7, 20, 5, 7]` l'algo précédent conclue à un match nul (puisque 18 + 7 + 5 = 3 + 20 + 7 = 20) alors que le joueur qui commence a la possibilité de gagner 41 points
Figure fractale
Avec le module turtle, réalisez une figure fractale :
