EVALUATION EN ALGORITHMIQUE TEST  03/ 10    

Exercice 1 : Définition : Algorithme, boucle, instruction, Processeur.
Exercice 2 : Question réponse (justifier)

1. Soit L’affectation tab[i,j] := ‘X’ ; quel est le rôle de cette instruction ?
2. Donnez la différence entre une variable et une constante avec un exemple à l’appui ?
3. Bool est une variable de type booléen, l’affectation bool := False ; est-elle correcte  ?
4. C’est quoi un invariant de boucle ?
5. Différence entre TabCar[i] et TabCar[i,i] pour i égale à 1 ?

Exercice 3 : Donnez le principe claire et nette du Tri-Sélection et donnez son algorithme.
Exercice 4 : S est une suite de nombre entier positif ordonné par Ordre Croissant et terminé par le marqueur -1. Ecrire un Algorithme qui détermine la longueur Lmax de la plus longue sous suite extraite de S et ne comportant que des éléments identiques : Exemple : Si la suite est S=111222233334566666777899-1, on affiche :
 La plus longue sous_suite est 6 et sa Longueur vaut 5.
Exercice 5 : Ecrire un algorithme qui demande à l’utilisateur d’entrer une série de nombre se terminant par le marqueur -1et qui recherche l’indice du plus petit élément d’un tableau et l’affiche, Exemple :
 

       
L’indice du plus petit élément de votre Tableau est 13.

Exercice 6 :Bomberman est une série de jeux vidéo de Hudson soft ou le jouer incarne un poseur de bombes, alors le but du jeu étant de faire exploser les adversaires/ennemis pour gagner. Alors Mr Joël_Yk vous propose de créer un jeu de ce sous une autre forme style en 3 phase :
Etape (1) Le placement des Bombes : En fait les bombes que nous allons représenter par ‘Boom’ seront au préable place dans les éléments paire et impaire de notre grille (matrice) comme indiquez ci-dessous :

Etape (2) Lancement : Les bombes étant placés l’utilisateur devra juste entré un nombre qui vas correspondre au pas (déplacement) de son avatar nomme (Bomber) le nombre entrer devra être compris entre 1 et N (la taille) la grille.
Etape (3) Règlé du jeu :  Si l’avatar de l’utilisateur se positionne sur les Bombes (Boom) que nous avons au préable placé au étage de notre grille l’on l’affiche Game Over sinon on affiche Vous venez de Franchir l’étage i (i indice de l’étage) avec succès ainsi de suite jusqu’à atteindre le dernier étage de notre grille.
Remarque : La disposition des Bombes pour cet exercice vous êtes impose ainsi que la taille de la grille qui seras de taille N*N.
(Cet exercice est le fruit de mon imagination donc une reproduction, copie parfaite à mauvais escient © est interdit)

                                                                                                                                                                                                                                                                                                                                                  Par Joel_Yk | Contact :+237652027193

EVALUATION EN ALGORITHMIQUE TEST  03/ 10    — CORRECTION

Exercice 1 : Définitions

• Algorithme : suite finie et ordonnée d’instructions non ambiguës permettant de résoudre un problème.
• Boucle : structure répétitive qui exécute plusieurs fois un même bloc d’instructions selon une condition (ou un nombre de tours).
• Instruction : commande élémentaire de l’algorithme (affectation, lecture, écriture, test, boucle…).
• Processeur : composant de l’ordinateur (CPU) qui exécute les instructions des programmes (calcul, contrôle, gestion).

Exercice 2 : Questions / réponses (justifier)

1. tab[i,j] ← 'X' : affecte le caractère 'X' à la case de la matrice tab située à la ligne i et colonne j.
   Rôle : marquer une position, remplir une grille, initialiser/mettre à jour une case.
2. Variable : zone mémoire dont la valeur peut changer pendant l’exécution.
   Constante : valeur fixe, non modifiable pendant l’exécution.
   Exemple :
   • Const N ← 8 (taille fixe)
   • Var score : entier ; score ← score + 1 (change)
3. Bool est de type booléen, donc bool ← Faux est correcte (à condition d’utiliser les mots-clés du cours : Vrai/Faux ou True/False, mais pas mélanger les deux).
4. Invariant de boucle : propriété vraie avant l’entrée dans la boucle et qui reste vraie après chaque itération. Il sert à prouver la correction d’un algorithme.
5. Pour i = 1 :
   • TabCar[i] = TabCar[1] : case 1 d’un tableau 1D.
   • TabCar[i,i] = TabCar[1,1] : case (1,1) d’une matrice 2D.
   Différence : pas la même structure (1 dimension vs 2 dimensions), donc pas la même case mémoire.

Exercice 3 : Tri-Sélection : principe + algorithme

Principe (clair et net) : à chaque étape, on cherche le plus petit élément de la partie non triée, puis on l’échange avec le premier élément de cette partie. La zone triée grandit de gauche à droite.

Le tri est l'une des opérations fondamentales en informatique et en science de données. Il consiste à réorganiser un ensemble de données dans un ordre particulier, généralement croissant ou décroissant. Il existe de nombreuses méthodes de tri, chacune ayant ses propres caractéristiques et efficacités. L'un des algorithmes de tri les plus simples, mais néanmoins instructifs, est l'algorithme de tri par sélection.

PSEUDO-CODE

Algorithme TriSelection;
    Const  N = 100;
    Var
        t: tableau [1-N] de Elément;
        X: Elément;
        val, i, j, k: Entier;

    Début
        Écrire("Lecture des éléments du tableau")
        Pour i de 1 à N faire
            Écrire("Entrer le ", i, "ème élément")
            Lire(t[i]);
        Fin Pour

        Pour i de 1 à N faire

                   j ← i;
            Pour k de i + 1 à N faire
                Si t[k] < t[j] alors
                    j ← k;
                Fin Si
            Fin Pour
            val ← t[j];
            t[j] ← t[i];
            t[i] ← val
        Fin Pour

        Écrire("Tableau trié :")
        Pour i de 1 à N faire
            Écrire(t[i])
        Fin Pour
    Fin.

Exercice 4 : Plus longue sous-suite d’éléments identiques

Algorithme PlusLongueSousSuite_Tableau ;
Const
    NMAX = 200 ;
Var
    S : tableau[1..NMAX] de entier ;
    n, i : entier ;
    x : entier ;
    L, Lmax : entier ;
    vmax : entier ;
Début
    n ← 0 ;

    Ecrire("Entrer une suite croissante (fin -1) : ") ;

    /* Saisie 1 par 1, sans dépasser NMAX */
    Repeter
        Lire(x) ;

        Si (x ≠ -1) Alors
            Si (n < NMAX) Alors
                n ← n + 1 ;
                S[n] ← x ;
            Sinon
                Ecrire("ERREUR : tableau plein (max = ", NMAX, ").") ;
                /* on force l'arrêt de la saisie */
                x ← -1 ;
            FinSi
        FinSi
    Jusqu’à (x = -1) ;

    Si (n = 0) Alors
        Ecrire("Suite vide.") ;
    Sinon
        /* Recherche de la plus longue sous-suite d'identiques */
        L ← 1 ;
        Lmax ← 1 ;
        vmax ← S[1] ;

        Pour i de 2 à n Faire
            Si (S[i] = S[i-1]) Alors
                L ← L + 1 ;
            Sinon
                Si (L > Lmax) Alors
                    Lmax ← L ;
                    vmax ← S[i-1] ;
                FinSi
                L ← 1 ;
            FinSi
        FinPour

        /* Vérifier le dernier bloc */
        Si (L > Lmax) Alors
            Lmax ← L ;
            vmax ← S[n] ;
        FinSi

        Ecrire("La plus longue sous-suite est ", vmax, " et sa Longueur vaut ", Lmax, ".") ;
    FinSi
Fin.

Exercice 5 : Série terminée par -1 : indice du plus petit élément

On lit une suite, on stocke dans un tableau, puis on affiche la position (indice) du minimum.

Algorithme IndiceMinimum ;
Const
    NMAX = 300 ;
Var
    t : tableau[1..NMAX] de réel ;
    k, i, posMin : entier ;
    x, minVal : réel ;
Début
    k ← 0 ;
    Ecrire("Entrer des nombres (fin -1) : ") ;
    Lire(x) ;

    Tantque (x ≠ -1) Faire
        k ← k + 1 ;
        t[k] ← x ;
        Lire(x) ;
    FinTantque

    Si (k = 0) Alors
        Ecrire("Aucune valeur saisie.") ;
    Sinon
        minVal ← t[1] ;
        posMin ← 1 ;

        Pour i de 2 à k Faire
            Si (t[i] < minVal) Alors
                minVal ← t[i] ;
                posMin ← i ;
            FinSi
        FinPour

        Ecrire("L'indice du plus petit élément de votre Tableau est ", posMin, ".") ;
    FinSi
Fin.

Remarque : Dans l’exemple de l’énoncé, l’indice demandé est 13.

Exercice 6 : Bomberman (3 phases) 

Idée : on construit une grille N×N. Les bombes “Boom” sont placées selon la disposition imposée (image) : ici on modélise exactement par la règle suivante (très utilisée dans ce type d’exercice) :

• Une case contient "Boom" si (i + j) mod 2 = 0, sinon elle contient "." (case vide).

Ensuite l’utilisateur donne un pas p (entre 1 et N). Le Bomber avance d’étage en étage (ligne par ligne). À chaque étage i, sa colonne est :

col ← 1 + ((i-1) * p mod N)

Si la case (i, col) est une bombe => Game Over, sinon succès jusqu’au dernier étage.

Algorithme BombermanGenius ;
Var
    Grille : tableau[1..N, 1..N] de chaine ;
    N, i, j, p, col : entier ;
Début
    N ← 5 ;  /* taille imposée ou lue, selon l'énoncé */
    
    /* Phase 1 : placement des bombes (disposition imposée) */
    Pour i de 1 à N Faire
        Pour j de 1 à N Faire
            Si ((i + j) mod 2 = 0) Alors
                Grille[i,j] ← "Boom" ;
            Sinon
                Grille[i,j] ← "." ;
            FinSi
        FinPour
    FinPour

    /* Affichage optionnel de la grille */
    Ecrire("===== GRILLE =====") ;
    Pour i de 1 à N Faire
        Pour j de 1 à N Faire
            EcrireSansRetour(Grille[i,j], " ") ;
        FinPour
        Ecrire("") ;
    FinPour

    /* Phase 2 : lancement (choix du pas) */
    Repeter
        Ecrire("Entrer le pas p (1..", N, ") : ") ;
        Lire(p) ;
    Jusqu’à (p >= 1 et p <= N) ;

    /* Phase 3 : règle du jeu */
    Pour i de 1 à N Faire
        col ← 1 + (((i - 1) * p) mod N) ;

        Si (Grille[i, col] = "Boom") Alors
            Ecrire("Game Over : Bombe à l'étage ", i, " (col ", col, ").") ;
            FinAlgorithme
        Sinon
            Ecrire("Vous venez de Franchir l'étage ", i, " avec succès (col ", col, ").") ;
        FinSi
    FinPour

    Ecrire("Bravo : vous avez atteint le dernier étage !") ;
Fin.

Par Joel_Yankam | Contact :+237652027193

 PROCHAIN TEST  >>