Calendrier 
Enchaînement d'entiers
Énoncé
Note historique
Les intentions
Fiche professeur
Expérimentation Bibliographie
On considère un nombre entier N compris entre 1 et 100. En partant de N, on construit une chaîne de nombres en respectant les règles suivantes :
1. Si un nombre A de la chaîne est pair, le suivant s’obtient en divisant A par 2.
2. Si un nombre A de la chaîne est impair, le suivant s’obtient en multipliant A par 3 et en ajoutant 1.
3. Si un nombre A de la chaîne dépasse 100, la chaîne est cassée.
4. Si un nombre A de la chaîne est égal à 1, la chaîne est terminée.
Exemples :
– si N=23 on obtient 23-70-35-106 et la chaîne est cassée;
– si N=20 on obtient 20-10-5-16-8-4-2-1 et la chaîne a pour longueur 8.
Quel est l’entier compris entre 1 et 100 qui possède la chaîne (non cassée) la plus longue ?
La conjecture de Syracuse :
Pour tout entier non nul n, la suite de Syracuse associée comprend le nombre 1
Point info
Cette conjecture dont l'origine, vers 1950 reste confuse, porte une
grande variété de noms, provenant de mathématiciens l'ayant étudiée ou
fait connaître : problème de Collatz, problème de Kakutani, problème de
l'algorithme de Hasse, problème d'Ulam. Le nom de conjecture de Syracuse
est lié à l'université de Syracuse, aux USA, où le problème fut étudié.
Kakutani fit circuler le problème et raconte : « Pendant un mois, tout le monde à l'Université
de Yale travailla dessus, sans résultat. Un phénomène semblable se produisit à l'Université de Chicago. Cette énigme,
pensaient certains, avait été avancée par le KGB pour ralentir la recherche mathématique aux Etats-Unis »
(d'après JP Delahaye)
Info : cette conjecture a été vérifiée jusqu'au nombre 3,2 x 1026
- S’approprier un problème dont l’approche est numérique. Construire quelques chaînes (à la main) en partant de nombres entiers compris entre 1 et 100. Noter sa longueur, repérer la plus grande chaîne. - Se familiariser avec des formulations mathématiques en lien avec l’algorithmique et la logique : Si...alors..., faire tant que..., et, ou, , négation de propositions..............
- Ecrire des algorithmes à différents niveaux :
. Algorithme permettant d’afficher les différentes étapes du calcul.
. Algorithme, avec un test, permettant de lire la longueur de la chaîne ;
. Algorithme complet, avec plusieurs tests, permettant de donner la
longueur maximum des chaînes et d’afficher le nombre correspondant.
. Algorithme permettant d’afficher la chaîne la plus longue et sa longueur. En résumé, il s’agit d’aborder ou de réinvestir quelques bases de
l’algorithmique en classe de seconde.
- Traduire des algorithmes simples en programmes en utilisant des tableurs, des calculatrices, des logiciels.
- Analyser des algorithmes.
- Traduire un algorithme en énoncé.
Cette fiche est composée de cinq parties
Partie A : Descriptif
Un descriptif détaillé de la démarche pédagogique envisagée pour l'étude de l'exercice
Enchaînement d'entiers
Démarche progressive présentant, dans chacune des étapes,
un algorithme en langage naturel, sa traduction en programme avec
tableur, avec une calculatrice, avec Scratch.
Il est alors possible de repérer les difficultés de certains élèves
dans les différentes étapes d'élaboration d'algorithmes, permettant
ainsi de proposer l'élaboration d'un algorithme plus adapté.
Les choix de calculatrice ou logiciel sont faits en fonction de la
disponibilité de l'outil ou de sa simplicité d'utilisation par l'élève.
Partie B : Algorithmes
Trois encadrés présentant des algorithmes en langage naturel sont proposés.
Les objectifs :
- Comprendre et analyser un algorithme préexistant
- Analyser la situation : identifier les données d'entrées, de sorties, le traitement.
- Valider la solution algorithmique par des traces d'exécution et de jeux d'essais simples.
A la recherche d'un énoncé.
Étudiez ces algorithmes.
Proposez un énoncé d'exercice dont l'algorithme est celui proposé.
Partie C : Organigramme
Présentation d'un algorithme sous forme d'organigramme.
Un organigramme est une représentation graphique conventionnelle d'un algorithme.
Très « mode » il y a une trentaine d'année, ils sont aujourd'hui remis en question.
(Tangente Hors série n°37 : Les algorithmes par Michel Rousselet)
Voici deux organigrammes correspondant au problème posé.
Il s'agit de traduire ces organigrammes en langage naturel.
Partie D : Programmes sur calculatrices
Les différentes étapes proposées dans la partie A sont programmées sur TI et sur Casio 35+
Partie E : Programme sur tableur
L'étape finale de la partie A est programmée sur tableur.
L'énoncé proposé, à cette classe de seconde, est celui du rallye mathématique de Franche-Comté (expérimentation mai 2003)
Cette étude nous a permis de repérer quelques difficultés liées à la formulation de l'énoncé (autre énoncé au début du document)
Enchaînement d'entiers
On considère un entier n compris entre 2 et 99.
En partant de n , on construit une chaîne de nombres de la façon suivante :
- si un nombre k de la chaîne est pair, le suivant s'obtient en k par 2,
- si le nombre k de la chaîne est impair, le suivant s'obtient en multipliant k par 3 et en ajoutant 1.
La longueur de la chaîne est le nombre d'entiers nécessaires pour atteindre le nombre 1.
Exemple en prenant n = 20 : 20-10-5-16-8-4-2-1 est une chaîne de longueur 8.
Attention, les nombres utilisés dans chaque chaîne ne peuvent s'écrire qu'avec 1 ou 2 chiffres.
Quel est le nombre compris entre 2 et 99 qui possède la chaîne la plus longue ?
Donnez sa chaîne complète.
-Bulletin vert APMEP n° 485 Pour un enseignement de l'informatique dans le secondaire.
Jean-Pierre Archambault et Gilles Dowek.
-Bulletin vert APMEP n° 485 Algorithmique en seconde au fil du Net
Gérard Kuntz
- http://www.pise.info/algo/introduction.htm
- http://dhenin2.free.fr/AlgoSeconde/AlgoSeconde.html
- http://eduscol.education.fr/D0015/
- http://www.irem.univ-mrs.fr
Algorithmes et logique au lycée - Octobre 2009
- http://eduscol.education.fr/D0015/
- http://fr.wikipedia.org/wiki/Logique
-Tangente Hors série n°37