يقدم موقعنا تمارين مصححة في لغات البرمجة مثل C / C ++ و PHP
abdelouafi
Administrator
إذا كنت ترغب في مشاهدة الصور ، يرجى النقر عليها
Blog
SUIVEZ NOTRE CHAINE YOUTUBE: قم بالتسجيل في قناتنا عبر هذا الرابط https://www.youtube.com/channel/UCCITRMWPcElh-96wCS3EyUg
devoir 1 math tronc commun
مجموعة من دروس و فروض جميع المستويات
دروس الإعدادي - دروس الثانوي الثأهيلي - دروس التعليم الابتدائي - فروض مختلف المستويات الدراسيةفضلا و ليس أمرا شارك هذه الصفحة مع أصدقائك:
Une affaire à trier
Le tri d'un tableau consiste à organiser tous les éléments du tableau dans un ordre particulier. Il peut être utile de trier un tableau dans de nombreux cas différents. Par exemple, votre programme de messagerie affiche généralement les e-mails dans l'ordre chronologique, car les e-mails les plus récents sont généralement considérés comme plus pertinents. Lorsque vous accédez à votre liste de contacts, les noms sont généralement classés par ordre alphabétique, car il est plus facile de trouver le nom que vous recherchez. Ces deux présentations impliquent le tri des données avant la présentation.
Le tri d'un tableau peut rendre la recherche dans un tableau plus efficace, non seulement pour les humains, mais également pour les ordinateurs. Par exemple, considérons le cas où nous voulons savoir si un nom apparaît dans une liste de noms. Afin de voir si un nom était dans la liste, nous devrions vérifier chaque élément du tableau pour voir si le nom apparaît. Pour un tableau contenant de nombreux éléments, la recherche à travers eux peut être coûteuse.
Cependant, supposons maintenant que notre tableau de noms soit trié par ordre alphabétique. Dans ce cas, il suffit de chercher jusqu'au point où nous rencontrons un nom alphabétiquement plus grand que celui que nous recherchons. À ce stade, si nous ne trouvons pas le nom, nous savons qu’il n’existe pas dans le reste du tableau, car tous les noms que nous n’avons pas vus dans le tableau ont la garantie d’être alphabétiquement supérieurs!
Il s'avère qu'il existe encore de meilleurs algorithmes pour rechercher des tableaux triés. En utilisant un algorithme simple, nous pouvons rechercher un tableau trié contenant 1 000 000 éléments en utilisant seulement 20 comparaisons! Bien sûr, l’inconvénient est que le tri d’un tableau coûte relativement cher et qu’il n’est souvent pas utile de trier un tableau pour accélérer la recherche, à moins que vous ne le fassiez plusieurs fois.
Dans certains cas, trier un tableau peut rendre inutile la recherche. Prenons un autre exemple où nous voulons trouver le meilleur score au test. Si le tableau n'est pas trié, nous devons examiner chaque élément du tableau pour trouver le meilleur score au test. Si la liste est triée, le meilleur score de test sera dans la première ou la dernière position (selon que nous avons trié par ordre croissant ou décroissant), nous n’avons donc pas besoin de chercher du tout!
Comment fonctionne le tri
Le tri est généralement effectué en comparant de manière répétée des paires d’éléments de tableau et en les échangeant si elles répondent à certains critères prédéfinis. L'ordre dans lequel ces éléments sont comparés diffère selon l'algorithme de tri utilisé. Les critères dépendent de la manière dont la liste sera triée (par exemple, par ordre croissant ou décroissant).
Pour échanger deux éléments, nous pouvons utiliser la fonction std :: swap () de la bibliothèque standard C ++, définie dans l'en-tête de l'algorithme. Pour des raisons d'efficacité, std :: swap () a été déplacé vers l'en-tête de l'utilitaire dans C ++ 11.
Ce programme imprime:
Before swap: x = 2, y = 4
After swap: x = 4, y = 2
Notez qu'après l'échange, les valeurs de x et y ont été échangées!
Tri de sélection
Il y a plusieurs façons de trier un tableau. Le type de sélection est probablement le type le plus facile à comprendre, ce qui en fait un bon candidat pour l'enseignement, même s'il fait partie des types les plus lents.
Le tri par sélection effectue les étapes suivantes pour trier un tableau du plus petit au plus grand:
1) À partir de l'index de tableau 0, recherchez dans le tableau entier pour trouver la plus petite valeur.
2) Échangez la plus petite valeur trouvée dans le tableau avec la valeur à l'index 0
3) Répétez les étapes 1 et 2 à partir de l'index suivant
En d’autres termes, nous allons trouver le plus petit élément du tableau et l’échanger dans la première position. Ensuite, nous allons trouver le prochain élément le plus petit et l’échanger en deuxième position. Ce processus sera répété jusqu'à ce que nous manquions d'éléments.
Voici un exemple de cet algorithme travaillant sur 5 éléments. Commençons par un exemple de tableau:
{30, 50, 20, 10, 40}
Tout d'abord, nous trouvons le plus petit élément, à partir de l'indice 0:
{30, 50, 20, 10, 40}
Nous échangeons ensuite ceci avec l'élément d'indice 0:
{10, 50, 20, 30, 40}
Maintenant que le premier élément est trié, nous pouvons l'ignorer. Maintenant, nous trouvons le plus petit élément, à partir de l'index 1:
{10, 50, 20, 30, 40}
Et échangez-le avec l'élément de l'index 1:
{10, 20, 50, 30, 40}
Nous pouvons maintenant ignorer les deux premiers éléments. Trouvez le plus petit élément à partir de l'index 2:
{10, 20, 50, 30, 40}
Et échangez-le avec l'élément de l'index 2:
{10, 20, 30, 50, 40}
Trouvez le plus petit élément à partir de l'index 3:
{10, 20, 30, 50, 40}
Et échangez-le avec l'élément de l'index 3:
{10, 20, 30, 40, 50}
Enfin, trouvez le plus petit élément à partir de l’indice 4:
{10, 20, 30, 40, 50}
Et échangez-le avec l'élément de l'index 4 (ce qui ne fait rien):
{10, 20, 30, 40 50}
Terminé!
{10, 20, 30, 40, 50}
Notez que la dernière comparaison sera toujours avec lui-même (ce qui est redondant), nous pouvons donc arrêter 1 élément avant la fin du tableau.
Tri de sélection en C ++
Voici comment cet algorithme est implémenté en C ++:
La partie la plus déroutante de cet algorithme est la boucle à l'intérieur d'une autre boucle (appelée boucle imbriquée). La boucle extérieure (startIndex) parcourt chaque élément un à un. Pour chaque itération de la boucle externe, la boucle interne (currentIndex) est utilisée pour rechercher le plus petit élément du tableau restant (à partir de startIndex + 1). smallestIndex garde la trace de l'index du plus petit élément trouvé par la boucle interne. Ensuite, smallestIndex est échangé avec startIndex. Enfin, la boucle externe (startIndex) avance d'un élément et le processus est répété.
Conseil: Si vous rencontrez des difficultés pour comprendre le fonctionnement du programme ci-dessus, il peut être utile d’examiner un exemple de cas sur une feuille de papier. Ecrivez les éléments de tableau de départ (non triés) horizontalement en haut du papier. Dessinez des flèches indiquant quels éléments sont indexés par startIndex, currentIndex et smallestIndex. Tracer manuellement à travers le programme et redessiner les flèches au fur et à mesure que les index changent. Pour chaque itération de la boucle externe, démarrez une nouvelle ligne indiquant l'état actuel du tableau.
Le tri des noms fonctionne avec le même algorithme. Il suffit de changer le type de tableau d'Int à std :: string et de l'initialiser avec les valeurs appropriées.
std :: sort
Le tri des tableaux étant si courant, la bibliothèque standard C ++ inclut une fonction de tri nommée std :: sort. std :: sort réside dans l'en-tête <algorithm> et peut être invoqué sur un tableau comme ceci:
Nous parlerons davantage de std :: sort dans un prochain chapitre.
Quiz
1) Montre manuellement le fonctionnement du tri par sélection sur le tableau suivant: {30, 60, 20, 50, 40, 10}. Affiche le tableau après chaque échange effectué.
2) Réécrivez le code de tri de sélection ci-dessus pour trier par ordre décroissant (les plus grands nombres en premier). Bien que cela puisse sembler complexe, c'est en fait étonnamment simple.
3) Celui-ci va être difficile, alors mettez votre visage de jeu dessus.
Un autre type simple est appelé "type de bulle". Le tri à bulles fonctionne en comparant des paires d'éléments adjacentes et en les échangeant si les critères sont remplis, de sorte que les éléments «bouillonnent» jusqu'à la fin du tableau. Bien qu’il existe de nombreuses façons d’optimiser le tri par bulle, dans ce questionnaire, nous allons nous en tenir à la version non optimisée, car elle est la plus simple.
Le tri par bulle non optimisé effectue les étapes suivantes pour trier un tableau du plus petit au plus grand:
A) Comparez l'élément de tableau 0 avec l'élément de tableau 1. Si l'élément 0 est plus grand, échangez-le avec l'élément 1.
B) Faites maintenant la même chose pour les éléments 1 et 2, et pour chaque paire d'éléments suivante, jusqu'à ce que vous atteigniez la fin du tableau. À ce stade, le dernier élément du tableau sera trié.
C) Répétez les deux premières étapes jusqu'à ce que le tableau soit trié.
Écrivez le code qui bulle trie le tableau suivant selon les règles ci-dessus:
Imprimez les éléments du tableau trié à la fin de votre programme.
Astuce: Si nous sommes en mesure de trier un élément par itération, cela signifie que nous aurons besoin de répéter autant de fois qu'il y a de nombres dans notre tableau pour garantir que tout le tableau est trié.
Conseil: lorsque vous comparez des paires d’éléments, faites attention à la plage de votre tableau.
4) Ajoutez deux optimisations à l'algorithme de tri à bulle que vous avez écrit dans la question précédente du quiz:
Votre sortie devrait correspondre à ceci:
Early termination on iteration 6
1 2 3 4 5 6 7 8 9
Le tri d'un tableau consiste à organiser tous les éléments du tableau dans un ordre particulier. Il peut être utile de trier un tableau dans de nombreux cas différents. Par exemple, votre programme de messagerie affiche généralement les e-mails dans l'ordre chronologique, car les e-mails les plus récents sont généralement considérés comme plus pertinents. Lorsque vous accédez à votre liste de contacts, les noms sont généralement classés par ordre alphabétique, car il est plus facile de trouver le nom que vous recherchez. Ces deux présentations impliquent le tri des données avant la présentation.
Le tri d'un tableau peut rendre la recherche dans un tableau plus efficace, non seulement pour les humains, mais également pour les ordinateurs. Par exemple, considérons le cas où nous voulons savoir si un nom apparaît dans une liste de noms. Afin de voir si un nom était dans la liste, nous devrions vérifier chaque élément du tableau pour voir si le nom apparaît. Pour un tableau contenant de nombreux éléments, la recherche à travers eux peut être coûteuse.
Cependant, supposons maintenant que notre tableau de noms soit trié par ordre alphabétique. Dans ce cas, il suffit de chercher jusqu'au point où nous rencontrons un nom alphabétiquement plus grand que celui que nous recherchons. À ce stade, si nous ne trouvons pas le nom, nous savons qu’il n’existe pas dans le reste du tableau, car tous les noms que nous n’avons pas vus dans le tableau ont la garantie d’être alphabétiquement supérieurs!
Il s'avère qu'il existe encore de meilleurs algorithmes pour rechercher des tableaux triés. En utilisant un algorithme simple, nous pouvons rechercher un tableau trié contenant 1 000 000 éléments en utilisant seulement 20 comparaisons! Bien sûr, l’inconvénient est que le tri d’un tableau coûte relativement cher et qu’il n’est souvent pas utile de trier un tableau pour accélérer la recherche, à moins que vous ne le fassiez plusieurs fois.
Dans certains cas, trier un tableau peut rendre inutile la recherche. Prenons un autre exemple où nous voulons trouver le meilleur score au test. Si le tableau n'est pas trié, nous devons examiner chaque élément du tableau pour trouver le meilleur score au test. Si la liste est triée, le meilleur score de test sera dans la première ou la dernière position (selon que nous avons trié par ordre croissant ou décroissant), nous n’avons donc pas besoin de chercher du tout!
Comment fonctionne le tri
Le tri est généralement effectué en comparant de manière répétée des paires d’éléments de tableau et en les échangeant si elles répondent à certains critères prédéfinis. L'ordre dans lequel ces éléments sont comparés diffère selon l'algorithme de tri utilisé. Les critères dépendent de la manière dont la liste sera triée (par exemple, par ordre croissant ou décroissant).
Pour échanger deux éléments, nous pouvons utiliser la fonction std :: swap () de la bibliothèque standard C ++, définie dans l'en-tête de l'algorithme. Pour des raisons d'efficacité, std :: swap () a été déplacé vers l'en-tête de l'utilitaire dans C ++ 11.
Code:
#include <algorithm> // for std::swap, use <utility> instead if C++11
#include <iostream>
int main()
{
int x = 2;
int y = 4;
std::cout << "Before swap: x = " << x << ", y = " << y << '\n';
std::swap(x, y); // swap the values of x and y
std::cout << "After swap: x = " << x << ", y = " << y << '\n';
}Ce programme imprime:
Before swap: x = 2, y = 4
After swap: x = 4, y = 2
Notez qu'après l'échange, les valeurs de x et y ont été échangées!
Tri de sélection
Il y a plusieurs façons de trier un tableau. Le type de sélection est probablement le type le plus facile à comprendre, ce qui en fait un bon candidat pour l'enseignement, même s'il fait partie des types les plus lents.
Le tri par sélection effectue les étapes suivantes pour trier un tableau du plus petit au plus grand:
1) À partir de l'index de tableau 0, recherchez dans le tableau entier pour trouver la plus petite valeur.
2) Échangez la plus petite valeur trouvée dans le tableau avec la valeur à l'index 0
3) Répétez les étapes 1 et 2 à partir de l'index suivant
En d’autres termes, nous allons trouver le plus petit élément du tableau et l’échanger dans la première position. Ensuite, nous allons trouver le prochain élément le plus petit et l’échanger en deuxième position. Ce processus sera répété jusqu'à ce que nous manquions d'éléments.
Voici un exemple de cet algorithme travaillant sur 5 éléments. Commençons par un exemple de tableau:
{30, 50, 20, 10, 40}
Tout d'abord, nous trouvons le plus petit élément, à partir de l'indice 0:
{30, 50, 20, 10, 40}
Nous échangeons ensuite ceci avec l'élément d'indice 0:
{10, 50, 20, 30, 40}
Maintenant que le premier élément est trié, nous pouvons l'ignorer. Maintenant, nous trouvons le plus petit élément, à partir de l'index 1:
{10, 50, 20, 30, 40}
Et échangez-le avec l'élément de l'index 1:
{10, 20, 50, 30, 40}
Nous pouvons maintenant ignorer les deux premiers éléments. Trouvez le plus petit élément à partir de l'index 2:
{10, 20, 50, 30, 40}
Et échangez-le avec l'élément de l'index 2:
{10, 20, 30, 50, 40}
Trouvez le plus petit élément à partir de l'index 3:
{10, 20, 30, 50, 40}
Et échangez-le avec l'élément de l'index 3:
{10, 20, 30, 40, 50}
Enfin, trouvez le plus petit élément à partir de l’indice 4:
{10, 20, 30, 40, 50}
Et échangez-le avec l'élément de l'index 4 (ce qui ne fait rien):
{10, 20, 30, 40 50}
Terminé!
{10, 20, 30, 40, 50}
Notez que la dernière comparaison sera toujours avec lui-même (ce qui est redondant), nous pouvons donc arrêter 1 élément avant la fin du tableau.
Tri de sélection en C ++
Voici comment cet algorithme est implémenté en C ++:
Code:
#include <algorithm> // for std::swap, use <utility> instead if C++11
#include <iostream>
int main()
{
const int length = 5;
int array[length] = { 30, 50, 20, 10, 40 };
// Step through each element of the array
// (except the last one, which will already be sorted by the time we get there)
for (int startIndex = 0; startIndex < length - 1; ++startIndex)
{
// smallestIndex is the index of the smallest element we’ve encountered this iteration
// Start by assuming the smallest element is the first element of this iteration
int smallestIndex = startIndex;
// Then look for a smaller element in the rest of the array
for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex)
{
// If we've found an element that is smaller than our previously found smallest
if (array[currentIndex] < array[smallestIndex])
// then keep track of it
smallestIndex = currentIndex;
}
// smallestIndex is now the smallest element in the remaining array
// swap our start element with our smallest element (this sorts it into the correct place)
std::swap(array[startIndex], array[smallestIndex]);
}
// Now that the whole array is sorted, print our sorted array as proof it works
for (int index = 0; index < length; ++index)
std::cout << array[index] << ' ';
return 0;
}La partie la plus déroutante de cet algorithme est la boucle à l'intérieur d'une autre boucle (appelée boucle imbriquée). La boucle extérieure (startIndex) parcourt chaque élément un à un. Pour chaque itération de la boucle externe, la boucle interne (currentIndex) est utilisée pour rechercher le plus petit élément du tableau restant (à partir de startIndex + 1). smallestIndex garde la trace de l'index du plus petit élément trouvé par la boucle interne. Ensuite, smallestIndex est échangé avec startIndex. Enfin, la boucle externe (startIndex) avance d'un élément et le processus est répété.
Conseil: Si vous rencontrez des difficultés pour comprendre le fonctionnement du programme ci-dessus, il peut être utile d’examiner un exemple de cas sur une feuille de papier. Ecrivez les éléments de tableau de départ (non triés) horizontalement en haut du papier. Dessinez des flèches indiquant quels éléments sont indexés par startIndex, currentIndex et smallestIndex. Tracer manuellement à travers le programme et redessiner les flèches au fur et à mesure que les index changent. Pour chaque itération de la boucle externe, démarrez une nouvelle ligne indiquant l'état actuel du tableau.
Le tri des noms fonctionne avec le même algorithme. Il suffit de changer le type de tableau d'Int à std :: string et de l'initialiser avec les valeurs appropriées.
std :: sort
Le tri des tableaux étant si courant, la bibliothèque standard C ++ inclut une fonction de tri nommée std :: sort. std :: sort réside dans l'en-tête <algorithm> et peut être invoqué sur un tableau comme ceci:
Code:
#include <algorithm> // for std::sort
#include <iostream>
int main()
{
const int length = 5;
int array[length] = { 30, 50, 20, 10, 40 };
std::sort(array, array+length);
for (int i=0; i < length; ++i)
std::cout << array[i] << ' ';
return 0;
}Nous parlerons davantage de std :: sort dans un prochain chapitre.
Quiz
1) Montre manuellement le fonctionnement du tri par sélection sur le tableau suivant: {30, 60, 20, 50, 40, 10}. Affiche le tableau après chaque échange effectué.
2) Réécrivez le code de tri de sélection ci-dessus pour trier par ordre décroissant (les plus grands nombres en premier). Bien que cela puisse sembler complexe, c'est en fait étonnamment simple.
3) Celui-ci va être difficile, alors mettez votre visage de jeu dessus.
Un autre type simple est appelé "type de bulle". Le tri à bulles fonctionne en comparant des paires d'éléments adjacentes et en les échangeant si les critères sont remplis, de sorte que les éléments «bouillonnent» jusqu'à la fin du tableau. Bien qu’il existe de nombreuses façons d’optimiser le tri par bulle, dans ce questionnaire, nous allons nous en tenir à la version non optimisée, car elle est la plus simple.
Le tri par bulle non optimisé effectue les étapes suivantes pour trier un tableau du plus petit au plus grand:
A) Comparez l'élément de tableau 0 avec l'élément de tableau 1. Si l'élément 0 est plus grand, échangez-le avec l'élément 1.
B) Faites maintenant la même chose pour les éléments 1 et 2, et pour chaque paire d'éléments suivante, jusqu'à ce que vous atteigniez la fin du tableau. À ce stade, le dernier élément du tableau sera trié.
C) Répétez les deux premières étapes jusqu'à ce que le tableau soit trié.
Écrivez le code qui bulle trie le tableau suivant selon les règles ci-dessus:
Code:
const int length(9);
int array[length] = { 6, 3, 2, 9, 7, 1, 5, 4, 8 };Imprimez les éléments du tableau trié à la fin de votre programme.
Astuce: Si nous sommes en mesure de trier un élément par itération, cela signifie que nous aurons besoin de répéter autant de fois qu'il y a de nombres dans notre tableau pour garantir que tout le tableau est trié.
Conseil: lorsque vous comparez des paires d’éléments, faites attention à la plage de votre tableau.
4) Ajoutez deux optimisations à l'algorithme de tri à bulle que vous avez écrit dans la question précédente du quiz:
- Remarquez qu'à chaque itération de type bulle, le plus grand nombre restant est bouillonné jusqu'à la fin du tableau. Après la première itération, le dernier élément du tableau est trié. Après la deuxième itération, l’avant-dernier élément du tableau est également trié. Et ainsi de suite… À chaque itération, nous n’avons pas besoin de revérifier les éléments que nous savons déjà triés. Changez votre boucle pour ne pas revérifier les éléments déjà triés.
- Si nous effectuons une itération complète sans effectuer d'échange, nous savons que le tableau doit déjà être trié. Implémentez une vérification pour déterminer si des swaps ont été effectués à cette itération et, dans le cas contraire, terminez la boucle plus tôt. Si la boucle a été terminée tôt, indiquez sur quelle itération le tri s'est terminé tôt.
Votre sortie devrait correspondre à ceci:
Early termination on iteration 6
1 2 3 4 5 6 7 8 9