Tri de cartes – 2
Énoncé :
Battre les 13 cartes de la même couleur. Choisir au hasard 7, puis 10 cartes parmi ces 13 cartes et les placer face cachée sur une grille avec 10 cases. Dans chaque jeu ci-dessous, trier les cartes en utilisant les trois opérations suivantes qui sont les seules autorisées :
- prendre deux cartes ;
- comparer les deux cartes et les mettre dans l’ordre ;
- reposer les cartes, face cachée, sur les cases vides.
Jeu 1 (individuel). Effectuer les actions que vous pensez nécessaires pour trier les cartes. Le nombre de coups n’est pas limité. La partie est gagnée si les cartes sont triées.
Jeu 2 (en binôme). Donner les instructions, correspondant aux trois opérations autorisées, à votre camarade qui ne peut que formellement exécuter les commandes sans vous montrer les cartes retournées. Quand vous pensez que les cartes sont triées, dites « stop ». Retournez les cartes pour vérifier. La partie est gagnée si les cartes sont triées.
Jeu 3 (en groupe). Donner les instructions, correspondant aux trois opérations autorisées, à trois (ou plus) camarades qui n’exécutent que formellement les commandes en même temps sans vous montrer les cartes retournées. Quand vous pensez que les cartes sont triées, dites « stop ». Retournez les cartes de tous les camarades pour vérifier. La partie est gagnée si les cartes de tous sont triées.Jeu 4 (en groupe ou en classe entière). Donner les instructions pour trier les cartes de vos camarades en même temps selon des règles du jeu 3 avec le moins de comparaisons possibles. Quand vous pensez que les cartes sont triées, dites « stop ». La partie est gagnée si les cartes de tous sont triées.
Matériel nécessaire : Jeux de cartes, grilles de 10 cases, fiches élève
Objectifs et notions ciblées :
Contenu : Notion d’algorithme, tri par insertion, tri par sélection, tri à bulles, tri cocktail.
Capacités attendues : Écrire un algorithme de tri. Étudier la complexité au pire d’un algorithme de tri. Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection.
Commentaires: La terminaison de ces algorithmes est à justifier. On montre que leur coût est quadratique dans le pire des cas.
Prérequis : Connaître les valeurs des cartes.
Domaine : Algorithmique
Cycle : Lycée
Classe(s) : 1ère, Term (Spé NSI)
Auteur(s) / Autrice(s) : Maryna Rafalska
Mots clés :
- Algorithme
- Algorithme de tri
- Complexité d’un algorithme
- Pattern
- Preuve d’un algorithme
- Tri par insertion
- Tri par sélection
Aucun format disponible.
Besoin d'une aide technique ?
Vous rencontrez des soucis sur la plateforme ? Contactez notre support technique pour une assistance rapide et efficace.
Vers le support technique