Aller au contenu principal

Apprendre les algo – Jour 7

Introduction​

Jusqu'ici, vous avez déjà vu :

  • les variables
  • les conditions
  • les boucles
  • les tableaux
  • les procédures et les fonctions
  • les classes

Le moment est donc venu de passer aux exercices.

Ici, nous allons travailler sur une classe Tableau. Le but est seulement de résoudre des exercices simples et très classiques.

À chaque fois, vous trouverez :

  • l'énoncé
  • le principe utilisé
  • le corrigé
  • un appel dans le programme principal

N'hésitez pas à relire le jour 4, le jour 5 et le jour 6 si un point vous semble flou.

Base de départ​

Si vous utilisez JetBrains Rider, vous pouvez créer rapidement le projet comme ceci :

  • File
  • New Solution
  • choisir Console Application
  • choisir C#
  • donner un nom au projet
  • valider

Une fois le projet créé, gardez simplement une structure très simple au début.

Par exemple :

ConsoleApp2/
├── Program.cs
└── Tableau.cs

Ici :

  • Program.cs contient le programme principal
  • Tableau.cs contient la classe Tableau

Avant les exercices, voici par exemple ce que vous pouvez mettre dans Tableau.cs :

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;

    public Tableau()
    {
        tab = new int[N];
        l = 0;
    }
}

Ici :

  • tab contient les valeurs
  • l représente le nombre d'éléments réellement utilisés
  • N représente la capacité maximale

En langage très simple :

  • private int[] tab; : c'est la grande boîte qui va contenir les nombres
  • private int l; : c'est le nombre de cases vraiment remplies
  • public static int N = 100; : c'est la taille maximale du tableau

Il faut bien distinguer l et N :

  • N dit combien de places existent au total
  • l dit combien de places sont déjà utilisées

Par exemple, on peut avoir :

  • N = 10
  • l = 4

Cela veut dire :

  • le tableau peut contenir 10 valeurs au maximum
  • mais pour l'instant, seulement 4 cases sont vraiment utilisées

Illustration de la différence entre l et N

Le bloc suivant :

public Tableau()
{
    tab = new int[N];
    l = 0;
}

s'appelle un constructeur.

Pour faire très simple, c'est un morceau de code qui prépare l'objet au moment où on le crée.

Ici, il sert juste à initialiser les attributs :

  • tab = new int[N]; : on fabrique un tableau vide de taille N
  • l = 0; : on dit qu'au début, aucune case n'est utilisée

On peut le voir comme ceci :

  • on prépare l'armoire
  • on fixe le nombre total de cases
  • puis on dit qu'au départ, elle est vide

Exercice 1. estVide()​

Énoncé​

Écrire une méthode qui dit si le tableau est vide.

Principe​

On utilise ici une idée très simple :

Vous avez compris que l est censé contenir le nombre d'éléments réellement présents dans le tableau.

Donc, si on veut savoir si le tableau est vide, c'est très simple :

  • s'il n'y a aucun élément, alors l vaut 0
  • donc il suffit de vérifier si l == 0

Illustration du principe pour savoir si le tableau est vide

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public bool estVide()
    {
        return l == 0;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        Console.WriteLine(tableau.estVide());
    }
}

Exercice 2. estTrie()​

Énoncé​

Écrire une méthode qui dit si le tableau est trié dans l'ordre croissant.

Principe​

On utilise ici le schéma de parcours vu au jour 4 :

  • on compare chaque case avec la suivante
  • dès qu'on trouve une paire mal ordonnée, on répond false

Illustration du principe pour savoir si le tableau est trie

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public bool estTrie()
    {
        int i = 0;

        while (i < l - 1)
        {
            if (tab[i] > tab[i + 1])
            {
                return false;
            }
            i++;
        }

        return true;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(3);
        tableau.ajouterElement(8);
        tableau.ajouterElement(12);
        Console.WriteLine(tableau.estTrie());
    }
}

Exercice 3. ajouterElement(int element)​

Énoncé​

Ajouter un élément à la fin du tableau.

Principe​

On place la nouvelle valeur à la position l, puis on augmente l.

Illustration du principe pour ajouter un élément

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void ajouterElement(int element)
    {
        tab[l] = element;
        l = l + 1;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
    }
}

Exercice 4. afficher()​

Énoncé​

Afficher tous les éléments du tableau.

Principe​

On utilise le schéma de parcours :

  • on part du début
  • on affiche chaque case
  • on avance avec i

Illustration du schéma de parcours

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void afficher()
    {
        int i = 0;

        while (i != l)
        {
            Console.Write("[" + tab[i] + "]");
            i++;
        }

        Console.WriteLine();
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.afficher();
    }
}

Exercice 5. sommeMoyenne()​

Énoncé​

Calculer puis afficher la somme et la moyenne des éléments.

Principe​

On utilise encore le schéma de parcours :

  • on additionne tous les éléments
  • puis on divise la somme par la taille

Illustration du schéma de parcours pour sommer

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void sommeMoyenne()
    {
        if (estVide())
        {
            Console.WriteLine("Tableau vide");
            return;
        }

        int i = 0;
        int som = 0;

        while (i != l)
        {
            som += tab[i];
            i++;
        }

        float moy = (float)som / l;
        Console.WriteLine("La somme est : " + som);
        Console.WriteLine("La moyenne est : " + moy);
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(10);
        tableau.ajouterElement(30);
        tableau.sommeMoyenne();
    }
}

Exercice 6. estPresent(int element)​

Énoncé​

Dire si un élément est présent dans le tableau.

Principe​

On utilise le schéma de recherche vu au jour 4 :

  • on avance tant qu'on n'a pas trouvé
  • ou tant qu'on n'est pas arrivé à la fin

Illustration du schéma de recherche

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public bool estPresent(int element)
    {
        int i = 0;

        while (i != l && tab[i] != element)
        {
            i++;
        }

        return i != l;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        Console.WriteLine(tableau.estPresent(200));
    }
}

Exercice 7. nbOccurence(int element)​

Énoncé​

Compter combien de fois un élément apparaît dans le tableau.

Principe​

On parcourt tout le tableau :

  • si l'élément courant est égal à la valeur cherchée
  • on augmente le compteur

Illustration du schéma de parcours pour compter

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public int nbOccurence(int element)
    {
        int i = 0;
        int cpt = 0;

        while (i != l)
        {
            if (tab[i] == element)
            {
                cpt = cpt + 1;
            }

            i++;
        }

        return cpt;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(20);
        Console.WriteLine("NB occ de 20 : " + tableau.nbOccurence(20));
    }
}

Exercice 8. positionPremierOcc(int element)​

Énoncé​

Trouver la position de la première occurrence d'un élément.

Principe​

On réutilise le schéma de recherche :

  • si on trouve, on retourne l'indice
  • sinon, on retourne -1

Illustration du schéma de recherche pour la première occurrence

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public int positionPremierOcc(int element)
    {
        int i = 0;

        while (i != l && tab[i] != element)
        {
            i++;
        }

        if (i != l)
        {
            return i;
        }

        return -1;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        Console.WriteLine("Position premier occ de 10 : " + tableau.positionPremierOcc(10));
    }
}

Exercice 9. min()​

Énoncé​

Trouver le plus petit élément du tableau.

Principe​

On suppose au départ que le minimum est le premier élément, puis on compare avec tous les autres.

Illustration du principe pour chercher le minimum

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public int min()
    {
        if (estVide())
        {
            // On arrête ici, car on ne peut pas chercher un minimum dans un tableau vide.
            throw new Exception("Tableau vide");
        }

        int i = 1;
        int min = tab[0];

        while (i != l)
        {
            if (tab[i] < min)
            {
                min = tab[i];
            }

            i++;
        }

        return min;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        Console.WriteLine(tableau.min());
    }
}

Exercice 10. max()​

Énoncé​

Trouver le plus grand élément du tableau.

Principe​

Même idée que pour le minimum, mais avec la comparaison inverse.

Illustration du principe pour chercher le maximum

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public int max()
    {
        if (estVide())
        {
            // On arrête ici, car on ne peut pas chercher un maximum dans un tableau vide.
            throw new Exception("Tableau vide");
        }

        int i = 1;
        int max = tab[0];

        while (i != l)
        {
            if (tab[i] > max)
            {
                max = tab[i];
            }

            i++;
        }

        return max;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(100);
        Console.WriteLine(tableau.max());
    }
}

Exercice 11. trier()​

Énoncé​

Trier le tableau dans l'ordre croissant.

Principe​

On utilise ici un tri très simple :

  • on fixe une case
  • on la compare aux suivantes
  • on échange si besoin

Illustration du principe du tri simple

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void trier()
    {
        int i = 0;

        while (i != l - 1)
        {
            int j = i + 1;

            while (j != l)
            {
                if (tab[i] > tab[j])
                {
                    int stock = tab[i];
                    tab[i] = tab[j];
                    tab[j] = stock;
                }

                j++;
            }

            i++;
        }
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        tableau.trier();
        tableau.afficher();
    }
}

Exercice 12. inverser()​

Énoncé​

Inverser le tableau.

Principe​

On échange :

  • le début avec la fin
  • puis le deuxième avec l'avant-dernier
  • et ainsi de suite

Illustration du principe pour inverser le tableau

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void inverser()
    {
        int i = 0;
        int j = l - 1;

        while (i < j)
        {
            int stock = tab[i];
            tab[i] = tab[j];
            tab[j] = stock;

            i++;
            j--;
        }
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        tableau.inverser();
        tableau.afficher();
    }
}

Exercice 13. insererOrdonner(int element)​

Énoncé​

Insérer un élément dans un tableau tout en gardant l'ordre croissant.

Principe​

On trie d'abord si besoin, puis :

  • on décale vers la droite les éléments plus grands
  • on place la nouvelle valeur au bon endroit

Illustration du principe pour insérer dans l&#39;ordre

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void insererOrdonner(int element)
    {
        if (!estTrie())
        {
            // On trie d'abord, sinon on ne peut pas garantir une insertion au bon endroit.
            trier();
        }

        int i = l - 1;

        while (i != -1 && tab[i] >= element)
        {
            tab[i + 1] = tab[i];
            i = i - 1;
        }

        tab[i + 1] = element;
        l = l + 1;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        tableau.insererOrdonner(15);
        tableau.afficher();
    }
}

Exercice 14. supprimerDansUnePostion(int k)​

Énoncé​

Supprimer l'élément situé à une position donnée.

Principe​

On décale vers la gauche tous les éléments qui suivent cette position.

Illustration du principe pour supprimer à une position

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void supprimerDansUnePostion(int k)
    {
        int i = k;

        while (i < l - 1)
        {
            tab[i] = tab[i + 1];
            i++;
        }

        l = l - 1;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        tableau.ajouterElement(100);
        tableau.supprimerDansUnePostion(2);
        tableau.afficher();
    }
}

Exercice 15. supprimerNonOrdonnerAPosition(int k)​

Énoncé​

Supprimer rapidement un élément à une position donnée, sans se soucier de garder l'ordre.

Principe​

On remplace la case à supprimer par le dernier élément du tableau.

Illustration du principe pour supprimer rapidement

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void supprimerNonOrdonnerAPosition(int k)
    {
        tab[k] = tab[l - 1];
        l = l - 1;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        tableau.ajouterElement(100);
        tableau.supprimerNonOrdonnerAPosition(1);
        tableau.afficher();
    }
}

Exercice 16. suppressionElement(int element)​

Énoncé​

Supprimer un élément par sa valeur.

Principe​

On cherche d'abord sa position, puis on réutilise la suppression par position.

Illustration : chercher puis supprimer

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public void suppressionElement(int element)
    {
        int i = 0;

        while (i != l && tab[i] != element)
        {
            i++;
        }

        if (i != l)
        {
            supprimerDansUnePostion(i);
        }
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        tableau.ajouterElement(10);
        tableau.suppressionElement(9);
        tableau.afficher();
    }
}

Exercice 17. taille()​

Énoncé​

Retourner le nombre d'éléments réellement présents dans le tableau.

Principe​

Ici, la taille utile est déjà stockée dans l.

Illustration de la différence entre l et N

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public int taille()
    {
        return l;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(20);
        tableau.ajouterElement(9);
        Console.WriteLine(tableau.taille());
    }
}

Exercice 18. getElement(int index) et setElement(int index, int valeur)​

Énoncé​

Lire ou modifier un élément à une position donnée.

Principe​

  • getElement retourne la valeur
  • setElement remplace la valeur

Illustration du principe pour lire ou modifier une case

Corrigé​

namespace ConsoleApp2;

public class Tableau
{
    private int[] tab;
    private int l;
    public static int N = 100;
    ...
    public int getElement(int index)
    {
        if (estVide())
        {
            // On arrête ici, car il n'y a aucun élément à lire dans un tableau vide.
            throw new Exception("Tableau vide");
        }

        return tab[index];
    }

    public void setElement(int index, int valeur)
    {
        tab[index] = valeur;
    }
}

Appel dans le programme principal​

Program.cs
using ConsoleApp2;

public class Program
{
    public static void Main()
    {
        Tableau tableau = new Tableau();
        tableau.ajouterElement(10);
        tableau.ajouterElement(9);
        Console.WriteLine(tableau.getElement(0));
        tableau.setElement(0, 20);
        tableau.afficher();
    }
}

Fin du jour 7​

À ce stade, vous avez déjà manipulé beaucoup d'exercices classiques sur les tableaux :

  • test
  • recherche
  • parcours
  • minimum et maximum
  • tri
  • suppression
  • insertion

Prenez le temps de relire plusieurs fois. Quand on débute, refaire les mêmes exercices aide énormément.

Le plus important maintenant est de reconnaître le bon schéma :

  • parcours
  • recherche
  • décalage
  • échange

Autrement dit, dans beaucoup d'exercices, il ne faut pas trop paniquer ni trop compliquer les choses.

Prenez l'habitude de :

  • lire l'énoncé 3 fois calmement
  • vous demander ce que l'on cherche vraiment

Puis posez-vous cette question très simple :

  • est-ce qu'il faut connaître toutes les valeurs du tableau ?
  • ou est-ce qu'il faut seulement trouver une valeur ou une position ?

Si vous avez besoin de lire tout le tableau, pensez d'abord au schéma de parcours. Si vous cherchez seulement un élément précis, pensez d'abord au schéma de recherche.

Nous l'avons déjà vu au jour 4, mais il faut vraiment garder ce réflexe en tête :

  • parcours quand on lit tout
  • recherche quand on cherche quelque chose
  • décalage quand on insère ou supprime
  • échange quand on inverse ou quand on trie