Chapitre 02

Exercices avec corrigés : Les notions de base

Énoncés

Ce chapitre propose des exercices avec corrigés en algorithmique et Python.

Manipulation des tests et des boucles

Exercice 1

Résolution des équations du premier et second degré

  1. Écrire un algorithme qui permet de résoudre l'équation en x : ax+b=0. Posez tous les cas possibles et soignez l'affichage des résultats. Les coefficients a et b sont saisis au clavier par l'utilisateur.
  2. Écrire un algorithme qui permet de résoudre l'équation en x : ax² + bx + c = 0. Posez tous les cas possibles et soignez l'affichage des résultats. Les coefficients a, b et c sont saisis au clavier par l'utilisateur.
Exercice 2

Une entreprise emploie des salariés à l'heure. Elle les paie chaque semaine suivant un taux horaire T (salaire d'une heure de travail) auquel est appliqué un coefficient k donné par :

CoefficientDescription
k = 1pour les 39 premières heures
k = 1.2de la 40ème à la 44ème heure
k = 1.5de la 45ème à la 49ème heure
k = 1.8au-delà de la 49ème heure

Écrire un algorithme qui calcule et affiche le salaire hebdomadaire d'un salarié. Le nombre d'heures effectuées (NBH) est saisi par l'opérateur ainsi que le taux horaire (T).

Exercice 3

Écrire un algorithme qui lit un nombre entier n, calcule et affiche sa factorielle.

Exercice 4

Écrire un algorithme qui lit un nombre entier n, calcule et affiche la somme suivante :

Σk=1n k² / (k+1)

Exercice 5

Le jeu consiste à deviner un nombre entier (Nm) choisi par l'ordinateur d'une manière aléatoire. L'opérateur saisit un entier (K) et l'ordinateur affiche les indications suivantes pour le guider dans l'estimation du nombre (Nm) :

  • Trop petit si K < Nm
  • Trop grand si K > Nm
  • Gagné si K = Nm
  • Perdu si le nombre de coups > Nbc

Le jeu s'arrête lorsque l'opérateur trouve le bon nombre (Nm) ou si le nombre de coups dépasse un nombre maximum (Nbc) saisi au clavier.

Écrire un algorithme (Jeu) qui prend en entrée le nombre maximal de coups (Nbc) et permet à l'opérateur de le guider à trouver le nombre (Nm) par la saisie du nombre (K), à chaque itération, et ceci en suivant les messages décrits ci-dessus. La fonction tirage_aleatoire() retourne un nombre aléatoire.

Exercice 6

On se donne un nombre entier positif (N). On dit que le nombre (IM) est l'image-miroir de (N) si les chiffres composant (N) sont renversés pour former (IM) (exemple : N=1089, IM=9801).

Écrire un algorithme permettant de saisir un entier positif (N), de calculer son image-miroir (IM) et d'afficher si (N) divise (IM).

À ne pas utiliser les transformations d'entiers en chaîne de caractères et vice versa.

Exercice 7

Écrire un algorithme qui lit 2 entiers A et B, calcule et affiche leur Plus Grand Commun Diviseur (PGCD).

  1. Méthode 1 : si un des nombres est nul, l'autre est le PGCD, sinon il faut soustraire le plus petit du plus grand et laisser le plus petit inchangé. Puis, recommencer ainsi avec la nouvelle paire jusqu'à ce qu'un des deux nombres soit nul. Dans ce cas, l'autre nombre est le PGCD.
  2. Méthode 2 :
    • si A=0 : PGCD(0,B) = B
    • si B=0 : PGCD(A,0) = A
    • si A et B sont pairs : PGCD(A,B) = 2 × PGCD(A/2, B/2)
    • si A est pair et B impair : PGCD(A,B) = PGCD(A/2, B)
    • si A est impair et B pair : PGCD(A,B) = PGCD(A, B/2)
    • si A et B sont impairs :
      • PGCD(A,B) = PGCD(A-B, B) si A > B
      • PGCD(A,B) = PGCD(A, B-A) si B > A
  3. Méthode 3 : Assigner à A la valeur de B et à B la valeur du reste de la division de A par B. Recommencer jusqu'à ce que le reste de la division soit nul.
Exercice 8

Un nombre est dit parfait s'il est égal à la somme de ses diviseurs sauf lui-même. Écrire un algorithme qui lit un entier N (avec N>0), et détermine si N est un nombre parfait.

Modifier cet algorithme pour calculer tous les nombres parfaits inférieurs à 10000.

Exercice 9

Deux nombres entiers N et M sont dits amis ou aimables si la somme des diviseurs de N sauf lui-même est égale à M et la somme des diviseurs de M sauf lui-même est égale à N.

Exemples : (220, 284), (1184, 1210), (17296, 18416), (9363584, 9437056)...

Écrire un algorithme qui lit 2 entiers positifs N et M et détermine s'ils sont amis.

Exercice 10

Un nombre est dit premier s'il n'a comme diviseur que un et lui-même.

  1. Écrire un algorithme qui lit un nombre entier n et détermine si n est premier.
  2. Modifier l'algorithme précédent pour prendre en considération les propriétés suivantes des entiers naturels :
    • Tous les nombres pairs ne sont pas premiers sauf 2.
    • Si l'entier (n) n'a pas de diviseur inférieur à √n alors (n) n'a pas de diviseur supérieur à √n.
    • Tout nombre impair n'est divisible que par un nombre impair.
Exercice 11

Les facteurs premiers de 13195 sont 5, 7, 13 et 29. Écrire un algorithme qui lit un nombre entier n et calcule son plus grand facteur premier.

Exercice 12

2520 est le plus petit nombre qui peut être divisé par chaque nombre de 1 à 10 sans aucun reste. Écrire un algorithme qui lit un nombre entier n et retourne le plus petit entier positif divisible par tous les entiers de 1 à n.

Exercice 13

Un triplet de Pythagore est un ensemble de 3 entiers naturels {a, b, c}, tel que a<b<c, pour lesquels a²+b²=c². Il existe exactement un triplet de Pythagore pour lequel a+b+c=1000. Écrire un algorithme pour trouver le produit a×b×c.

Exercice 14

La somme des entiers premiers inférieurs à 10 est 2+3+5+7=17. Écrire un algorithme qui lit un nombre entier n et calcule la somme de tous les entiers premiers inférieurs à n millions.

Exercice 15

On considère la suite (𝒰n) définie par :

𝒰0 = 1,    𝒰n = (1/2) × (𝒰n-1 + 2/𝒰n-1)

La suite (𝒰n) est convergente et limn→∞ 𝒰n = √2.

Écrire un algorithme pour calculer une valeur approchée de √2. On calcule les termes de la suite jusqu'à ce que la différence entre deux termes consécutifs devienne inférieure ou égale à ε = 10-6, |𝒰n - 𝒰n-1| < ε. Le dernier terme calculé représente une valeur approchée de √2 à ε près.

Exercice 16

Nous pouvons étendre l'algorithme précédent pour calculer une valeur approchée de la racine carrée d'un réel A positif au moyen de la suite (𝒰n) définie par :

𝒰0 = 1,    𝒰n = (1/2) × (𝒰n-1 + A/𝒰n-1)

On arrête les calculs lorsque |𝒰n - 𝒰n-1| < ε.

Exercice 17

Nous pouvons étendre l'algorithme précédent pour calculer la racine n-ième d'un réel x > 0 au moyen de la suite convergente :

𝒰0 = 1,    𝒰k+1 = (1/n) × ((n-1)·𝒰k + x/𝒰kn-1)

On arrête les calculs lorsque l'erreur relative |(𝒰k+1 - 𝒰k)/𝒰k| < ε.

Exercice 18

Soient deux suites (an) et (bn) se définissant mutuellement :

a0 = 1,    an+1 = (an + bn)/2

b0 = 1/√2,    bn+1 = √(an·bn)

On a 𝒰n = 4an² / (1 - 2·Σi=1n 2i(ai² - bi²)) → π lorsque n → ∞.

Écrire un algorithme pour calculer une valeur approchée de π.

Exercice 19

La fraction continue suivante permet de calculer une valeur approchée de π lorsque n (impair) tend vers ∞ :

π = 4 / (1 + 1²/(2 + 3²/(2 + 5²/(2 + 7²/(2 + 9²/(2 + ⋯ + n²/2))))))

Écrire un algorithme retournant une valeur approchée de π en prenant comme entrée la valeur de n.

Exercice 20

La fraction continue suivante permet de calculer une valeur approchée de π lorsque n tend vers ∞ :

π = 4 / (1 + 1²/(3 + 2²/(5 + 3²/(7 + 4²/(9 + 5²/(11 + ⋯ + n²/(2n+1)))))))

Écrire un algorithme retournant une valeur approchée de π en prenant comme entrée la valeur de n.

Exercice 21

La méthode de Viète permet de calculer une valeur approchée de π au moyen de la suite (𝒰n) définie par :

𝒰0 = 1/√2,    𝒰n = √(1/2 + 𝒰n-1/2)

limn→∞ 2 / ∏i=0n 𝒰i = π

Écrire un algorithme retournant une valeur approchée de π en utilisant la méthode de Viète.

Exercice 22

π = limk→∞ 2k·√(2 - √(2 + √(2 + √(2 + ⋯))))

avec k est le nombre de racines carrées.

Écrire un algorithme retournant une valeur approchée de π en calculant la limite précédente.

Exercice 23

Soit la suite Pn (n impair) définie par :

P1 = 2,    Pn = Pn-2 · ((n-1)/n) · ((n+1)/n)

(avec n > 1 et impair, n = 3, 5, 7, 9, 11, …)

Écrire un algorithme qui permet de calculer et d'afficher les termes de la suite Pn jusqu'à ce que la différence entre deux termes consécutifs de la suite devienne inférieure ou égale à 10-4 : |Pn - Pn-2| < 10-4

Exercice 24

On souhaite écrire un algorithme qui calcule le nombre d'or souvent désigné par la lettre φ = (1 + √5) / 2. Si l'on considère deux suites numériques (𝒰) et (𝒱) telles que :

𝒰0 = 1,    𝒰1 = 1,    𝒰n = 𝒰n-1 + 𝒰n-2

𝒱n = 𝒰n / 𝒰n-1

On montre que la suite (𝒱) tend vers une limite appelée nombre d'or nbr (nbr ≈ 1.61803398874989484820458683436564).

Écrire un algorithme permettant de calculer et d'afficher la valeur de nbr, avec une précision de ε = 10-10.

On arrête les calculs quand : |(𝒱n+1 - 𝒱n) / 𝒱n| < ε

Exercice 25

On trouve trois suites qui convergent vers le nombre d'or φ. Ce sont les suites (an), (bn) et (cn) définies par :

a0 = 1,    an+1 = 1 + 1/an

b0 = 1,    bn+1 = √(bn + 1)

c0 = 1,    cn+1 = (cn² + 1) / (2cn - 1)

N'importe laquelle de ces suites donne un algorithme très simple d'approximation de φ. Les vitesses de convergence des trois suites données ci-dessus sont fort différentes ; ainsi, pour obtenir φ avec 14 décimales, il faut calculer a37, alors que b30 et c6 donnent le même résultat.

Exercice 26

Suite inspirée de la formule de Brent-Salamin.

Soient trois suites (An), (Bn) et (Cn) se définissant mutuellement :

A0 = 1,    An+1 = (An + Bn)/2

B0 = √(1/2),    Bn+1 = √(An·Bn)

C0 = 1/4,    Cn+1 = Cn - 2n·((An - Bn)/2)²

On a : π = limn→∞ (An + Bn)² / (4·Cn)

Exercice 27

Écrire un algorithme qui lit un réel x, calcule et affiche d'après la formule suivante ex :

ex = Σk=0+∞ xk/k! = 1 + x/1 + x²/2! + x³/3! + ...

On arrête les calculs lorsque le terme Tk = xk/k! en valeur absolue est inférieur à ε une constante infinitésimale donnée.

Exercice 28

Le développement en série de Taylor de (1+x)a, avec |x| < 1 et a ∈ ℝ, est donné par :

(1+x)a = 1 + (a/1!)·x + (a(a-1)/2!)·x² + ⋯ + (a(a-1)⋯(a-n)/(n+1)!)·xn+1 + ⋯

Écrire un algorithme pour saisir deux réels a et x avec |x| < 1, calculer et afficher la valeur approximative de (1+x)a.

Exercice 29

Le développement en série entière de ln(1+x) au voisinage de 0 pour un réel x tel que |x| < 1 est donné par :

ln(1+x) = Σi=0∞ (-1)i·xi+1/(i+1) = x - x²/2 + x³/3 - x⁴/4 + ⋯

Écrire un algorithme qui permet de :

  1. Saisir un réel x tel que -1 < x < 1.
  2. Calculer une valeur approchée de ln(1+x) avec une précision eps = 10-6. Cette précision est obtenue lorsque la valeur absolue du dernier terme calculé de la série devient inférieure à eps.
Exercice 30

Le développement en série entière de sinh(x) au voisinage de 0 pour un réel x tel que |x| < 1 est donné par :

sinh(x) = x + x³/3! + x⁵/5! + ⋯ + x2n+1/(2n+1)! + ⋯

Écrire un algorithme qui permet de :

  1. Saisir un réel x tel que -1 < x < 1.
  2. Calculer une valeur approchée de sinh(x) avec une précision eps = 10-6.
Exercice 31

Soient les suites an et cn définies par :

a0 = 1,    an = an-1(1 + cn-1)

c0 = 1 - x,    cn = (cn-1)²

Pour x tel que 0 < x < 2, on a : limn→∞ an = 1/x

Écrire un algorithme qui permet de saisir un réel x tel que 0 < x < 2, de calculer et d'afficher une valeur approchée de 1/x. On arrête les calculs dès que la différence en valeur absolue entre deux termes successifs de la suite an est inférieure à une précision eps = 0.000001.

Exercice 32

Soient la suite ak et la fonction b(x) définies par :

a0 = 1.5574,    ak+1 = 2ak/(1 - ak²)

b(x) = 1 si x < 0, sinon b(x) = 0

On se propose de calculer la valeur de π par la série convergente suivante :

1/π = Σk=0∞ b(ak) / 2k+1

Écrire un algorithme qui permet de calculer et d'afficher une valeur approximative de π, sachant que le calcul se limite à la somme des 100 termes non nuls de la série.

Exercice 33

Le développement en série entière de la fonction y = 1/√(1+x) (avec |x| < 1) est donné par :

1/√(1+x) = 1 - (1/2)x + (3/8)x² + ⋯ + (-1)n·(1·3·5⋯(2n-1))/(2·4·6⋯(2n))·xn + ⋯

Écrire un algorithme qui permet de saisir un réel x (|x| < 1), de calculer et d'afficher une valeur approximative de y.

Remarque : le calcul des termes de la série s'arrête lorsque la valeur absolue du dernier terme est inférieure à une précision eps = 0.000001.

Exercice 34

Approximations de √2

On présente trois méthodes pour approcher le nombre irrationnel √2 par des nombres rationnels.

  1. La dichotomie : La méthode consiste à partir d'un intervalle qui contient le nombre que l'on cherche (ici √2) et à diminuer la taille de cet intervalle par approximations successives. On sait que √2 se situe entre 0 et 2, donc on pose a0=0 et b0=2.

    Si ((an+bn)/2)² > 2 : an+1 = an, bn+1 = (an+bn)/2

    Sinon : an+1 = (an+bn)/2, bn+1 = bn

    La précision est atteinte lorsque |((an+bn)/2)² - 2| < ε.

  2. La méthode de Newton : Pour approcher √2, on utilise le polynôme P(x) = x² - 2 dont les racines sont ±√2.

    xn = (1/2)(xn-1 + 2/xn-1)

    Le processus s'arrête lorsque |xn - xn-1| ≤ ε.

  3. Les fractions continues : √2 + 1 = 2 + 1/(2 + 1/(2 + 1/(2 + ⋯)))

    𝒰0 = 2,    𝒰n+1 = 2 + 1/𝒰n

    Cette suite converge vers une valeur approchée de √2 + 1.

Exercice 35

Chaque nouveau terme dans la suite de Fibonacci est généré par la sommation des deux derniers termes. En commençant avec 1 et 2, les 10 premiers termes seront : 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

En considérant les termes de la suite de Fibonacci dont la valeur soit inférieure à 4 millions, trouver la somme des termes pairs.

Manipulation des fonctions et des procédures

Exercice 36

Soient A et B deux fonctions de la variable entière n (n ≥ 0) :

A = 1 + 6n + 7n + 17n + 18n + 23n

B = 2n + 3n + 11n + 13n + 21n + 22n

On remarque que A = B pour les premières valeurs de n. Pour n=0 : A=B=6, pour n=1 : A=B=72, etc. Il existe un entier n pour lequel A ≠ B.

  1. Écrire une fonction F qui reçoit deux entiers k et n et renvoie kn (n>0).
  2. Écrire un algorithme qui permet d'afficher la première valeur de n pour laquelle A ≠ B.
Exercice 37

Soit P un nombre entier positif composé d'un nombre quelconque de chiffres. On cherche à déterminer si P est divisible par 21 ou non, en appliquant la méthode suivante :

  1. Supprimer le chiffre des unités de P
  2. Calculer la différence entre le nombre obtenu en a) et le double du chiffre d'unité supprimé
  3. Recommencer les étapes a) et b) jusqu'à obtenir un nombre à un seul chiffre
  4. Si le chiffre obtenu en c) est égal à 0 alors le nombre P est divisible par 21.

Exemple : Soit P = 5289417.

528941 - 2×7 = 528927
52892 - 2×7 = 52878
5287 - 2×8 = 5271
527 - 2×1 = 525
52 - 2×5 = 42
4 - 2×2 = 0

On trouve 0, donc le nombre P = 5289417 est divisible par 21.

Écrire :

  1. Une fonction Test qui reçoit un entier P et retourne un résultat booléen.
  2. Un algorithme principal permettant de saisir un entier positif P (P ≥ 100) et de tester la divisibilité par 21.
Exercice 38

Suite de Syracuse

On appelle suite de Syracuse toute suite d'entiers naturels vérifiant :

𝒰n+1 = 𝒰n/2 si 𝒰n est pair, sinon 𝒰n+1 = 3·𝒰n + 1

Par exemple, la suite de Syracuse partant de 𝒰0 = 11 est : 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

En se bornant à 1, on appelle cette suite finie d'entiers le vol de 11. On appelle étape un nombre quelconque de cette suite finie. Par exemple 17 est une étape du vol de 11. La suite atteint une étape maximale, appelée altitude maximale du vol. Par exemple 52 est l'altitude maximale du vol de 11.

  1. Créer une fonction etapeSuivante(nème terme). Elle reçoit un entier strictement positif et retourne l'entier suivant dans la suite de Syracuse.
  2. Créer une fonction vol(1er terme). Elle reçoit un entier initial strictement positif, et retourne la première valeur de n pour laquelle Un = 1.
  3. Créer une fonction altMaxi(1er terme). Elle reçoit un entier et retourne la valeur de l'altitude maximale.
Exercice 39

Pour contrôler le résultat d'une multiplication, il existe un procédé très simple, appelé la preuve par 9. Il consiste à tracer une croix et inscrire dans les espaces définis par les branches le résultat des étapes :

  1. Additionner les chiffres du premier nombre (multiplicande) et calculer le reste de la division par 9 — partie haute.
  2. Additionner les chiffres du second nombre (multiplieur) et calculer le reste de la division par 9 — partie basse.
  3. Multiplier les résultats des étapes 1 et 2, et calculer le reste de la division par 9 — partie gauche.
  4. Additionner les chiffres du résultat de la multiplication et calculer le reste — partie droite.

Il y a une erreur dans la multiplication si les chiffres aux étapes 3 et 4 sont différents.

Exemple : 2688 × 2258 = 6069504

2+6+8+8 = 24, reste de 24/9 = 6
2+2+5+8 = 17, reste de 17/9 = 8
6×8 = 48, reste de 48/9 = 3
6+0+6+9+5+0+4 = 30, reste de 30/9 = 3

Les chiffres sont égaux, la multiplication a des chances d'être exacte.

Écrire :

  1. Une procédure Modulo qui reçoit un nombre Nb et renvoie le reste de la division par 9.
  2. Une procédure SommeCh qui reçoit un nombre Nb et renvoie la somme de ses chiffres.
  3. L'algorithme principal permettant de saisir trois nombres et d'afficher le résultat du contrôle.

Manipulation des tableaux

Exercice 40

Supposons que les types suivants soient définis :

CONSTANTE N = 100
TYPE TAB = TABLEAU[1..N] de ENTIER

Nous allons créer un ensemble de sous-programmes permettant de manipuler des tableaux triés. Ces tableaux sont de taille N. La première case du tableau (indice 1) contient le nombre d'éléments significatifs. Les éléments significatifs sont placés juste après et sont disposés par ordre croissant.

  1. Écrire la procédure affiche(T:TAB) qui affiche tous les éléments significatifs.
  2. Écrire la fonction estVide(T:TAB):booléen qui retourne vrai si T est vide.
  3. Écrire la fonction estPlein(T:TAB):booléen qui retourne vrai si T est plein (N-1 éléments).
  4. Écrire la fonction indice(T:TAB, x:entier):entier qui utilise la recherche dichotomique.
  5. Écrire la procédure supprimeFin(variable T:TAB) qui supprime le dernier élément.
  6. Écrire la procédure ajouteFin(variable T:TAB, x:entier) qui ajoute x à la fin.
  7. Écrire la procédure decalage(variable T:TAB, i:entier, j:entier, GD:booléen).
  8. Écrire la procédure insere(variable T:TAB, x:entier).
  9. Écrire la procédure supprime(variable T:TAB, x:entier).
Exercice 41

Considérons une séquence non vide de bits (entiers valant 0 ou 1), par exemple :

[1,1,1,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1]

C'est une alternance de groupes de 1 consécutifs et de groupes de 0 consécutifs. Chacun de ces groupes peut être représenté par un couple (valeur binaire, nombre de répétitions).

Pour notre exemple, la séquence devient : [1,4,0,2,1,1,0,5,1,2,0,3,1,1,0,6,1,2]

Cette séquence peut être représentée sous forme matricielle.

  1. Écrire une procédure Saisie pour saisir la taille L et les éléments d'un tableau TSB.
  2. Écrire une procédure compactage1 qui construit une matrice M.
  3. Écrire une procédure compactage2 qui construit la forme compacte TFC.
  4. Écrire une procédure décompactage qui produit le tableau TSB initial.
Exercice 42

Écrire une procédure tasse(n:entier, var T:TAB) qui efface toutes les occurrences du chiffre 0 dans le tableau T et tasse les éléments restants sans utiliser de tableaux supplémentaires (on remplira la fin du tableau par des zéros).

Exemple :

T = [1, 0, 2, 5, 0, 0, 0, 8, 5, 0, 0, 4]

Le résultat :

T = [1, 2, 5, 8, 5, 4, 0, 0, 0, 0, 0, 0]

Exercice 43

Considérons un tableau de bits (entiers valant 0 ou 1), par exemple :

T = [1,1,1,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,1,1]

C'est une alternance de groupes de 1 consécutifs et de groupes de 0 consécutifs.

  1. Écrire une procédure pour saisir un entier N dans [1, Nmax].
  2. Écrire une procédure pour saisir un tableau T de taille N (chaque élément ∈ {0,1}).
  3. Écrire une fonction groupe_nulle_maxi qui retourne la longueur du plus long groupe nul.

Exemple : pour le tableau ci-dessus, la fonction doit retourner 6 (six 0 consécutifs).

Exercice 44

Le but du problème est d'appliquer des permutations sur les éléments d'un tableau T d'entiers afin de le trier. Soient deux tableaux T et P de dimension N. P est un tableau d'éléments distincts qui prend ses valeurs dans [1..N].

Exemple : T=[5, -2, 6, 9] et P=[3, 1, 4, 2]

Application : T[1]=T[P[1]]=T[3]=6, T[2]=T[1]=5, T[3]=T[4]=9, T[4]=T[2]=-2

Donc T=[6, 5, 9, -2].

  1. Écrire une fonction est_identite(N:ENTIER, P:TAB):BOOLEEN.
  2. Écrire une fonction nombre_inv(N:ENTIER, P:TAB):ENTIER qui calcule le nombre d'inversions.
  3. Écrire la procédure compose_perm qui calcule P_C[i] = P1[P2[i]].
  4. Écrire une procédure applique_perm.
  5. Écrire une fonction existe(T:TAB, i, x:ENTIER):BOOLEEN.
  6. Écrire une procédure perm_alea(N:ENTIER, variable P:TAB).
  7. Écrire une fonction est_trie(N:ENTIER, T:TAB):BOOLEEN.
  8. Écrire une procédure trier qui trie le tableau par permutations aléatoires.

Corrigés

Corrigé Exercice 1

Algorithme résolution de ax + b = 0 :

Python 
print("Résolution de ax + b = 0")
print("Donner la valeur des 2 réelles a et b")
a=float(input("a= "))
b=float(input("b= "))
if a==0:
    if b==0:
        print("Tout réel est solution")
    else:
        print("Pas de solution")
else:
    print("la solution est ",-b/a)

Algorithme résolution de ax² + bx + c = 0 :

  • Si a = 0, le problème revient à résoudre l'équation du premier degré bx + c = 0.
  • Si a ≠ 0, on raisonne selon la valeur du discriminant Δ = b² - 4ac.

Si Δ > 0 : deux solutions x1 = (-b+√Δ)/(2a) et x2 = (-b-√Δ)/(2a)

Si Δ = 0 : une racine double x1 = x2 = -b/(2a)

Si Δ < 0 : deux solutions complexes conjuguées

Python 
from math import *
print("Résolution de ax2 + bx + c = 0")
print("donner la valeur des 3 réelles a , b et c")
a=float(input("a= "))
b=float(input("b= "))
c=float(input("c= "))
if a==0:
    print("Résolution de l'équation bx + c = 0 voir question (a)")
else:
    DISC=b * b - 4 * a * c
    if (DISC > 0):
        x1=(-b + sqrt(DISC))/(2 * a)
        x2=(-b - sqrt(DISC))/(2 * a)
        print("Deux racines réelles distinctes :")
        print("x1=",x1, " x2=",x2)
    else:
        if (DISC == 0):
            x1=-b/(2 * a)
            x2=x1
            print("Une racine réelle double :")
            print("x1=",x1, " x2=",x2)
        else:
            print("Deux racines complexes")
            print("x1=",-b/(2*a),"+i",sqrt(abs(DISC))/(2*a))
            print("x2=",-b/(2*a),"+i",-sqrt(abs(DISC))/(2*a))
Corrigé Exercice 2
Python 
print("Donner le taux horaire T :")
T=float(input("T= "))
while T<=0:
    T=float(input("T= "))

NBH=float(input("NBH= "))
while NBH<=0:
    NBH=float(input("NBH= "))

if (NBH <= 39):
    S = NBH * T
elif (NBH <= 44):
    S = (39 + (NBH - 39) * 1.2) * T
elif (NBH <= 49):
    S = (45 + (NBH - 44) * 1.5) * T
else:
    S = (52.5 + (NBH - 49) * 1.8) * T

print("le salaire=",S)
Corrigé Exercice 3

Ici nous allons utiliser le formalisme : n! = ∏k=1n k = 1·2·...·n

Python 
print("Calcul de factorielle n :")
print("Donner un entier positif pour calculer n ! :")
n=int(input("n= "))
while n<0:
    print("Donner un entier positif pour calculer n ! :")
    n=float(input("n= "))

F = 1 # initialisation à un de F
for k in range(1,n+1):
    F = F * k

print(n,"!  =  ",F)
Corrigé Exercice 4
Python 
print("Donner un entier positif :")
n=int(input("n= "))

while n<0:
    print("Donner un entier positif :")
    n=float(input("n= "))

S = 0 #initialisation à zéro de S
for k in range(1,n+1):
    S = S + k * k/(k + 1)

print("Somme=",S)
Corrigé Exercice 5
Python 
import random
Nm = random.randint(1,100)
print("le nombre maximale de coups (Nbc) :")
Nbc=int(input("Nbc= "))
i = 1
while (True):
    K=int(input("Donner une estimation du nombre choisi par l'ordinateur : "))    
    if (K <Nm):
        print("Trop petit")
    elif (K >Nm):
        print("Trop grand")
    i = i + 1
    if (i > Nbc) or (K == Nm):
        break
if K == Nm:
    print("Gagné")
else:
    print("Perdu")
Corrigé Exercice 6
Python 
while True:
    print("Donner un entier positif N :")
    N=int(input("N= "))
    if N >= 0:
        break

N1 = N #copier N dans N1
IM = 0 #initialisation à zéro de IM
while N != 0:
    U = N % 10
    N = N // 10
    IM = 10 * IM + U
if (IM % N1)== 0: #test de divisibilité de IM par N1
    print(N1,"divise",IM)
else:
    print(N1,"ne divise pas ",IM)
Corrigé Exercice 7

Méthode 1 : Soustraction

Python 
print("Calcul du PGCD de 2 entiers A et B :")
while True:
    A=int(input("A= "))
    B=int(input("B= "))
    if (A >= 0) and (B >= 0):
        break
A1 = A #sauvegarde A dans A1 
B1 = B #sauvegarde B dans B1 
while (A * B != 0):
    if (A > B):
        A = A - B
    else:
        B = B - A
if (A == 0):
    print("PGCD(",A1,",",B1,")=",B)
else:
    print("PGCD(",A1,",",B1,")=",A)

Méthode 2 : Méthode binaire

Python 
print("Calcul du PGCD de 2 entiers A et B :")
while True:
    A=int(input("A= "))
    B=int(input("B= "))
    if (A >= 0) and (B >= 0):
        break
A1,B1,PGCD = A,B,1 
while (A*B) != 0:
    if (A % 2 +B % 2) == 0:
        PGCD = PGCD * 2
        A = A // 2
        B = B // 2
    if (A % 2 +B % 2) == 1:
        if (A % 2) == 0:
            A = A // 2
        else:
            B = B // 2
    if (A % 2 +B % 2) == 2:
        if (A > B):
            A = A - B
        else:
            B = B - A
if A == 0:
    print("PGCD(",A1,",",B1,")=",PGCD * B)
else:
    print("PGCD(",A1,",",B1,")=",PGCD * A)

Méthode 3 : Méthode euclidienne

Python 
print("Calcul du PGCD de 2 entiers A et B :")
while True:
    A=int(input("A= "))
    B=int(input("B= "))
    if (A >= 0) and (B >= 0):
        break

A1 = A #sauvegarde A dans A1 
B1 = B #sauvegarde B dans B1 
while B != 0:
    R = A % B
    A = B
    B = R

print("PGCD(",A1,",",B1,")=",A)
Corrigé Exercice 8
Python 
from math import *
print("Recherche des nombres parfaits < 10000 ")
for N in range(2,10000+1):
    Som = 1
    R = floor(sqrt(N))
    for p in range(2, R+1):
        if (N % p) == 0:
            Som = Som+ p + (N // p)
    if Som == N:
        print(N," est un nombre parfait")
Corrigé Exercice 9
Python 
from math import floor,sqrt
print("Vérification des nombres amis :")
while True:
    print("Donner 2 entiers positifs N et M avec N != M :")
    N=int(input("N= "))
    M=int(input("M= "))
    if (N >= 0) and (M >= 0) and N!=M:
        break

#calcul de la somme des diviseurs de N 
SomN = 1 
R = floor(sqrt(N))
for p in range(2, R+1):
    if (N % p) == 0:
        SomN = SomN + p + (N // p)
        
#calcul de la somme des diviseurs de M 
SomM = 1
R = floor(sqrt(M))
for p in range(2,R+1):
    if (M % p) == 0:
        SomM = SomM + p + (M // p) 

if (SomM == N) and (SomN == M):
    print(N,"et",M," sont 2 nombres amis")
else:
    print(N,"et",M," ne sont pas 2 nombres amis")
Corrigé Exercice 10

Version simple

Python 
print("Algorithme pour vérifier si un entier est premier:")
while (1):
    print("Donner un entier positif n:")
    n=int(input("n= "))
    if n>=0:
        break

if n==0 or n==1 :
    print(n,"n'est pas un nombre premier.")
else:
    i=2
    while (i<n) and (n%i!=0):
        i+=1

    if i==n:
        print(n," est premier ")
    else:
        print(n," n'est pas premier ")

Version optimisée

Python 
from math import sqrt
print("Algorithme pour vérifier si un entier est premier:")
while (1):
    n=int(input("Donner un entier positif n: "))
    if (n >= 0):
        break
if n==0 or n==1 :
    print(n,"n'est pas un nombre premier.")
else:    
    if n==2:
        print(n," est premier ")
    elif n%2==0:
        print(n," n'est pas premier ")
    else:
        i=3
        while (i < sqrt(n)) and (n %i != 0):
            i+=2
        if (i > sqrt(n)):
            print(n," est premier ")
        else:
            print(n," n'est pas premier ")
Corrigé Exercice 11
Python 
from math import *
def premier(a): # Définir une fonction pour vérifier la primalité
    for i in range(2,int(sqrt(a))+1):
        if a%i==0:
            return False
    return True


while 1: # Saisir un entier positif n
    try:
        n=int(input("n ="))
        if n>0:
            break
    except ValueError:
        print (" Veuillez saisir un entier")

fin = False
for i in range(int(sqrt(n)),1,-1): # Chercher le plus grand diviseur premier
    if n%i==0:
        fin =  premier(i)
        if fin:
            break
if fin:
    print("Le plus grand divisuer de ",n," = ",i)
else: # Lorsque n est premier
    print("Le plus grand divisuer de ",n," = ", n)
Corrigé Exercice 12
Python 
while 1: # Saisir un entier positif n
    try:
        n=int(input("n ="))
        if n>=2:
            break
    except ValueError:
        print (" Veuillez saisir un entier")
        
def pgcd(a, b): # Définir une fonction pour calculer le PGCD
    while b:
        a, b = b, a%b
    return a

s=1
for i in range(1,n+1):
    s=i*s/pgcd(s,i)

print (int(s))
Corrigé Exercice 13
Python 
def trip():
    for b in range(1,1000):
        for a in range (1,b):
            c=1000-a-b
            if c*c==a*a+b*b:
                 return (a*b*c)
print (trip())
Corrigé Exercice 14
Python 
from math import *
def premier(a): # Vérifier la primalité
    for i in range(2,int(sqrt(a))+1):
        if a%i==0:
            return False
    return True
while 1: # Saisir un entier positif n
    try:
        n=int(input("n ="))
        if n>0:
            break
    except ValueError:
        print (" Veuillez saisir un entier")
s=2
for i in range (3,n*10**6+1,2): # Les nombres premiers sont tous impairs sauf 2
    if premier(i):
        s+=i
print(s)
Corrigé Exercice 15
Python 
eps = 10**-6
U = 1
while (1):
    V=U
    U=1/2 * (U + 2/U )
    if abs(U - V ) < eps:
        break
print("Une valeur approchée de racine carré de 2 =",U )
Corrigé Exercice 16
Python 
print("Calcul de la racine carrée d'un réel>0")
eps = 10**-6
while (1):
    A=float(input("A = "))
    if A>0:
        break
U = 1
while (1):
    V=U
    U=1/2 * (U + A/U )
    if abs(U - V ) < eps:
        break
print("Une valeur approchée de racine carré de", A," =",U )
Corrigé Exercice 17

Ici nous allons ajouter une variable pour calculer 𝒰kn-1 :

Python 
print("Programme de calcul de la racine nieme d'un réel:")
while 1:
    print("Donner un réel x > 0:")
    x=float(input("x = "))
    if x>0:
        break

while 1:
    print("donner la précision de calcul eps :")
    eps=float(input("eps = "))
    if (eps > 0) and (eps < 1):
        break
while 1:
    print("Donner l'ordre de la racine n > 1:")
    n=int(input("n = "))
    if (n > 1):
        break
U = 1
ERR = 1
while ERR >= eps:
    Up = 1
    for i in range(1,n):
        Up*=U
    V = U
    U = ((n - 1) * U + x/Up)/n
    ERR = abs((U - V )/V)
print("La racine ",n,"ieme(",x,")=",U ," à ", eps, "près")
Corrigé Exercice 18
Python 
from math import sqrt
print("Programme pour calculer une valeur approchée de Pi")
eps = 10**-6
a,b = 1,1/sqrt(2)
Puiss,som,U = 1,0,4
while 1:
    aa = a
    a = (a + b)/2
    b = sqrt(aa * b)
    V = U
    Puiss = Puiss * 2
    som = som + Puiss * (a * a - b * b)
    U = 4 * a * a/(1 - 2 * som)
    if abs(U - V ) < eps:
        break
print("Une valeur approchée de pi =",U )
Corrigé Exercice 19
Python 
print("Calcul d'une valeur approchée de Pi avec les fractions continues")
while 1:
    print("Donner un nombre entier impair")
    n=int(input("n = "))
    if n >= 1 and n % 2 == 1:
        break

U = n * n/2
for i in range(n-2,-1,-2):
    U = i * i/(2 + U )

print("Une valeur approchée de Pi=",4/(1 + U ))
Corrigé Exercice 20
Python 
print("Calcul de Pi avec les fractions continues")
while 1:
    print("Donner un nombre entier")
    n=int(input("n = "))
    if n >= 1:
        break

U = n * n/(2 * n + 1)
for i in range( n - 1 ,0,-1):
    U = i * i/(2 * i + 1 + U )
print("Une valeur approchée de Pi=",4/(1 + U ))
Corrigé Exercice 21
Python 
from math import sqrt
eps=10**-6
U = 1/sqrt(2); p = 2/U # exécution séquentielle
while 1:
    q,U = p,sqrt(1/2 + 1/2 * U )
    p = p * 1/U
    if abs(p - q) < eps: break
print("Une valeur approchée de Pi=",p)
Corrigé Exercice 22
Python 
from math import sqrt
print("Calcul de Pi")
eps=10**-6
U,P = sqrt(2),2
V = P * sqrt(2)
while 1:
    W = V
    P = P * 2
    V = P * sqrt (2 - U )
    U = sqrt (2 + U )
    if abs(V - W ) < eps:
        break
print("Une valeur approchée de racine carré de Pi=",V)
Corrigé Exercice 23
Python 
print("Calcul des termes d'une suite")
eps = 10**-4
n,P = 1,2
print(P )
while 1:
    n = n + 2
    Q = P
    P = P * (n - 1)/n * (n + 1)/n
    print(P )
    if (abs(P - Q) < eps):
        break
Corrigé Exercice 24

On a besoin de 3 variables A, B et C pour stocker respectivement les termes 𝒰n-2, 𝒰n-1 et 𝒰n.

Python 
print("Calcul du nombre d'Or")
eps = 10**-10
A = 1
B = 1
V = B/A

while 1:
    C = A + B
    A = B
    B = C
    W = V
    V = B/A
    if abs((V - W )/W ) < eps:
        break
print ("La valeur approchée du nombre d'or est", V )
#Résultat:
#La valeur approchée du nombre d'or est 1.6180339887802426
Corrigé Exercice 25

a) Suite (an)

Python 
print("Calcul du nombre d'Or (an)")
eps = 10**-6
a = 1
i = 1
while 1:
    b = a
    a = 1 + 1/a
    i = i + 1
    if abs(b - a) < eps:
        break

print("Une valeur approchée du nombre d'or est=",a)
print("La précision est atteinte pour le",i,"ème terme")
#Résultat:
#Une valeur approchée du nombre d'or est= 1.618033813400125
#La précision est atteinte pour le 17 ème terme

b) Suite (bn)

Python 
from math import sqrt
print("Calcul du nombre d'Or (bn)")
eps = 10**-6
b = 1
i = 1
while 1:
    a = b
    b = sqrt(b + 1)
    i = i + 1
    if abs(b - a) < eps:
        break

print("Une valeur approchée du nombre d'or est=",b)
print("La précision est atteinte pour le",i,"ème terme")
#Résultat:
#Une valeur approchée du nombre d'or est= 1.618033829661219
#La précision est atteinte pour le 14 ème terme

c) Suite (cn)

Python 
from math import sqrt
print("Calcul du nombre d'Or (cn)")
eps = 10**-6
c = 1
i = 1
while 1:
    a = c
    c = (c * c + 1)/(2 * c - 1)
    i = i + 1
    if  abs(c - a) < eps:
        break

print("Une valeur approchée du nombre d'or est=",c)
print("La précision est atteinte pour le",i,"ème terme ")

#Résultat:
#Une valeur approchée du nombre d'or est= 1.618033988749989
#La précision est atteinte pour le 6 ème terme
Corrigé Exercice 26
Python 
from math import sqrt
print("Calcul de Pi ( formule de Brent-Salamin")
eps = 10**-6
A0,B0,C0 = 1,sqrt(1/2),1/4
R = 1
while 1:
    d0 = (A0 + B0)**2/(4 * C0)
    A = (A0 + B0)/2
    B = sqrt(A0 * B0)
    C = C0 - R * ((A0 - B0)/2)**2
    R = R * 2
    A0,B0,C0 = A, B, C
    d = (A0 + B0)**2/(4 * C0)
    err = abs(d - d0)
    if err < eps:
        break
print("Une valeur approchée de pi=",d)
#Résultat:
#Une valeur approchée de pi= 3.141592653589794
Corrigé Exercice 27

Pour ce style d'exercice, il ne faut jamais se lancer dans le calcul de puissances et de la factorielle, chercher une récurrence entre deux termes successifs. On a :

Tk = xk/k! = (xk-1/(k-1)!) · (x/k) = Tk-1 · (x/k)

Donc T0 = 1 et Tk = Tk-1 · (x/k).

Python 
print("Calcul approchée de exp(x)")
eps = 10**-8
print("Donner un réel x:")
x=float(input("x = "))
k = 0
S = 1
T = 1
while abs(T ) >= eps:
    k +=1
    T *= x/k
    S += T
print("EXP(",x,")=",S ," à ", eps, "près")
#Résultat:
#Donner un réel x:
#x = 1
#EXP( 1.0 )= 2.7182818282861687  à  1e-08 près
Corrigé Exercice 28
Python 
print("Calcul de (1+x)**a")
eps = 10**-6
while 1:
    print("donner un réel ")
    x=float(input(" x = " ))
    if (x > -1) and (x < 1):
        break
print ("donner la valeur de a ")
a=float(input("a = "))
S = i = t = 1
while 1:
    t *= (a - i + 1) * x/i
    S += t
    i += 1
    if abs(t)<= eps:
        break
print ("La valeur approchée de (1 + x)a est " , S)
Corrigé Exercice 29
Python 
print("Calcul d'une valeur approchée de ln(x)")
eps = 10**-6
while 1:
    print (" donner un réel ")
    x=float(input("x = "))
    if (x > -1) and (x < 1):
        break

i = 1
S = x
t = x
while 1:
    i += 1
    t *= (-1)* x/i
    S += t
    if abs(t) <= eps:
        break
print ("La valeur approchée de ln(1 + x) est " , S )
Corrigé Exercice 30
Python 
print("Calcul d'une valeur approchée de sinh(x)")
eps = 10**-6
while 1:
    print (" donner un réel ")
    x=float(input("x = "))
    if (x > -1) and (x < 1):
        break

i = 1
S = x
t = x
while 1:
    i += 2
    t *= x*x/(i*(i-1))
    S += t
    if abs(t) <= eps:
        break
print ("La valeur approchée de sinh(x) est " , S )
Corrigé Exercice 31
Python 
print("Calcul approché de 1/x")
eps = 10**-6
while 1:
    X= float(input("X = "))
    if X > 0 and X < 2:
        break
a = 1
c = 1 - X
while 1:
    b = a
    a = a * (1 + c)
    c = c * c
    if abs(a - b) < eps:
        break

print ("La valeur approchée de 1/",X, " à ", eps, "près est =", a)
Corrigé Exercice 32
Python 
print("Calcul approché de Pi")
a = 1.5574
non_nul = 0
p = 2
S = 0
while 1:
    a = 2 * a/(1 - a * a)
    p *= 2
    if a < 0:
        non_nul += 1
        S += 1/p
    if non_nul == 100:
        break

print ("La valeur approchée de Pi après le calcul de la somme des 100 premiers termes non nuls de la série =", 1/S)
#Résultat:
#La valeur approchée de Pi après le calcul de la somme des 100 premiers termes non nuls de la série = 3.1415997380229306
Corrigé Exercice 33
Python 
print("Calcul approché de 1/sqrt(1+x)")
eps = 10**-6
while 1:
    X = float(input(" X = "))
    if abs(X) < 1:
        break
U = 1
S = U
signe = 1
n = 1
while 1:
    U = (2 * n - 1) * X/(2 * n) * U
    signe *= (-1)
    S += signe * U
    n += 1
    if abs(U ) < eps:
        break
print ("Résultat =", S)
Corrigé Exercice 34

1) Dichotomie

Python 
eps = 10**-6
a = 0
b = 2
c = (a + b)/2

while abs(c * c - 2) >= eps:
    if c * c > 2:
        b = (a + b)/2
    else:
        a = (a + b)/2
    c = (a + b)/2

print("Une valeur approchée de racine(2) en utilisant la méthode de dichotomie =",c," à ",eps,"près")

2) Méthode de Newton

Python 
eps = 10**-6
x = 1
while 1:
    y = x
    x = 1/2 * (x + 2/x)
    if (abs(y - x) < eps):
        break
    
print("Une valeur approchée de racine(2) en utilisant la méthode de Newton =",x," à ",eps,"près")

3) Fractions continues

Python 
eps = 10**-6
U = 2
while 1:
    V = U
    U = 2 + 1/U
    if (abs(U - V) < eps):
        break

print("Une valeur approchée de racine(2) en utilisant la méthode des fractions continues =",U - 1," à ",eps,"près")
Corrigé Exercice 35
Python 
u0=1
u1=2
s=0
while u1<4000000 :
    if u1%2==0:
        s+=u1
    u0,u1=u1,u0+u1
    
print(s)