algorithmique_intro

Notebook

Introduction à l'algorithmique¶

Definition¶

L'algorithmique est l'étude et la production de règles et techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est-à-dire de processus systématiques de résolution d'un problème permettant de décrire précisément des étapes pour résoudre un problème.

En d'autre termes, un algorithme definit une méthode qui permet d'obtenir d'une machine qu'elle éxécute une tache de manière automatique, reproductible et fiable.

Exemples de tâches que l'on peut résoudre avec des algorithmes

Calculer la valeur de la TVA en fonction d'un prix hors-taxes.
Calculer la valeur d'une fonction affine.
Trier un ensemble de valeurs.
Rechercher une valeur dans un ensemble de valeurs.
...
Résoudre une équation.
Déterminer la meilleure trajectoire pour un robot.
...
Fournir une page web à un navigateur.
Diriger un paquet de données ou une page web sur internet (on parle de routage).
Calculer les paramètres d'un moteur pour obtenir une trajectoire acceptable pour aller de la Terre à la Lune.
Faire fonctionner un ordinateur.

Remarques¶

Un problème complexe peut toujours être décomposé en plusieurs problèmes plus simples.

Un algorithme prend des données en entrées. Il produit des résultats en sortie, en fonctions de conditions et à l'aide de moyens

Algorithme

Example¶

Avec AlgoBox, calculer la tva et le prix ttc à partir d'un prix hors taxe. Le taux de tva est 20%.

FONCTIONS_UTILISEES
VARIABLES
  prix_ht EST_DU_TYPE NOMBRE
  tva EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  LIRE prix_ht
  tva PREND_LA_VALEUR prix_ht * 0.20
  AFFICHER "le prix ttc est "
  AFFICHERCALCUL* prix_ht + tva
  AFFICHER "prix ht :"
  AFFICHER* prix_ht
  AFFICHER "tva :"
  AFFICHER* tva
FIN_ALGORITHME

Representation des données numériques: Les variables NOMBRE¶

Déclaration d'une variable¶

VARIABLES
  a EST_DU_TYPE NOMBRE

Affectation d'une variable¶

a PREND_LA_VALEUR 5
a PREND_LA_VALEUR 25000
a PREND_LA_VALEUR b 
LIRE a

Affichage d'une variable¶

// sans retour a la ligne
AFFICHER a

// pour obtenir un retour a la ligne on ajoute une *
AFFICHER* a

Operations mathematiques¶

a PREND_LA_VALEUR 5 + 2
a PREND_LA_VALEUR 6 / 3
a PREND_LA_VALEUR 8 * 3
a PREND_LA_VALEUR 8 - 6
a PREND_LA_VALEUR b + 5
a PREND_LA_VALEUR a + 1
a PREND_LA_VALEUR (a + (b / 2) * c) / (d + 4) // attention a la priorite des opérateurs mathématique, dans le doute utiliser des ()

Algorithmique : Les conditions¶

Les conditions permettent d'éxécuter des instructions en fonction de la valeur d'une variable

SI (condition) ALORS
    DEBUT_SI
    ...
    ...
    FIN_SI
    SINON
        DEBUT_SINON
        ...
        ...
        FIN_SINON

Si la condition est vraie, on execute les instructions dans le bloc compris entre DEBUT_SI et FIN_SI. Si la condition est fausse on execute les instructions dans le bloc compris entre DEBUT_SINON et FIN_SINON

Example¶

A partir d'une valeur entrée au clavier, afficher sa valeur absolue

FONCTIONS_UTILISEES
VARIABLES
  a EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  LIRE a
  SI (a > 0) ALORS
    DEBUT_SI
    AFFICHER* a
    FIN_SI
    SINON
      DEBUT_SINON
      AFFICHERCALCUL* -a
      FIN_SINON

FIN_ALGORITHME

Ecriture de condition¶

Dans Algobox les conditions s'écrivent de la manière suivante :

a >  b    // la valeur de a est supérieure à la valeur de b
a >= b    // la valeur de a est superieure ou égale à la valeur de b
a <  b    // La valeur de a est inférieure à la valeur de b
a <= b    // la valeur de a est inférieure ou égale à la valeur de b
a == b    // la valeur de a est égale à la valeur de b

Les conditions peuvent être combinées avec les mots clefs OU et ET

a > b ET b > c    // vrai si les deux conditions sont vraies 
a > b OU b > c    // vrai si une des deux conditions est vraie

Exercice¶

Avec Algobox, on cherche à déterminer le salaire net d'un Commercial. Le salaire brut du commercial est determiné par une partie fixe + une prime égale à 5% de son chiffre d'affaire. Le salaire Net est le résultat du salaire brut, moins les cotisations sociales. Les cotisations sociales sont les suivantes :

Assurance chomage : 5% du salaire du brut.
Assurance maladie : 3% pour la part du salaire brut inferieure au plafond de la securité sociale, 4% au dela. Le plafond de la securite sociale est de 3000 euros.
Assurance retraite : 11% pour la part du salaire brut inferieure au plafond de la securité sociale, 12% pour la part entre 1 fois et 2 fois le plafond de la securite sociale, 14% au dela.

Réaliser un algorithme qui :

Demande à l'utilisateur de renseigner le salaire fixe ainsi que le chiffre d'affaire.
Calcule le salaire brut.
Calcule les cotisations.
Affiche le salaire brut, les cotisations et le salaire net.

Tester l'algorithme avec les valeurs suivantes :

Salaire fixe	Chiffre d'affaire
1200	2000
2900	2200
2900	10000
3600	60000
9000	90000

Solution proposée¶

FONCTIONS_UTILISEES
VARIABLES
  salaire_fixe EST_DU_TYPE NOMBRE
  chiffre_affaire EST_DU_TYPE NOMBRE
  salaire_brut EST_DU_TYPE NOMBRE
  assurance_chomage EST_DU_TYPE NOMBRE
  plafond_secu EST_DU_TYPE NOMBRE
  assurance_maladie EST_DU_TYPE NOMBRE
  assurance_veillesse EST_DU_TYPE NOMBRE
  part EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  plafond_secu PREND_LA_VALEUR 3000
  LIRE salaire_fixe
  LIRE chiffre_affaire
  //calcul salaire brut
  salaire_brut PREND_LA_VALEUR salaire_fixe + (chiffre_affaire * 0.05)
  //calcul assurance chomage
  assurance_chomage PREND_LA_VALEUR salaire_brut * 0.05
  //calcul assurance maladie
  SI (salaire_brut > plafond_secu) ALORS
    DEBUT_SI
    assurance_maladie PREND_LA_VALEUR (plafond_secu * 0.03) + ((salaire_brut - plafond_secu) * 0.04)
    FIN_SI
    SINON
      DEBUT_SINON
      assurance_maladie PREND_LA_VALEUR salaire_brut * 0.03
      FIN_SINON
  //calcul assurance vieillesse
  assurance_veillesse PREND_LA_VALEUR 0
  SI (salaire_brut > 2 * plafond_secu) ALORS
    DEBUT_SI
    assurance_veillesse PREND_LA_VALEUR (salaire_brut - (2 * plafond_secu)) * 0.14
    FIN_SI
  SI (salaire_brut > plafond_secu) ALORS
    DEBUT_SI
    part PREND_LA_VALEUR salaire_brut - plafond_secu
    SI (part > plafond_secu) ALORS
      DEBUT_SI
      part PREND_LA_VALEUR plafond_secu
      FIN_SI
    assurance_veillesse PREND_LA_VALEUR assurance_veillesse + (part * 0.12)
    FIN_SI
  part PREND_LA_VALEUR salaire_brut
  SI (part > plafond_secu) ALORS
    DEBUT_SI
    part PREND_LA_VALEUR plafond_secu
    FIN_SI
  assurance_veillesse PREND_LA_VALEUR assurance_veillesse + (part * 0.11)
  //affichage
  AFFICHER "Salaire brut "
  AFFICHER* salaire_brut
  AFFICHER "Cot chomage "
  AFFICHER* assurance_chomage
  AFFICHER "cot maladie "
  AFFICHER* assurance_maladie
  AFFICHER "cot vieillesse "
  AFFICHER* assurance_veillesse
  AFFICHER "salaire net "
  AFFICHERCALCUL* salaire_brut - assurance_chomage -assurance_maladie - assurance_veillesse
FIN_ALGORITHME

Representation des données "texte": Les variables CHAINE¶

Les variables de types CHAINE contiennent une liste de caracteres, on parle de chaine de caracteres.

Déclaration d'une variable¶

VARIABLES
  a EST_DU_TYPE CHAINE

Affectation d'une variable¶

a PREND_LA_VALEUR "toto"
a PREND_LA_VALEUR "machin"
a PREND_LA_VALEUR b 
LIRE a

Affichage d'une variable¶

// sans retour a la ligne
AFFICHER a

// pour obtenir un retour a la ligne on ajoute une *
AFFICHER* a

Operations sur les chaines¶

a PREND_LA_VALEUR a + " est à la plage" // concatenation de chaines de caracteres

conditions sur les chaines¶

a == "s"
a > "b"
a >= "bcde"
a < "bcde"
a <= "bcde"

Algorithmique : Boucle TANT_QUE¶

Lors de la réalisation d'un algorithme, il est parfois interessant d'éxécuter les mêmes instructions plusieurs fois. Avec Algobox on utilise l'instruction TANT_QUE

TANT_QUE (expression)
    DEBUT_TANT_QUE
    ...
    FIN_TANT_QUE

si l'expression est vraie on execute les instructions entre DEBUT_TANT_QUE et FIN_TANT_QUE. Apres FIN_TANT_QUE on revient sur l'instruction TANT_QUE et on teste de nouveau l'expression pour déterminer si on éxécute le bloc d'instruction encore une fois. Quand l'expression devient fausse on éxécute l'instruction qui suit TANT_QUE .

Example¶

FONCTIONS_UTILISEES
VARIABLES
  i EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  i PREND_LA_VALEUR 0
  TANT_QUE (i < 10) FAIRE
    DEBUT_TANT_QUE
    AFFICHER* i
    i PREND_LA_VALEUR i + 1
    FIN_TANT_QUE
  AFFICHER "la valeur de i est :"
  AFFICHER* i
FIN_ALGORITHME

Exercice¶

Sur une planete quelconque de gravite g on cherche à déterminer en combien de temps (à la seconde près) un objet situé à une certaine altitude tombe au sol.
Rappel de physique, à chaque seconde :

La vitesse de chute de l'objet augmente de la gravite (m/s-2)
L'altitude de l'objet diminue de la vitesse de chute (m/s)

L'algorithme demandera :

L'altitude de l'objet
La gravité

L'algorithme affichera :

L'altitude théorique de l'objet à l'arrivé
La vitesse de chute en m/s
Le temps en secondes mis par l'objet pour arriver au sol (altitude 0)

On utilisera la fonctionnalite "dessiner dans un repere" d'Algobox pour afficher les altitudes successives de l'objet en fonction du temps.

Solution proposée¶

FONCTIONS_UTILISEES
VARIABLES
  altitude EST_DU_TYPE NOMBRE
  vitesse_chute EST_DU_TYPE NOMBRE
  gravite EST_DU_TYPE NOMBRE
  temps EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  LIRE altitude
  LIRE gravite
  vitesse_chute PREND_LA_VALEUR 0
  temps PREND_LA_VALEUR 0
  TANT_QUE (altitude >= 0) FAIRE
    DEBUT_TANT_QUE
    vitesse_chute PREND_LA_VALEUR vitesse_chute + gravite
    altitude PREND_LA_VALEUR altitude - vitesse_chute
    temps PREND_LA_VALEUR temps + 1
    TRACER_POINT_Rouge (temps,altitude)
    TRACER_POINT_Bleu (temps,vitesse_chute)

    FIN_TANT_QUE
  AFFICHER* altitude
  AFFICHER* vitesse_chute
  AFFICHER* temps
FIN_ALGORITHME

Jeu :-)¶

A partir de l'exercice précédent, on veut proposer un simulateur d'aterrissage.
Le joueur pilote un module d'aterrissage et démarre à 1000 mètres d'altitude.
La masse a vide du module est 20 tonnes.
La quantite de carburant disponible au depart est de 200 tonnes.
La gravité sur la planête Schtroumpf est de 5.
Quand on brule du carburant, la vitesse de chute diminue de (la quantite de carburant brulé * 200) / la masse totale du module.
Le joueur gagne si il arrive au sol avec une vitesse inférieure à 20 m/s.

A chaque tour, l'algorithme demande au joueur combien de carburant il veut bruler. L'algorithme verifiera que la quantité de carburant brulée est positive et que la quantité de carburant est bien disponible dans le reservoir. On tiendra compte également de l'évolution de la masse du module au cours du temps.

Solution proposée¶

FONCTIONS_UTILISEES
VARIABLES
  altitude EST_DU_TYPE NOMBRE
  vitesse_chute EST_DU_TYPE NOMBRE
  gravite EST_DU_TYPE NOMBRE
  temps EST_DU_TYPE NOMBRE
  masse EST_DU_TYPE NOMBRE
  carburant EST_DU_TYPE NOMBRE
  carburant_brule EST_DU_TYPE NOMBRE
  carburant_nouveau EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  EFFACER_GRAPHIQUE
  altitude PREND_LA_VALEUR 1000
  gravite PREND_LA_VALEUR 5
  masse PREND_LA_VALEUR 20
  carburant PREND_LA_VALEUR 200
  vitesse_chute PREND_LA_VALEUR 0
  temps PREND_LA_VALEUR 0
  TANT_QUE (altitude >= 0) FAIRE
    DEBUT_TANT_QUE
    temps PREND_LA_VALEUR temps + 1
    AFFICHER "temps "
    AFFICHER* temps
    AFFICHER "altitude "
    AFFICHER* altitude
    AFFICHER "vitesse "
    AFFICHER* vitesse_chute
    AFFICHER "carburant restant "
    AFFICHER* carburant
    carburant_nouveau PREND_LA_VALEUR -1
    TANT_QUE (carburant_nouveau < 0 OU carburant_brule < 0) FAIRE
      DEBUT_TANT_QUE
      LIRE carburant_brule
      carburant_nouveau PREND_LA_VALEUR carburant - carburant_brule
      FIN_TANT_QUE
    carburant PREND_LA_VALEUR carburant_nouveau
    vitesse_chute PREND_LA_VALEUR vitesse_chute - ((carburant_brule * 200) / (masse + carburant))
    vitesse_chute PREND_LA_VALEUR vitesse_chute + gravite
    altitude PREND_LA_VALEUR altitude - vitesse_chute
    TRACER_POINT_Rouge (temps,altitude)
    TRACER_POINT_Bleu (temps,vitesse_chute)
    FIN_TANT_QUE
  AFFICHER* altitude
  AFFICHER* vitesse_chute
  AFFICHER* temps
  SI (vitesse_chute < 20) ALORS
    DEBUT_SI
    AFFICHER* "gagné"
    FIN_SI
    SINON
      DEBUT_SINON
      AFFICHER* "perdu"
      FIN_SINON

FIN_ALGORITHME

Utilisation de fonction¶

Quelque soit le système de programmation utilisé, il est possible de faire appel à des fonctions existantes, c'est le cas par exemple de la fonction TRACER_POINT_Rouge. Dans Algobox, on trouve notamment de nombreuses fonction mathématiques comme:

sin() // retourne le sinus d'un angle en radian
cos() // retourne le cosinus d'un angle en radian
floor () // retourne la partie entière d'un nombre

Exercice¶

On cherche à deviner l'age de l'utilisateur à un an près. On part de l'hypothese qu'un utilisateur peut avoir entre 1 et 120 ans. L'algorithme propose un age à l'utilisateur et demande à l'utilisateur de rentrer :

+ si il est plus agé que l'age proposé.
- si il est moins agé que l'age proposé.
= si il à bien l'age proposé.

L'algorithme propose des ages jusqu'a ce que l'utilisateur est rentré '='.

Solution proposée¶

FONCTIONS_UTILISEES
VARIABLES
  age_max EST_DU_TYPE NOMBRE
  age_min EST_DU_TYPE NOMBRE
  age_propose EST_DU_TYPE NOMBRE
  reponse EST_DU_TYPE CHAINE
  trouve EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  age_max PREND_LA_VALEUR 120
  age_min PREND_LA_VALEUR 1
  trouve PREND_LA_VALEUR  0
  TANT_QUE (trouve == 0) FAIRE
    DEBUT_TANT_QUE
    age_propose PREND_LA_VALEUR floor((age_min + age_max) / 2)
    AFFICHER "Avez vous "
    AFFICHER age_propose
    AFFICHER* " ans "
    AFFICHER* "+ si plus agé, - si moins agé, = si bonne réponse "
    LIRE reponse
    SI (reponse == "+") ALORS
      DEBUT_SI
      age_min PREND_LA_VALEUR age_propose
      FIN_SI
    SI (reponse == "-") ALORS
      DEBUT_SI
      age_max PREND_LA_VALEUR age_propose
      FIN_SI
    SI (reponse == "=") ALORS
      DEBUT_SI
      trouve PREND_LA_VALEUR 1
      FIN_SI
    FIN_TANT_QUE
  AFFICHER "Vous avez "
  AFFICHER age_propose
  AFFICHER* " ans"
FIN_ALGORITHME

Algorithmique : Boucle POUR¶

On a vu précédemment que l'on pouvait réaliser des boucles de valeur avec une variable et l'instruction TANT_QUE. Il existe une instruction spécialisée, la boucle POUR.

Syntaxe¶

POUR <variable> ALLANT_DE <debut> A <fin>
DEBUT_POUR
...
FIN_POUR

Fonctionnement¶

Le bloc d'instruction entre DEBUT_POUR et FIN_POUR est executer avec des valeurs de variable qui evolue successivement de la valeur debut à la valeur fin Attention debut et fin peuvent être des variables, mais ne peuvent pas changer pendant l'execution de l'instruction POUR

Example¶

FONCTIONS_UTILISEES
VARIABLES
  i EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  POUR i ALLANT_DE 1 A 10
    DEBUT_POUR
    AFFICHER* i
    FIN_POUR
FIN_ALGORITHME

Exercice¶

On cherche à afficher un cercle de rayon 10. Rappel : pour un cercle de rayon 1, la position pour un angle donné a est cosinus(a), sinus(b).

Algorithme

Solution proposée¶

FONCTIONS_UTILISEES
VARIABLES
  angle EST_DU_TYPE NOMBRE
  x EST_DU_TYPE NOMBRE
  y EST_DU_TYPE NOMBRE
  angle_radian EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  POUR angle ALLANT_DE 0 A 360
    DEBUT_POUR
    angle_radian PREND_LA_VALEUR angle * Math.PI / 180
    x PREND_LA_VALEUR cos(angle_radian) * 10
    y PREND_LA_VALEUR sin(angle_radian) * 10
    TRACER_POINT_Vert (x,y)
    FIN_POUR
FIN_ALGORITHME

Algorithmique : Les listes¶

Les listes permettent de stocker des valeurs numérique dans une "table" indicé par des valeurs, les valeurs doivent être affecté avant leur utilisation. Pour accéder à un élément de la liste on utilise [] pour indiquer la position de la valeur dans la table.

Syntaxe¶

VARIABLES
tbl EST_DU_TYPE LISTE
DEBUT_ALGORITHME
  tbl[0] = 25
  tbl[1] = 33
  tbl[2] = 44
  AFFICHER* tbl[0]
  AFFICHER* tbl[1]
  AFFICHER* tbl[2]
FIN_ALGORITHME

Exercice¶

En utilisant la fonction random (), on initialise une liste avec 100 valeurs entieres comprise entre 0 et 500. Afficher la liste des valeurs sous forme de graphique.

Solution proposée¶

FONCTIONS_UTILISEES
VARIABLES
  table EST_DU_TYPE LISTE
  i EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
POUR i ALLANT_DE 0 A 99
    DEBUT_POUR
        table[i] PREND_LA_VALEUR floor(random() * 500)
    FIN_POUR
POUR i ALLANT_DE 0 a 99
    DEBUT_POUR
        TRACER_POINT (i,table[i])
    FIN_POUR


FIN_ALGORITHME

Exercice¶

A partir de l'exercice précédent, trier le tableau de valeur en ordre décroissant avant l'affichage. On pourra afficher l'etat de la liste dans les differentes étapes de tri dans une couleur différente.

Solution Proposée¶

FONCTIONS_UTILISEES
VARIABLES
  table EST_DU_TYPE LISTE
  i EST_DU_TYPE NOMBRE
  j EST_DU_TYPE NOMBRE
  tmp EST_DU_TYPE NOMBRE
  trier EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  POUR i ALLANT_DE 0 A 99
    DEBUT_POUR
    table[i] PREND_LA_VALEUR floor(random() * 500)
    FIN_POUR
  trier PREND_LA_VALEUR 0
  TANT_QUE (trier == 0) FAIRE
    DEBUT_TANT_QUE
    trier PREND_LA_VALEUR 1
    POUR i ALLANT_DE 0 A 98
      DEBUT_POUR
      SI (table[i] < table[i + 1]) ALORS
        DEBUT_SI
        tmp PREND_LA_VALEUR table[i + 1]
        table[i + 1] PREND_LA_VALEUR table[i]
        table[i] PREND_LA_VALEUR tmp
        trier PREND_LA_VALEUR 0
        FIN_SI
      FIN_POUR
    POUR j ALLANT_DE 0 A 99
      DEBUT_POUR
      TRACER_POINT_Rouge (j,table[j])
      FIN_POUR
    FIN_TANT_QUE
  POUR i ALLANT_DE 0 A 99
    DEBUT_POUR
    TRACER_POINT_Vert (i,table[i])
    FIN_POUR
FIN_ALGORITHME

Exercice¶

La solution de l'exercice precedent est un tri à bulles. Quelle est la complexité de l'algorithme ? Comment peut on améliorer le tri pour optimiser la complexité ? Réaliser deux programmes pour mettre en evidence l'amélioration de la complexité

Structuration d'un algorithme : Réalisation de fonctions¶

Une fonction est un bloc d'instructions nommé qui peut être appelé à partir de n'importe qu'elle endroit de l'algorithme. Une fonction accepte des parametres, les parametres sont des variables utilisables dans bloc d'instructions de la fonction. Une fonction retourne une valeur, on nomme une fonction qui ne retourne pas de valeur une procédure. De manière générale, une fonction de structurer un algorithme en permettant :

D'éviter d'écrire le même code plusieurs fois
De représenter la décomposition d'un problème en plusieurs blocs d'instructions identifiées.

Syntaxe¶

FONCTIONS_UTILISEES
  FONCTION mafonction(p1,p2,p3)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER p1+p2+p3
    FIN_FONCTION

Appel de la fonction¶

a PREND_LA_VALEUR mafonction (5,6,unevariable)

Exercice¶

Obélix à deux méthodes pour fabriquer un menhir

Il va chercher un pierre à la carriere. Le voyage lui prend 2 jours aller / retour et il mange 4 sangliers. Ensuite il taille le menhir pendant 1 jour et il mange 1 sanglier
Il demande à Assurancetourix d'aller lui chercher un pierre à la carrière. Assurancetourix demande un fixe de 10 sangliers pour rembourser les concerts annuler puis Assurancetourix prend 3 jours pour ramener une pierre et demande 1/2 sanglier en rémunération. La pierre etant de moins bonne qualité, Obélix prend 2 jours pour la tailler et mange 3 sangliers.

En fonction d'une commande de x menhirs, aider Obélix à choisir la méthode la plus econome en sangliers. Combien de jours doit il prévoir pour réaliser cette commande, sachant qu'évidemment Obélix taille les pierres en stock pendant le voyage d'Assurancetourix (on considere que le stock de pierre est a 0 lors de la commande) ?

Solution proposée¶

FONCTIONS_UTILISEES
  FONCTION jours_assurancetourix(nbmenhir)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER 5 + ((nbmenhir - 1) * 3)
    FIN_FONCTION
  FONCTION sanglier_assurancetourix(nbmenhir)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER 10 + (nbmenhir * 3.5)
    FIN_FONCTION
  FONCTION jours_obelix(nbmenhir)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER nbmenhir * 3
    FIN_FONCTION
  FONCTION sanglier_obelix(nbmenhir)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER nbmenhir * 5
    FIN_FONCTION
VARIABLES
  menhir_commander EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  LIRE menhir_commander
  SI (sanglier_obelix (menhir_commander) <= sanglier_assurancetourix(menhir_commander)) ALORS
    DEBUT_SI
    AFFICHER* "methode Obelix"
    AFFICHER "delai en jours = "
    AFFICHERCALCUL* jours_obelix(menhir_commander)
    FIN_SI
    SINON
      DEBUT_SINON
      AFFICHER* "methode Assurancetourix"
        AFFICHER "delai en jours = "
        AFFICHERCALCUL* jours_assurancetourix(menhir_commander)
      FIN_SINON
FIN_ALGORITHME

Exercice¶

A partir du probleme précédent, comment peut on representer graphiquement le point de bascule ou une solution devient plus avantageuse que l'autre

Solution proposée¶

FONCTIONS_UTILISEES
  FONCTION jours_assurancetourix(nbmenhir)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER 5 + ((nbmenhir - 1) * 3)
    FIN_FONCTION
  FONCTION sanglier_assurancetourix(nbmenhir)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER 10 + (nbmenhir * 3.5)
    FIN_FONCTION
  FONCTION jours_obelix(nbmenhir)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER nbmenhir * 3
    FIN_FONCTION
  FONCTION sanglier_obelix(nbmenhir)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER nbmenhir * 5
    FIN_FONCTION
VARIABLES
  menhir_commander EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  POUR menhir_commander ALLANT_DE 1 A 15
    DEBUT_POUR
    TRACER_POINT_Rouge (menhir_commander,sanglier_obelix(menhir_commander))
    TRACER_POINT_Bleu (menhir_commander,sanglier_assurancetourix(menhir_commander))
    FIN_POUR
FIN_ALGORITHME

Exercice¶

En utilisant la fonction random (), on initialise une liste avec 100 valeurs entieres comprise entre 0 et 500. Afficher l'indice et la valeur de la valeur maximum Afficher l'indice et la valeur de la valeur minimum

Solution proposée¶

FONCTIONS_UTILISEES
VARIABLES
  table EST_DU_TYPE LISTE
  i EST_DU_TYPE NOMBRE
  j EST_DU_TYPE NOMBRE
  tmp EST_DU_TYPE NOMBRE
  trier EST_DU_TYPE NOMBRE
  min EST_DU_TYPE NOMBRE
  max EST_DU_TYPE NOMBRE
  pos_min EST_DU_TYPE NOMBRE
  pos_max EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  POUR i ALLANT_DE 0 A 99
    DEBUT_POUR
    table[i] PREND_LA_VALEUR floor(random() * 500)
    FIN_POUR
  min PREND_LA_VALEUR table[0]
  pos_min PREND_LA_VALEUR 0
  max PREND_LA_VALEUR table[0]
  pos_max PREND_LA_VALEUR 0
  POUR i ALLANT_DE 0 A 99
    DEBUT_POUR
    SI (table[i] < min) ALORS
      DEBUT_SI
      min PREND_LA_VALEUR table[i]
      pos_min PREND_LA_VALEUR i
      FIN_SI
    SI (table[i] > max) ALORS
      DEBUT_SI
      max PREND_LA_VALEUR table[i]
      pos_max PREND_LA_VALEUR i
      FIN_SI
    FIN_POUR
  AFFICHER "min"
  AFFICHER* min
  AFFICHER "max"
  AFFICHER* max
FIN_ALGORITHME

Exercice¶

En utilisant la fonction random (), on initialise une liste avec 99 valeurs entieres comprise entre 0 et 500. Afficher l'indice et la valeur de la valeur mediane (la valeur qui possede autant d'elements inférieurs que d'elements supérieurs)

Solution proposée¶

A l'aide du tri à bulle, on tri le tableau de valeur. La valeur médiane se trouve à la position milieu de la liste, c'est à dire l'indice 49

FONCTIONS_UTILISEES
VARIABLES
  table EST_DU_TYPE LISTE
  i EST_DU_TYPE NOMBRE
  j EST_DU_TYPE NOMBRE
  tmp EST_DU_TYPE NOMBRE
  trier EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  POUR i ALLANT_DE 0 A 98
    DEBUT_POUR
    table[i] PREND_LA_VALEUR floor(random() * 500)
    FIN_POUR
  trier PREND_LA_VALEUR 0
  TANT_QUE (trier == 0) FAIRE
    DEBUT_TANT_QUE
    trier PREND_LA_VALEUR 1
    POUR i ALLANT_DE 0 A 97
      DEBUT_POUR
      SI (table[i] < table[i + 1]) ALORS
        DEBUT_SI
        tmp PREND_LA_VALEUR table[i + 1]
        table[i + 1] PREND_LA_VALEUR table[i]
        table[i] PREND_LA_VALEUR tmp
        trier PREND_LA_VALEUR 0
        FIN_SI
      FIN_POUR
    FIN_TANT_QUE
  AFFICHER "la valeur mediane est "
  AFFICHER* table[49]
FIN_ALGORITHME

Exercice¶

Le petit poucet se promene en forêt. A chaque pas il avance d'une valeur aléatoire comprise entre 0 et 1 dans la direction X et la direction Y (les valeurs sont differentes pour x et y). A chaque pas il depose un caillou pour retrouver son chemin. Il dispose de 100 cailloux au depart et fait demi-tour quand il n'à plus de caillou. Pour l'aider à retrouver son chemin, représenter graphiquement sa position d'arrivée et le chemin du retour.

Solution Proposée¶

FONCTIONS_UTILISEES
  FONCTION oublier_pas( )
    VARIABLES_FONCTION
    DEBUT_FONCTION
    SI (spos > 0) ALORS
      DEBUT_SI
      spos PREND_LA_VALEUR spos - 1
      FIN_SI
    FIN_FONCTION
  FONCTION combien_pas( )
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER spos
    FIN_FONCTION
  FONCTION dernier_y( )
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER liste_y [spos - 1]
    FIN_FONCTION
  FONCTION dernier_x( )
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER liste_x[spos - 1]
    FIN_FONCTION
  FONCTION stocke_pas(x,y)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    AFFICHER* spos
    liste_x[spos] PREND_LA_VALEUR x
    liste_y[spos] PREND_LA_VALEUR y
    spos PREND_LA_VALEUR spos + 1
    FIN_FONCTION
VARIABLES
  liste_x EST_DU_TYPE LISTE
  liste_y EST_DU_TYPE LISTE
  pas EST_DU_TYPE NOMBRE
  posx EST_DU_TYPE NOMBRE
  posy EST_DU_TYPE NOMBRE
  spos EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  posx PREND_LA_VALEUR 0
  posy PREND_LA_VALEUR 0
  spos PREND_LA_VALEUR 0
  APPELER_FONCTION stocke_pas (posx,posy)
  POUR pas ALLANT_DE 1 A 100
    DEBUT_POUR
    AFFICHER* pas
    posx PREND_LA_VALEUR random() + posx
    posy PREND_LA_VALEUR random() + posy
    APPELER_FONCTION stocke_pas (posx, posy)
    FIN_POUR
  TANT_QUE (combien_pas () > 0) FAIRE
    DEBUT_TANT_QUE
    TRACER_POINT_Rouge (dernier_x(),dernier_y())
    APPELER_FONCTION oublier_pas()
    FIN_TANT_QUE
FIN_ALGORITHME

Exercice¶

Nous sommes dans un restaurant. Le restaurant propose 3 plats differents.

Pizza
Galette saucisse
Kebab

Le cuisinier s'absente faire une course, le serveur prend 10 commandes pendant son absence. Les plats des commandes sont bien evidement aléatoires, chaque commandes comporte 1 plat unique.

Aider le cuisinier à préparer les commandes à son retour, pour éviter de déplaire à la clientêle, les commandes doivent être réalisées dans l'ordre de la commande.
Pour accélerer le mouvement, le cuisinier ne tient plus compte de l'ordre des commandes et souhaite réaliser toutes les Pizzas avant de passer aux galettes puis aux kebab. Comment modifier l'algorithme ?

Solution proposée 1¶

FONCTIONS_UTILISEES
FONCTION plat_suivant()
    VARIABLES_FONCTION
    DEBUT_FONCTION
    SI (consumer_pos < producer_pos) ALORS
        DEBUT_SI
        consumer_pos PREND_LA_VALEUR consumer_pos + 1
        FIN_SI
    FIN_FONCTION
FONCTION plat_disponible()
    VARIABLES_FONCTION
        disponible EST_DU_TYPE NOMBRE    
    DEBUT_FONCTION
    disponible PREND_LA_VALEUR 0
    SI (consumer_pos < producer_pos) ALORS
        DEBUT_SI
        disponible PREND_LA_VALEUR 1
        FIN_SI
    RENVOYER disponible
    FIN_FONCTION
FONCTION lire_plat()
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER fifo_plat[consumer_pos]
    FIN_FONCTION
FONCTION stocke_plat(plat)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    fifo_plat[producer_pos] PREND_LA_VALEUR plat
    producer_pos PREND_LA_VALEUR producer_pos + 1
    FIN_FONCTION
FONCTION afficher_plat(plat)
    VARIABLES_FONCTION
    DEBUT_FONCTION
        SI (plat == PIZZA) ALORS
            DEBUT_SI
            AFFICHER* "Pizza"
            FIN_SI
        SINON
                DEBUT_SINON
                SI (plat == GALETTE) ALORS
                    DEBUT_SI
                    AFFICHER* "Galette"
                    FIN_SI
                SINON
                    DEBUT_SINON
                    SI (plat == KEBAB) ALORS
                        DEBUT_SI
                        AFFICHER* "Kebab"
                        FIN_SI
                    FIN_SINON   
                FIN_SINON   
    FIN_FONCTION

VARIABLES
  PIZZA EST_DU_TYPE NOMBRE
  GALETTE EST_DU_TYPE NOMBRE
  KEBAB EST_DU_TYPE NOMBRE
  fifo_plat EST_DU_TYPE LISTE
  producer_pos EST_DU_TYPE NOMBRE
  consumer_pos EST_DU_TYPE NOMBRE
  i EST_DU_TYPE NOMBRE
  monplat EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  PIZZA PREND_LA_VALEUR 0
  GALETTE PREND_LA_VALEUR 1
  KEBAB PREND_LA_VALEUR 2
  producer_pos PREND_LA_VALEUR 0
  consumer_pos PREND_LA_VALEUR 0

  POUR i ALLANT_DE 1 A 10
    DEBUT_POUR
    monplat PREND_LA_VALEUR floor(random() * 3)
        APPELER_FONCTION afficher_plat(monplat)
        APPELER_FONCTION stocke_plat(monplat)
    FIN_POUR

  AFFICHER* " " 
    AFFICHER* "Le cuisinier commence"   
  AFFICHER* " " 

    TANT_QUE (plat_disponible () > 0) FAIRE
        DEBUT_TANT_QUE
        monplat PREND_LA_VALEUR lire_plat()
      APPELER_FONCTION afficher_plat(monplat)
      APPELER_FONCTION plat_suivant ()
        FIN_TANT_QUE  

FIN_ALGORITHME

Solution proposée 2¶

FONCTIONS_UTILISEES
  FONCTION trier_fifo( )
    VARIABLES_FONCTION
      triok EST_DU_TYPE NOMBRE
      j EST_DU_TYPE NOMBRE
      tmp EST_DU_TYPE NOMBRE
    DEBUT_FONCTION
    triok PREND_LA_VALEUR 0
    TANT_QUE (triok == 0) FAIRE
      DEBUT_TANT_QUE
      triok PREND_LA_VALEUR 1
      POUR j ALLANT_DE consumer_pos A producer_pos - 1
        DEBUT_POUR
        SI (fifo_plat[j] > fifo_plat[j + 1]) ALORS
          DEBUT_SI
          tmp PREND_LA_VALEUR fifo_plat[j+1]
          fifo_plat[j+1] PREND_LA_VALEUR fifo_plat[j]
          fifo_plat[j] PREND_LA_VALEUR tmp
          triok PREND_LA_VALEUR 0
          FIN_SI
        FIN_POUR
      FIN_TANT_QUE
    FIN_FONCTION
  FONCTION plat_suivant( )
    VARIABLES_FONCTION
    DEBUT_FONCTION
    SI (consumer_pos < producer_pos) ALORS
      DEBUT_SI
      consumer_pos PREND_LA_VALEUR consumer_pos + 1
      FIN_SI
    FIN_FONCTION
  FONCTION plat_disponible( )
    VARIABLES_FONCTION
      disponible EST_DU_TYPE NOMBRE
    DEBUT_FONCTION
    disponible PREND_LA_VALEUR 0
    SI (consumer_pos < producer_pos) ALORS
      DEBUT_SI
      disponible PREND_LA_VALEUR 1
      FIN_SI
    RENVOYER disponible
    FIN_FONCTION
  FONCTION lire_plat( )
    VARIABLES_FONCTION
    DEBUT_FONCTION
    RENVOYER fifo_plat[consumer_pos]
    FIN_FONCTION
  FONCTION stocke_plat(plat)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    fifo_plat[producer_pos] PREND_LA_VALEUR plat
    producer_pos PREND_LA_VALEUR producer_pos + 1
    FIN_FONCTION
  FONCTION afficher_plat(plat)
    VARIABLES_FONCTION
    DEBUT_FONCTION
    SI (plat == PIZZA) ALORS
      DEBUT_SI
      AFFICHER* "Pizza"
      FIN_SI
      SINON
        DEBUT_SINON
        SI (plat == GALETTE) ALORS
          DEBUT_SI
          AFFICHER* "Galette"
          FIN_SI
          SINON
            DEBUT_SINON
            SI (plat == KEBAB) ALORS
              DEBUT_SI
              AFFICHER* "Kebab"
              FIN_SI
            FIN_SINON
        FIN_SINON
    FIN_FONCTION
VARIABLES
  PIZZA EST_DU_TYPE NOMBRE
  GALETTE EST_DU_TYPE NOMBRE
  KEBAB EST_DU_TYPE NOMBRE
  fifo_plat EST_DU_TYPE LISTE
  producer_pos EST_DU_TYPE NOMBRE
  consumer_pos EST_DU_TYPE NOMBRE
  i EST_DU_TYPE NOMBRE
  monplat EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  PIZZA PREND_LA_VALEUR 0
  GALETTE PREND_LA_VALEUR 1
  KEBAB PREND_LA_VALEUR 2
  producer_pos PREND_LA_VALEUR 0
  consumer_pos PREND_LA_VALEUR 0
  POUR i ALLANT_DE 1 A 10
    DEBUT_POUR
    monplat PREND_LA_VALEUR floor(random() * 3)
    APPELER_FONCTION afficher_plat(monplat)
    APPELER_FONCTION stocke_plat(monplat)
    FIN_POUR
  AFFICHER* " "
  AFFICHER* "Le cuisinier commence"
  AFFICHER* " "
  APPELER_FONCTION trier_fifo()
  TANT_QUE (plat_disponible () > 0) FAIRE
    DEBUT_TANT_QUE
    monplat PREND_LA_VALEUR lire_plat()
    APPELER_FONCTION afficher_plat(monplat)
    APPELER_FONCTION plat_suivant ()
    FIN_TANT_QUE
FIN_ALGORITHME

Exercice¶

Une fusée décolle du sol à une vitesse de 104 m/s et coupe immédiatement son moteur. Sachant que la fusée est soumise à une gravité de 10m/s-2, calculer l'altitude maximum atteinte par la fusée, ainsi que le temps à la milliseconde pret pour atteindre cette altitude.

Rappel :

A chaque seconde, la vitesse diminue d'une fois la gravité.
A chaque seconde, l'altitude augmente d'une fois la vitesse.

On essaiera de limiter la complexité de l'algorithme.

Solution Proposée¶

FONCTIONS_UTILISEES
  FONCTION recursive_dichotomie(t1,v1,t2,v2)
    VARIABLES_FONCTION
      t EST_DU_TYPE NOMBRE
      v EST_DU_TYPE NOMBRE
    DEBUT_FONCTION
    SI (t2 - t1 <= 0.001) ALORS
      DEBUT_SI
      RENVOYER t1
      FIN_SI
    t PREND_LA_VALEUR (t1 + t2) / 2
    v PREND_LA_VALEUR (v1 + v2) / 2
    SI (v > 0) ALORS
      DEBUT_SI
      RENVOYER recursive_dichotomie (t,v,t2,v2)
      FIN_SI
      SINON
        DEBUT_SINON
        RENVOYER recursive_dichotomie (t1,v1, t,v)
        FIN_SINON
    FIN_FONCTION
VARIABLES
  vitesse EST_DU_TYPE NOMBRE
  altitude EST_DU_TYPE NOMBRE
  vitesse_precedente EST_DU_TYPE NOMBRE
  gravite EST_DU_TYPE NOMBRE
  temps EST_DU_TYPE NOMBRE
  altitude_precis EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  vitesse PREND_LA_VALEUR 104
  gravite PREND_LA_VALEUR 10
  temps PREND_LA_VALEUR 0

  TANT_QUE (vitesse >= 0) FAIRE
    DEBUT_TANT_QUE
    vitesse_precedente PREND_LA_VALEUR vitesse
    vitesse PREND_LA_VALEUR vitesse - gravite
    altitude PREND_LA_VALEUR altitude + vitesse
    temps PREND_LA_VALEUR temps + 1
    FIN_TANT_QUE
  AFFICHER "altitude "
  AFFICHER* altitude
  AFFICHER "vitesse_precedente "
  AFFICHER* vitesse_precedente
  AFFICHER "vitesse "
  AFFICHER* vitesse
  AFFICHER "temps "
  AFFICHER* temps
  temps PREND_LA_VALEUR recursive_dichotomie (temps -1, vitesse_precedente, temps, vitesse)
  AFFICHER "temps precis "
  AFFICHER* temps
  altitude_precis PREND_LA_VALEUR altitude - vitesse
  altitude_precis PREND_LA_VALEUR altitude_precis + (temps - floor(temps)) * vitesse
  AFFICHER "estimation altitude "
  AFFICHER* altitude_precis
FIN_ALGORITHME

In [ ]: