id: 33-509-synthese-algorithmes-classiques-tableaux slug: 33-509-synthese-algorithmes-classiques-tableaux titre: 'Synthèse : algorithmes classiques sur les tableaux et les nombres' chapitre: 4 chapitre_titre: 'Algorithmique avancée : tableaux et boucles' lecon: 1 niveau: 4eme-sci ordre: 40 prerequis: [] duree_estimee_min: 45 mots_cles:

• boucle pour
• boucle repeter
• tableau
• recherche
• occurrence
• nombre premier
• palindrome
• pgcd
• ppcm
• min max langages:
• analyse objectifs:
• Convertir une boucle Pour en boucle Répéter
• Écrire les algorithmes classiques de remplissage et d'affichage d'un tableau
• Mettre en œuvre la recherche d'un élément, le calcul d'occurrences et de sommes
• Tester si un nombre est premier et si une chaîne est un palindrome
• Calculer le PGCD et le PPCM de deux entiers status: published source_pdf: 33_509.pdf source_pages:
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10 kind: recueil

Synthèse : algorithmes classiques sur les tableaux et les nombres

Cette leçon récapitule les algorithmes types à connaître pour les épreuves de bac scientifique : conversions de boucles, traitements sur un tableau, propriétés sur les entiers (premier, PGCD, PPCM) et sur les chaînes (palindrome).

I. Convertir une boucle Pour en boucle Répéter

Toute boucle Pour (à nombre d'itérations connu) peut être réécrite à l'aide d'une boucle Répéter (à condition d'arrêt). Le principe est de simuler manuellement le compteur, son incrémentation et la condition de sortie.

Pour i de 1 à n faire
    // Traitement
Fin Pour

Pour i de 1 à n faire
    // Traitement
Fin Pour

i ← 0
Répéter
    i ← i + 1
    // Traitement
Jusqu'à (i = n)

II. Remplissage d'un tableau

1) Sans contrôle de saisie

On lit n valeurs sans aucune contrainte sur les données saisies.

Pour i de 1 à n faire
    écrire("T[", i, "] = ")
    lire(T[i])
Fin Pour

2) Avec contrôle de saisie (tableau d'entiers positifs)

On force l'utilisateur à ressaisir tant que la valeur ne respecte pas la contrainte (ici : T[i] ≥ 0).

Pour i de 1 à n faire
    Répéter
        écrire("T[", i, "] = ")
        lire(T[i])
    Jusqu'à (T[i] ≥ 0)
Fin Pour

III. Affichage d'un tableau

1) Affichage simple (sans condition)

Pour i de 1 à n faire
    écrire(T[i], " | ")
Fin Pour

2) Affichage conditionnel (uniquement les entiers positifs)

Pour i de 1 à n faire
    Si (T[i] ≥ 0) alors
        écrire(T[i], " | ")
    Fin Si
Fin Pour

IV. Recherche d'un entier X dans un tableau T

Hypothèse : X est un entier déjà saisi par l'utilisateur.

Pour chercher un élément dans un tableau on utilise la boucle Répéter.

i ← 0
trouve ← Faux
Répéter
    i ← i + 1
    Si (T[i] = X) alors
        trouve ← Vrai
    Fin Si
Jusqu'à ((trouve = Vrai) ou (i = n))

V. Détermination du nombre d'occurrences de X dans T

On compte ici combien de fois l'entier X apparaît dans T. Comme on doit parcourir tout le tableau, on utilise une boucle Pour.

nbocc ← 0
Pour i de 1 à n faire
    Si (T[i] = X) alors
        nbocc ← nbocc + 1
    Fin Si
Fin Pour

VI. Nombre premier

Objectif : déterminer si un entier X (donné) est premier ou non.

L'idée : tester les diviseurs possibles à partir de 2, et s'arrêter dès qu'on en trouve un (ou dès qu'on dépasse X div 2, puisqu'au-delà aucun diviseur n'est possible).

premier ← Vrai
i ← 2
Répéter
    Si ((X mod i = 0) et (i ≤ X div 2)) alors
        premier ← Faux
    Fin Si
    i ← i + 1
Jusqu'à ((premier = Faux) ou (i > X div 2))

VII. Calcul d'une somme

1) Somme des éléments d'un tableau

S ← 0
Pour i de 1 à n faire
    S ← S + T[i]
Fin Pour

2) Somme des entiers positifs du tableau T

S ← 0
Pour i de 1 à n faire
    Si (T[i] > 0) alors
        S ← S + T[i]
    Fin Si
Fin Pour

VIII. Vérifier si une chaîne est un palindrome

Principe : comparer le i-ème caractère avec le (long(ch) - i + 1)-ème caractère. Dès qu'une comparaison échoue, la chaîne n'est pas un palindrome. Il suffit de tester jusqu'au milieu de la chaîne (long(ch) div 2).

i ← 0
Répéter
    i ← i + 1
    verif ← (ch[i] = ch[long(ch) - i + 1])
Jusqu'à ((verif = Faux) ou (i = long(ch) div 2))

IX. Maximum et minimum d'un tableau T

On initialise min (ou max) avec la première case du tableau, puis on parcourt les suivantes.

min ← T[1]      // [ max ← T[1] ]
Pour i de 2 à n faire
    Si (T[i] < min) alors        // ( T[i] > max ) pour le maximum
        min ← T[i]
    Fin Si
Fin Pour

X. Calcul de la puissance Xⁿ

On accumule un produit n fois.

p ← 1
Pour i de 1 à n faire
    p ← p * X
Fin Pour

XI. PPCM et PGCD

1) PPCM (Plus Petit Commun Multiple)

On cherche le plus petit entier a × i divisible par b.

i ← 0
Répéter
    i ← i + 1
Jusqu'à ((a * i) mod b = 0)

écrire("PPCM de a et b est : ", a * i)

2) PGCD (méthode d'Euclide)

L'algorithme d'Euclide utilise les divisions successives : à chaque étape, on remplace (a, b) par (b, a mod b).

Répéter
    r ← a mod b
    a ← b
    b ← r
Jusqu'à (b = 0)

écrire("Le PGCD de a et b est = ", a)