Les algorithmes classiques

🟠 Difficile

Les énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres suivent l'accès à la famille « Algorithmique et Python ».

1
Décris l'algorithme du seuil pour la suite définie par un premier terme égal à 1 et par la relation donnant chaque terme comme le triple du précédent augmenté de 2, afin de trouver le premier rang où elle dépasse 100.
Voir le corrigéoffert
On initialise le terme courant à 1 et le rang à 0.
Tant que le terme courant ne dépasse pas 100, on calcule le terme suivant en le remplaçant par son triple augmenté de 2, et on augmente le rang de 1.
On déroule : 1, 5, 17, 53, 161. Le terme 161 est le premier à dépasser 100.
Il a été obtenu au rang 4 : c'est la réponse. L'ordre des deux instructions dans la boucle est sans importance ici, mais le compteur doit être augmenté à chaque tour, sans exception.
2
Démontre que l'algorithme d'Euclide par soustractions se termine toujours.
Voir le corrigéoffert
À chaque étape, on remplace le plus grand des deux nombres par leur différence, qui est strictement plus petite et strictement positive tant que les deux nombres diffèrent.
La somme des deux nombres est donc un entier positif qui décroît strictement à chaque tour.
Une suite d'entiers positifs strictement décroissante ne peut pas être infinie : elle atteint nécessairement une situation où les deux nombres sont égaux.
L'algorithme s'arrête donc, et il s'arrête sur le PGCD, puisque chaque étape conserve l'ensemble des diviseurs communs.
3
On cherche une solution par dichotomie sur un intervalle d'amplitude 1, avec une précision de $0{,}01$ . Détermine le nombre d'étapes nécessaires.
🔒 Corrigé réservé aux abonnésS'abonner →
4
Décris le tri par insertion et applique-le à la liste [4, 2, 7, 3].
🔒 Corrigé réservé aux abonnésS'abonner →
5
Compare le nombre d'opérations d'une recherche séquentielle et d'une recherche dichotomique sur une liste d'un million d'éléments.
🔒 Corrigé réservé aux abonnésS'abonner →
6
Explique comment estimer la valeur de $\pi$ par une simulation, et décris le principe du calcul.
🔒 Corrigé réservé aux abonnésS'abonner →
7
Explique pourquoi il suffit de tester les diviseurs jusqu'à la racine carrée de n pour savoir si n est premier.
🔒 Corrigé réservé aux abonnésS'abonner →
8
Décris l'algorithme d'exponentiation rapide pour calculer une puissance, et applique-le au calcul de 3 élevé à la puissance 8.
🔒 Corrigé réservé aux abonnésS'abonner →
9
Explique ce qu'est un invariant de boucle, et donne celui de l'algorithme qui calcule la somme des entiers de 1 à n.
🔒 Corrigé réservé aux abonnésS'abonner →
10
Une simulation estime la fréquence d'un événement sur 1000 répétitions, puis sur 100 000. Compare la fiabilité des deux estimations.
🔒 Corrigé réservé aux abonnésS'abonner →

Comment ça s'est passé ?

Retrouve tout dans Mon suivi.

← Changer de niveau