Scribd Logo
Importer

Bienvenue sur Scribd !

  • 73 vues

    TP-Info 9

    Transféré par

    samim1971
    Le document présente trois algorithmes : le calcul de la factorielle d'un nombre, le calcul du plus grand commun diviseur de deux nombres et la recherche du maximum dans un tableau. Pour chaque algorithme, le document demande de prouver sa terminaison et de montrer qu'il fonctionne correctement.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    TP-Info 9

    Transféré par

    samim1971
    73 vues2 pages
    Le document présente trois algorithmes : le calcul de la factorielle d'un nombre, le calcul du plus grand commun diviseur de deux nombres et la recherche du maximum dans un tableau. Pour chaque algorithme, le document demande de prouver sa terminaison et de montrer qu'il fonctionne correctement.

    Titre original

    TP-Info_9

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Le document présente trois algorithmes : le calcul de la factorielle d'un nombre, le calcul du plus grand commun diviseur de deux nombres et la recherche du maximum dans un tableau. Pour chaque algorithme, le document demande de prouver sa terminaison et de montrer qu'il fonctionne correctement.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    73 vues2 pages

    TP-Info 9

    Transféré par

    samim1971
    Le document présente trois algorithmes : le calcul de la factorielle d'un nombre, le calcul du plus grand commun diviseur de deux nombres et la recherche du maximum dans un tableau. Pour chaque algorithme, le document demande de prouver sa terminaison et de montrer qu'il fonctionne correctement.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 2

    TP Info 9 – Preuves d’algorithmes

    D.Malka – MPSI 2014-2015 – Lycée Saint-Exupéry

    I1 – Factorielle (encore !) Algorithme 2 : Calcul du PGCD de a et b


    L’algorithme suivant calcule la factorielle de l’entier naturelle n : Entrées : entier naturel a, entier naturel b<a
    Sorties : entier naturel dividende
    1 dividende=a
    Algorithme 1 : Calcul de n !
    2 diviseur=b
    Entrées : entier naturel n
    3 r=1
    Sorties : entier naturel fact
    4 tant que r 6= 0 faire
    1 c=0
    5 r=dividende/diviseur
    2 fact=1
    6 dividende=diviseur
    3 tant que c<n faire
    7 diviseur=r
    4 c=c+1
    8 retourner dividende
    5 fact=fact*c
    6 retourner fact

    I3 – Etude d’un algorithme sur un tableau


    1. Montrer que l’algorithme termine.
    2. En recherchant un invariant de boucle, montrer que l’algorithme donne le Algorithme 3 : Que fait l’algorithme ?
    résultat attendu. Entrées : tableau de nombres réels de taille N
    Sorties : maximum m du tableau
    I2 – Algorithme d’Euclide 1 m=tableau[0]
    2 pour i de 1 à longueur(tableau)-1 faire
    L’algorithme d’Euclide calcule le PGCD de deux entiers naturels a et b.
    3 si tableau[i]>m alors
    1. Montrer que l’algorithme termine. 4 m=tableau[i]
    2. Montrer que la proposition : 5 retourner m

    L’ensemble des diviseurs communs à dividende et diviseur est


    l’ensemble des diviseurs communs à a et b 1. Que fait l’algorithme 3 ?
    est un invariant de boucle. 2. Prouver sa terminaison.
    3. En déduire que le dernier reste non nul est bien le pgcd de a et b. 3. Montrer que cet algorithme fonctionne.

    http://www.mpsi-lycee-saint-exupery.fr 1
    MPSI – 2014-2015 – Lycée Saint-Exupéry D.Malka TP Info 9 – Preuves d’algorithmes

    4. Modifier l’algorithme pour qu’il renvoie aussi la position du maximum du


    tableau.
    5. Implémenter cet algorithme en Python et le tester pour un jeu variables
    d’entrée.

    http://www.mpsi-lycee-saint-exupery.fr 2

    Vous aimerez peut-être aussi