SCRATCH publié le 20/12/2009 - mis à jour le 21/12/2009
Un logiciel pour créer des algorithmes
Autres exemples.
Dans la suite, on part d’un algorithme simple et on l’enrichit progressivement. Les étapes sont :
- Tester si un nombre entier est divisible par un autre nombre entier.
- Etablir la liste des diviseurs d’un nombre entier.
- Faire la somme des diviseurs d’un nombre entier.
- Tester si un nombre entier est parfait ( égal à la somme de ses diviseurs stricts)
Voilà le premier algorithme :
Dans cet algorithme, on a utilisé une instruction spécifique pour entrer les 2 données dont on a besoin.
Cette instruction n’a pas été utilisée dans les exemples précédents, mais aurait pu l’être dans l’algorithme qui construit un polygone de n côtés.
Quand l’algorithme est lancé, il faut répondre aux questions posées et valider, pour que l’algorithme continue son travail.
Si réaliser un tel algorithme vous semble une tâche trop difficile pour les élèves, on peut imaginer de leur donner tout ou une partie des briques , en désordre, et leur demander de les remettre dans l’ordre.
On peut par exemple leur donner l’image suivante, puis lui les laisser se débrouiller pour construire l’algorithme. Beaucoup mêleront réflexion et progression par essais-erreurs.
Il faut reconnaître cependant que réaliser un tel travail pour tester la divisibilité d’un entier par un autre n’est pas très utile s’il n’y a pas de prolongement envisagé. En effet pour faire ce test, une simple calculatrice suffit, ou même un papier et un crayon si l’on est courageux.
Il faut donc faire évoluer cet algorithme vers la deuxième étape, la recherche de tous les diviseurs d’un entier. Cela pourra permettre par exemple d’aborder sereinement une des activités ( page 14) du document d’accompagnement des programmes sur les fonctions.
On obtient l’algorithme suivant :
Cet algorithme nécessite la création d’une liste capable de stocker tous les diviseurs du nombre choisi, au fur et à mesure qu’ils sont trouvés.
Bien sûr, il nécessite aussi une boucle pour réaliser le même calcul répétitif, mais c’est là tout l’intérêt de faire un algorithme.
On peut maintenant s’intéresser à la somme des diviseurs. Faire évoluer l’algorithme précédent vers celui-ci nécessite la création d’une nouvelle variable, »somme » . En revanche, on peut supprimer la liste si on n’a plus besoin des diviseurs mais seulement de leur somme.
On obtient ce qui suit :
Depuis très longtemps, les mathématiciens se sont intéressés aux entiers qui étaient égaux à la somme de leurs diviseurs propres, tel 6=1+2+3 qui est le plus petit entier à posséder cette propriété.
Ces entiers sont qualifiés de parfait. Personne n’a encore prouvé si l’ensemble des entiers parfaits est fini ou infini, ni s’il existe un entier parfait impair.
Il est naturel, et c’est un travail facile, de faire évoluer l’algorithme précédent pour qu’il devienne un test pour savoir si un entier est parfait ou non.
Il suffira de rajouter un bloc d’instruction à la fin de l’algorithme précédent pour un bonne présentation des résultats, et de modifier une borne de la boucle.
On obtient :
Un dernier prolongement souhaitable serait de rechercher tous les entiers parfaits jusqu’à 1000 ou 10000. Il est alors indispensable d’améliorer l’ algorithme précédent afin de diminuer le nombre d’opérations. Certains pourront s’y essayer mais j’ai constaté là les limites de SCRATCH(voir fichier joint).
Pas de partie entière, mais surtout une lenteur extrême pour les calculs.
Pour obtenir les 3 entiers parfaits inférieurs à 500, SCRATCH demande 3 minutes de calcul et plus d’une heure pour obtenir le 4ème.
En faisant le même programme avec Algobox, j’ai obtenu les 4 premiers entiers parfaits(6 ;28 ;496 ;8128) en 3s.
algorithme en scratch qui trouve les diviseurs d’un entier
Algorithme en scratch qui fait la liste des entiers parfaits jusqu’à 500.
Algorithme en Scratch qui dessine un polygone régulier de n côtés.
Teste si un entier est parfait
algorithme en scratch qui teste si un entier divise un autre entier.