Listons ! Listons !
Les manipulations de listes de données sont un grand thème classique d'algorithmique. Qu'il s'agisse de les remplir, de les vider, d'y chercher des éléments, de les trier ou de les structurer.
On a pas seulement un exigence de terminaison (est-ce que le programme se termine, est-ce qu'il ne tourne pas en rond à l'infini) et de correction (est-ce qu'il fait toujours bien ce qu'on lui demande, est-ce que ses résultats sont corrects) de l'algorithme, mais également de performance puisque ces listes peuvent être très longues (coûteuses en espace mémoire) et donc leur manipulation très coûteuses en temps.
Même si on commence à avoir des réponses efficaces pour la plupart de ces problèmes, la recherche se poursuit. Signalons au passage que vous traitez sans doute déjà de nombreuses listes (pas forcément informatiques ou numériques) au quotidien. Les activités débranchées sont d'ailleurs un excellent moyen de découvrir ces principes algorithmiques avant de se lancer dans la programmation.
Cherchons !
Comment retrouver un élément dans une liste, obtenir son numéro de rang ou même juste savoir s'il est ou non dans la liste ?
Comme vous l'avez déjà vu, il existe deux blocs qui peuvent être utilisés :
Nous allons voir comment écrire les algorithmes cachés dans ces blocs et nous imaginerons des blocs qui n'existent pas dans Scratch mais dont nous pourrions avoir besoin.
Créez une liste uneListe et reproduisez le programme suivant.
Lancez-le et vérifiez que la liste contient bien 1000 éléments (en l'affichant sur la scène).
Créez ensuite une variable nombre recherché. Modifiez son affichage sur la scène pour avoir une barre de défilement . Utilisez la barre pour constater le minimum et maximum disponibles. Normalement, vous devriez avoir un interval de 0 à 100
Prenez le nombre que vous voulez (si vous n'en voulez aucun prenez 42) avec cette barre de défilement.
Remplacer le bloc "... contient ..."
Question⚓
Faites maintenant un programme qui vérifie si nombre recherché est bien présent dans uneListe quand on clique sur le Scratch. Sans utiliser les blocs vus plus haut bien entendu, mais ceux ci-dessous.
Il faut bien entendu tester les deux cas : un nombre qui est bien dans la liste et un nombre qui n'y est pas.
Remplacer le bloc "élément # de ... dans ..."
Question⚓
Faites ensuite un programme qui indique le rang de la première occurrence de nombre recherché. Si nombre recherché n'est pas dans la liste, la valeur finale de rang doit être 0. Vous avez besoin d'au minimum 3 blocs supplémentaires. Mais la structure reste la même que la précédente solution.
Trouver le nombre d'occurrences d'un élément dans une liste.
Question⚓
Pour terminer la préparation avant la fiche d'activité, nous allons maintenant chercher le nombre d'occurrences d'un nombre dans cette liste en cliquant cette fois sur la lettre n. Nous pouvons pour cela, échanger le bloc "répéter jusqu'à ce que..." par un bloc "répéter ... fois", puisqu'il faut absolument "scanner" TOUS les éléments de la liste et non pas s'arrêter au premier que l'on trouve. Utilisez une nouvelle variable nb pour cela.
On vous laisse maintenant toute liberté pour vérifier avec un tableur par exemple que la fonction "nombre aléatoire" fonctionne correctement d'un point de vue statistique. Avec une liste initiale de 100 000 nombres, vous devriez commencer à voir le temps passer pour les calculs. Nous pourrions optimiser ces calculs si cette liste était ordonnée, mais cela fera sans doute partie des futures leçons.
Passez ensuite aux fiches d'activité 6.