Bonsoir à tous! Je suis en 1ère S et j'ai actuellement un petit problème sur un DM que je dois rendre pour la semaine prochaine, dans lequel on nous demande d'écrire un algorithme pour résoudre la suite de Syracuse sur Algobox. Voici le sujet:
La suite de Syracuse d'un nombre entier N est définie par récurrence, de la manière suivante:
u0=N et pour tout entier N≥0:
un+1=un/2 si un est pair
un+1= 3un+1 si un est impair
La conjecture affirme que, pour tout N>0, il existe un indice n tel que un=1.
(Ensuite ce sont des exemples qui permettent de vérifier que notre algorithme est correct)
On définit alors:
- le temps de vol: c'est le plus petit indice tel que un=1
Il est par exemple de 17 pour la suite de Syracuse 15-> u17=1
- le temps de vol en altitude: c'est le plus petit indice n tel que un+1<u0
Il est par exemple de 10 pour la suite de Syracuse 15-> u11=10<15 donc n+1=11->n=10
- L'altitude maximale: c'est la valeur maximale de la suite, elle est par exemple de 160 pour la suite de Syracuse 15->u7=160
Ecrire un algorithme (sur ALGOBOX) qui affiche:
1) La liste de tous les termes de la suite de Syracuse pour une valeur N choisie en entrée
2) Le temps de vol
3) Le temps de vol en altitude
4) L'altitude maximale
Vous vous efforcerez de soigner et de personnaliser la présentation des résultats en sortie de cet algorithme.
Voilà l'énoncé, il est temps d'annoncer mon problème: en fait, tout est bon pour le temps de vol et l'altitude maximale, mais le temps de vol en altitude ne correspond pas. La partie sur le temps de vol en altitude ressemble à ça dans mon algorithme actuel:
Si (U>P) alors
Début si
T prend la valeur T+1
Fin si
Et ça ne fonctionne pas, je trouve toujours le résultat demandé plus un, par exemple 11 au lieu de 10, etc
Quelqu'un aurait-il la solution à mon problème s'il vous plaît? Je vous remercie d'avance de prendre le temps de lire et de répondre à mon sujet.
Bonjour,
Le sujet a déjà été en Python sur le forum :
https://www.ilemaths.net/sujet-python-programme-de-syracuse-772933.html
Si ça peut t'aider à débugger ton script
bonjour,
quel conseil !!
bidouiller un résultat pour avoir celui qu'on attend sans comprendre pourquoi ...
je suppose que c'était "de l'humour"
en tout cas on ne peut pas répondre autre chose sans connaitre le reste de l'algo ...
comme c'est de l'Algobox, ça ne coute pas cher de faire un copier-coller direct
- soit à partir du mode "éditeur" de Algobox
- soit à partir d'un fichier "exporté en texte"
Voici l'algorithme, merci pour vos réponses!
FONCTIONS_UTILISEES
VARIABLES
U EST_DU_TYPE NOMBRE
I EST_DU_TYPE NOMBRE
T EST_DU_TYPE NOMBRE
N EST_DU_TYPE NOMBRE
A EST_DU_TYPE NOMBRE
P EST_DU_TYPE NOMBRE
M EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE A
U PREND_LA_VALEUR A
AFFICHER "U("
AFFICHER "0"
AFFICHER ")="
AFFICHER* U
P PREND_LA_VALEUR U
M PREND_LA_VALEUR U
I PREND_LA_VALEUR 0
T PREND_LA_VALEUR 0
N PREND_LA_VALEUR 0
TANT_QUE (U!=1) FAIRE
DEBUT_TANT_QUE
SI (U%==0) ALORS
DEBUT_SI
U PREND_LA_VALEUR U/2
FIN_SI
SINON
DEBUT_SINON
U PREND_LA_VALEUR 3*U+1
FIN_SINON
N PREND_LA_VALEUR N+1
AFFICHER "U("
AFFICHER N
AFFICHER ")="
AFFICHER* U
I PREND_LA_VALEUR I+1
SI (U>P) ALORS
DEBUT_SI
T PREND_LA_VALEUR T+1
FIN_SI
SI (U>M) ALORS
DEBUT_SI
M PREND_LA_VALEUR U
FIN_SI
FIN_TANT_QUE
AFFICHER "Temps de vol: I="
AFFICHER* I
AFFICHER "Temps de vol en altitude: T="
AFFICHER* T
AFFICHER "Altitude maximale: M="
AFFICHER* M
FIN_ALGORITHME
ton calcul de T ne correspond pas à la définition de l'énoncé
tu calcules le nombre d'éléments qui sont > U0
et pas le plus petit indice T tel que UT+1 soit < U0
T doit être nul si U1 < U0, même si par la suite on remonte au dessus de U0
par exemple A = 10
U0 = 10
U1 = 5 => c'est fini le vol en altitude, T = 0 plus petite valeur telle que U0+1 = U1 < U0
U2 = 16 => toi tu le comptes celui là !!
U3 = 8 etc
le calcul de T doit être définitivement figé dès que on trouve le premier U 0
le test sur U > P est donc insuffisant
et puis le mieux est de coller à la définition : de mette l'indice (c'est I, ou plutôt I-1) dans T au moment adéquat (la première fois qu'on a U < P)
et pas de faire de T un compteur en calculant T+1 dans T
Justement, en fait je ne comprends pas trop comment on peut faire ça, j'avais déjà demandé à ma prof de maths et je n'avais pas compris.. Je ne comprends pas trop comment on peut appliquer votre réponse
Bonjour.
L'instruction SI (U %== 0) ALORS est-elle correcte ?
Remarque dans certaines règles de codage comme le MISRA C pour des applications critiques, il est interdit d'écrire des instructions comme :
SI variable == constante ALORS
SI constante == variable ALORS
Je voulais simplement vous signaler une incohérence dans le code affiché avec :
SI (U % == 0) ALORS
Il doit manquer quelque chose si % est l'opérateur de modulo
Ah oui effectivement, j'avais modifié une partie de mon algorithme et j'avais oublié de remettre un 2
pour le coup du vol en altitude
traduction de l'énoncé mot à mot, de :
T est l'indice -1 du premier U qui est inférieur à U0
il faut traduire :
on met l'indice ( l'indice c'est I pas aurte chose) moins 1 dans T
la première fois
U < U0
on peut initialiser T à une valeur négative qui servira de "drapeau" pour signaler si on a déja mis sa sa valeur (définitive) dans U et donc traduire le "la première fois"
et donc
si U<0 ET U
D'accord merci, j'ai refait mon algorithme entre temps et je me demandais si comme ça il convenait? :
FONCTIONS_UTILISEES
VARIABLES
N EST_DU_TYPE NOMBRE
U EST_DU_TYPE NOMBRE
x EST_DU_TYPE NOMBRE
t EST_DU_TYPE NOMBRE
i EST_DU_TYPE NOMBRE
M EST_DU_TYPE NOMBRE
y EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE N
U PREND_LA_VALEUR N
x PREND_LA_VALEUR 0
AFFICHER "U("
AFFICHER x
AFFICHER ")="
AFFICHER U
M PREND_LA_VALEUR U
t PREND_LA_VALEUR 0
TANT_QUE (U!=1) FAIRE
DEBUT_TANT_QUE
SI (U%2==0) ALORS
DEBUT_SI
U PREND_LA_VALEUR U/2
FIN_SI
SINON
DEBUT_SINON
U PREND_LA_VALEUR 3*U+1
FIN_SINON
x PREND_LA_VALEUR x+1
AFFICHER "U("
AFFICHER x
AFFICHER ")="
AFFICHER U
SI (U>M) ALORS
DEBUT_SI
M PREND_LA_VALEUR U
FIN_SI
FIN_TANT_QUE
t PREND_LA_VALEUR x
AFFICHER "Temps de vol: T="
AFFICHER* t
AFFICHER "Altitude maximale: M="
AFFICHER M
U PREND_LA_VALEUR N
y PREND_LA_VALEUR 0
TANT_QUE (U>=N) FAIRE
DEBUT_TANT_QUE
SI (U%2==0) ALORS
DEBUT_SI
U PREND_LA_VALEUR U/2
FIN_SI
SINON
DEBUT_SINON
U PREND_LA_VALEUR 3*U+1
FIN_SINON
y PREND_LA_VALEUR y+1
FIN_TANT_QUE
i PREND_LA_VALEUR y-1
AFFICHER "Temps de vol en altitude: i="
AFFICHER i
FIN_ALGORITHME
c'est pire...
rien ne correspond plus à rien là dedans
(surtout sans aucun commentaire)
avec Algobox on peut ajouter des lignes de commentaires disant à quoi sert ce qu'on fait
donc on doit ajouter des lignes de commentaires disant à quoi sert ce qu'on fait
évidement une ligne de commentaire du genre
// ajouter 1 à K
K PREND_LA_VALEUR K+1
est totalement inutile !!
// pourquoi j'ajoute 1 à K
K PREND_LA_VALEUR K+1
permet d'expliquer ce qu'on fait (pourquoi on le fait et quelle en est la signification dans le processus global de mon algorithme)
et il n'y a aucune justification à faire deux boucles !
tout est dans la seule et unique boucle
Tant que U > 1
// progresser ma suite et traiter ce U là
fin tant que
Donc si je mets à la place de la 2e boucle T prend la valeur T-1, ça irait? Je ne comprends pas trop quel genre de commentaires je dois mettre sur l'algorithme
la prise de valeur de T doit se faire DANS la seule boucle
comme tu avais fait dans ton premier algo du 17-03-18 à 22:47
li fallait juste modifier l'initialisation, le test et le traitement de T
(pour correspondre à ce que dit l'énoncé)
et uniquement ça.
...des commentaires....
pour indiquer ce que veulent dire tes x, y, i etc, à quoi servent les différents tests et boucles dont il est quasiment impossible à la lecture de "ça" de savoir à quoi ils servent
si tu te demandes quels commentaire mettre c'est que tu n'as aucune justification de ce que tu écris et que tu alignes du code au pif sans savoir toi même pourquoi tu fais telle ou telle opération.
Je ne vois pas comment modifier T sans modifier également le temps de vol et l'altitude maximale, je ne comprends pas ce que je dois ajouter
il n'y a rien à ajouter
il y a à modifier (des traitements qui existent déja)
je t'ai dit que ce que tu faisais avec T ne correspondait absolument pas à ce que dit l'énoncé pour ce T=temps de vol en altitude
donc dans ton algorithme du 17-03-18 à 22:47
T PREND_LA_VALEUR 0
...
TANT_QUE (U!=1) FAIRE
DEBUT_TANT_QUE
I PREND_LA_VALEUR I+1
...
SI (U>P) ALORS
DEBUT_SI
T PREND_LA_VALEUR T+1
FIN_SI
...
FIN_TANT_QUE
...
AFFICHER "Temps de vol en altitude: T="
AFFICHER* T
...
les seules choses à modifier sont les éléments en rouge et rien d'autre
(et je t'ai même suggéré par quoi les remplaer "en pseudo code" dans mon message du 18-03-18 à 18:34)
Ton principal problème est que tu bidouilles du code au lieu de le construire
c'est un problème de méthodologie : comment programmer sainement
on commence par l'énoncé, en le découpant en opérations simples du plus général vers les détails les plus spécifiques
on doit générer la suite de Syracuse
l'algo est donc :
entrer la valeur initiale de U
tant que U >1
faire progresser U selon les règles de la suite
fin tant que
ça c'est le squelette de base
(et on n'écrit pas ça ni en Algobox, ni en Python ni en rien du tout mais en français, ("langage naturel" ou "pseudo code")
faire ça comme ça est indispensable pour avoir une idée claire et matérialisée sur sa feuille de brouillon du cadre de l'algo (de son squelette)
ensuite on va compléter la traduction de l'énoncé
toujours en français en oubliant Algobox, Python etc etc
on demande d'afficher chaque terme de la suite avec son rang
donc il me faut une variable "rang" en plus de la variable U
appelons là i
le squelette devient :
entrer la valeur initiale de U
le rang est i = 0 (vu que c'est U0)
tant que U >1
faire progresser U selon les règles de la suite
rang suivant, i+1
afficher U et i
fin tant que
ensuite tous ces trucs en français deviendront des commentaires
// valeur initiale de la suite (on dit à quoi sert U)
LIRE U
// rang 0 (on dit à quoi sert i)
i Prend_LA_VALEUR 0
TANT_QUE U > 1
(DEBUT TANT_QUE) (ça c'est du verbiage Algobox)
// valeur suivante de la suite
SI (U%2==0) ...
U PREND_LA VALEUR etc
FIN SI
// rang suivant (on rappelle ici à quoi sert la variable i)
i PREND_LA_VALEUR i+1
// affichage de U[ i ]
bardée de "AFFICHER"
...
FIN_TANT_QUE
on complète ainsi tout l'énoncé point par point
mais pas du tout sur le code en ALGOBOX !!!
c'est le plantage assuré et obtenir un programme dont personne ne saura ce qu'il fait vraiment, pas même celui qui l'a écrit en le relisant deux jours après.
sur l'algo en langage naturel
et ensuite on traduit en ALGOBOX, en Python, etc
parlons donc de cette histoire de vol en altitude par exemple
l'énoncé dit
le temps de vol en altitude T est le premier indice T tel que U[T+1} soit < la valeur initiale de U
il y a plein de choses à traduire là dedans
- "indice de" : ok pas de problème, l'indice c'est i, il n'y a rien à créer de plus
juste utiliser i à bon escient
- évidemment créer la variable T donnant le vol en altitude
- "la valeur initiale de U"
là il faut créer une variable appelons la U0
car U est modifié au fur et à mesure de l'avancement de la suite
- un test pour savoir si U < U0 donc
- "la première fois que"
ceci est "quelque chose" qui sera "vrai" ou "faux" et qui devra figurer explicitement dans le test :
si U
T = ...
on dit que T est tel que la valeur actuelle de i est T+1 (relire et comprendre : "la valeur de T telle que U[T+1] ...)
donc mon test devient
si U
T <--- i - 1
reste cette histoire de "première fois" et tout le traitement sur T sera entièrement et correctement effectué ( = correspondra à sa définition par l'énoncé)
on peut utiliser ce qu'on appelle un "drapeau"
// sauve la valeur initiale de U
U0 <-- U
// on n'a pas encore eu un Ui < U0
drapeau <-- vrai
// rang 0
i <-- 0
tant que U > 1
// valeur suivante de la suite U
// valeur suivante du rang i
si drapeau =vrai et U< U0 (c'est bien la traduction mot à mot)
// première valeur T telle que U(T+1] < U0 donc i = T+1 et T = i-1
T <-- i-1
// les fois suivantes que U sera < U0 ne seront plus "la première fois"
drapeau <--- faux
(fin du si)
...
(fin du tant que)
au lieu de nommer mon drapeau "drapeau" je peux rappeler dans son nom même sa signification en l'appelant "prem_fois"
ce qui donnera en ALGOBOX
// on n'a pas encore eu un Ui < U0
// 1 veut dire "vrai"
prem_fois PREND_LA_VALEUR 1
...
// temps de vol en altitude
SI (prem_fois==1 ET U
// première fois que U < U0
T PREND_LA_VALEUR i - 1
// les fois suivantes ne seront plus la 1ère fois
prem_fois PREND_LA_VALEUR 0
FIN_SI
...
FIN TANT_QUE
...
// temps de vol en altltude
AFFICHER T
...
etc etc
on construit l'algorithme pas à pas en complétant l'algorithme en langage naturel,
disant ce que l'on fait et sa signification dans le problème et pas en écrivant du code
"ce que l'on fait" dans l'algo en langage naturel deviendra des commentaires dans le code.
Merci beaucoup Mathafou! Je vais utiliser vos conseils pour refaire mon algorithme, par contre je ne savais pas tout ça tout simplement parce que notre prof nous a donné un seul et unique exemple d'algorithme sur Algobox, et qu'elle ne nous a pas parlé de commentaires et qu'elle n'avait pas vraiment fait de méthodologie.. Et étant donné que de base j'ai des difficultés de compréhension en maths, je n'avais pas pensé à faire tout ça...
Bonjour.
On récapitule...
Les définitions.
Nombre de départ : premier terme de la suite U0
Vol : suite de nombres commençant par le nombre de départ
Étape : nombre de la suite.
Altitude maximale du vol : le plus grand nombre obtenu dans la suite.
Durée du vol en altitude : nombre d'étapes avant de passer sous le nombre de départ une première fois.
Durée du vol : nombre d'étapes avant d'obtenir 1.
L'algorithme.
Il doit :
Déclarer et initialiser des variables.
Saisir une donnée au clavier, premier terme de la suite U0.
A l'aide d'une boucle :
- afficher l'étape Un
- mémoriser le temps de vol
- mémoriser l'altitude maximale atteinte
- mémoriser le temps de vol en altitude
- générer le terme Un+1
Afficher les résultats
L'algorithme tel que je le vois et assez proche de votre premier jet.
VARIABLES
n EST_DU_TYPE NOMBRE
u0 EST_DU_TYPE NOMBRE
u EST_DU_TYPE NOMBRE
altitude_max EST_DU_TYPE NOMBRE
temps_vol_alt EST_DU_TYPE NOMBRE
inc_temps_vol_alt EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
// initialisation...
// altitude max, nulle par defaut
altitude_max PREND_LA_VALEUR 0
// temps de vol en altitude
temps_vol_alt PREND_LA_VALEUR -1
// increment pour le temps de vol en altitude
inc_temps_vol_alt = 1
// indice n, nul par defaut
n PREND_LA_VALEUR 0
// saisie de l'entier initial
LIRE u0
// debut de la suite Un
u PREND_LA_VALEUR u0
// fin de boucle avec Un = 1 ?
TANT_QUE (u != 1) FAIRE
DEBUT_TANT_QUE
// affichage de Un
AFFICHER "U("
AFFICHER n
AFFICHER ") = "
AFFICHER u
// altitude max depassee ?
SI (u > altitude_max) ALORS
DEBUT_SI
// oui : mise a jour de l'altitude max ?
altitude_max PREND_LA_VALEUR u
FIN_SI
// mise a jour temps de vol en altitude
SI (u > u0) ALORS
DEBUT_SI
temps_vol_alt PREND_LA_VALEUR temps_vol_alt + inc_temps_vol_alt
FIN_SI
// fin de temps de vol en altitude ?
SI (u < u0) ALORS
DEBUT_SI
inc_temps_vol_alt PREND_LA_VALEUR 0
FIN_SI
// calcul de Un+1...
// Un pair ?
SI (u % 2 == 0) ALORS
DEBUT_SI
// oui : Un+1 = Un / 2
u PREND_LA_VALEUR u / 2
FIN_SI
SINON
DEBUT_SINON
// non : Un+1 = 3Un + 1
u PREND_LA_VALEUR 3 * u + 1
FIN_SINON
// incrementation de l'indice n
n PREND_LA_VALEUR n + 1
FIN_TANT_QUE
// affichage de Un
AFFICHER "U("
AFFICHER n
AFFICHER ") = "
AFFICHER u
// affichage final
AFFICHER "Temps de vol : "
AFFICHER n
AFFICHER "Altitude maximale : "
AFFICHER altitude_max
AFFICHER "Temps de vol en altitude : "
AFFICHER temps_vol_alt
FIN_ALGORITHME
A titre d'exemple, sa traduction en Python...
Les commentaires #... permettent de comprendre le code sans connaitre Python.
#*******************************************************************************
# IMPORT ***********************************************************************
#*******************************************************************************
# module pour le système d'exploitation
import os
# module specifique pour le systeme
import sys
#*******************************************************************************
# MAIN *************************************************************************
#*******************************************************************************
# effacement de l'ecran (facultatif)
os.system('cls')
print(" ")
# saisie de u(0)
u0 = int(input(" Entrez u(0) : "))
print(" ")
# nombre de termes calculés
n = 0
# premier terme de la suite Un
u = u0
# altitude max, nulle par défaut
altitude_max = 0
# temps de vol en altitude
temps_vol_alt = -1
# increment pour le temps de vol en altitude
inc_temps_vol_alt = 1
# on sort de la boucle des que u(n) = 1
while u != 1 :
# affichage
print(" u(% 4d) = % 5d" % (n, u))
# altitude max depassee ?
if u > altitude_max :
altitude_max = u
# temps de vol en altitude
if u > u0 :
temps_vol_alt += 1
# increment pour le temps de vol en altitude
if u < u0 :
inc_temps_vol_alt = 0
# calcul de u(n+1)...
# u(n) pair ?
if u % 2 == 0 :
# oui : u(n+1) = u(n) // 2
u //= 2
else :
# non : u(n+1) = 3 u(n) + 1
u = 3 * u + 1
# entier suivant
n += 1
# affichage
print(" u(% 4d) = % 5d" % (n, u))
print(" ")
# affichage du temps de vol en altitude
print(" Temps de vol : % 4d" % n)
# affichage de l'altitude maximale
print(" Altitude maximale : % 4d" % altitude_max)
# affichage du temps de vol en altitude
print(" Temps de vol en altitude : % 4d" % temps_vol_alt)
Exécution pour tester l'algorithme et sa traduction :
Entrez u(0) : 15
u( 0) = 15
u( 1) = 46
u( 2) = 23
u( 3) = 70
u( 4) = 35
u( 5) = 106
u( 6) = 53
u( 7) = 160
u( 8) = 80
u( 9) = 40
u( 10) = 20
u( 11) = 10
u( 12) = 5
u( 13) = 16
u( 14) = 8
u( 15) = 4
u( 16) = 2
u( 17) = 1
Temps de vol : 17
Altitude maximale : 160
Temps de vol en altitude : 10
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :