Inscription / Connexion Nouveau Sujet
Algorithme
Bonjour,
J'ai un DM a rendre pour lundi et il y a cette exercice qui est dur pour moi. Je n'ai pas encore commencé. La professeur avait dit qu'il ne fallait pas exécuter l'algorithme.
Voici l'algorithme :
Variables : u et p sont des nombres entiers naturels non nuls.
Entrée : Saisir u
Traitement : Affecter à p la valeur 1
Tant que u different 1
Si u est pair alors
Affecter à u la valeur u/2
Sinon
Affecter à u la valeur 3u + 1
Fin Si
Affecter à p la valeur p + 1
Fin Tant que
Sortie : Afficher p
1)On exécute cet algorithme avec la valeur u = 6 saisie en entrée.
Quelle est la valeur de p affichée en sortie ?
2°) Exécuter l'algorithme avec u = 14 puis u = 100. Indiquer dans chaque cas la valeur de p affichée en sortie.
3°) a) Trouver un nombre u saisi en entrée tel que la valeur de p affichée en sortie soit p = 10.
b) De façon plus générale, quel nombre u peut-on saisir en entrée pour que la valeur de p affichée en sortie soit un entier naturel n ? justifier votre réponse.
Merci.
Bonjour,
il est impossible de prédire en général la valeur de p sans exécuter effectivement l'algorithme.
tu as donc certainement mal compris "La professeur avait dit qu'il ne fallait pas exécuter l'algorithme"
elle voulait sans doute dire "sur une machine"
(en fait il faut dérouler l'algorithme à la main dans un tableau)
pour la question 3 on demande "un" nombre tel que... pas le plus petit nombre tel que ...
si je choisis pour la valeur de départ une puissance de 2 que va faire l'algorithme ?
exemple de tableau : (à faire)
instruction u p commentaires
Saisir u 6
Affecter à p la valeur 1 6 1
Tant que u different 1 6 1 c'est vrai donc je fais
Si u est pair alors 6 1 oui 6 est pair, je fais
Affecter à u la valeur u/2 3 1
(sinon etc. bein .. je ne fais pas)
Affecter à p la valeur p + 1 3 2
(Fin Tant que je reviens au début de la boucle)
Tant que u different 1 3 2 c'est vrai donc je fais
Si u est pair alors 3 2 non 3 n'est pas pair, je fais le sinon
Affecter à u la valeur 3u + 1 10 2
Affecter à p la valeur p + 1 10 3
(Fin Tant que je reviens au début de la boucle)
Tant que u different 1 10 c'est vrai donc je fais
etc ...
on n'est pas obligé d'écrire explicitement les "fin tant que" et les "sinon" dans le tableau ni même d'écrire toutes les instructions une par une
on peut "résumer" avec une seule ligne par boucle exécutée.
certains mettent le tableau dans l'autre sens, mais c'est beaucoup moins pratique d'ajouter un nombre au départ inconnu de colonnes que d'ajouter des lignes...
Je ne sais pas la prof avait mis :
On s'intéresse à l'algorithme ci-contre :
( Il n'est pas nécessaire d'écrire un programme pour résoudre l'exercice, mais si vous souhaitez l'écrire sur Algobox, la commande pour tester si u est pair est : u%2 = = 0
c'est-à dire que le reste de la division euclidienne de u par 2 est zéro)
Elle avait mis un tableau aussi a compléter :
a) Reproduire et compléter le tableau des variables u et p.
u 6 3 10 …
p 1 2 3 ….
voila
Il n'est pas nécessaire d'écrire un programme
(ne pas confondre programme = sur machine et algorithme = description textuelle, l'algorithme est fourni, le programme il faudrait l'écrire)
Reproduire et compléter le tableau des variables u et p.
c'est bien ce que j'ai fait (refaire le début qui était donné en fait)
sauf que dans ce sens là il est beaucoup moins pratique à écrire, rédiger et comprendre
(c'est juste un extrait des seules colonnes p et u de mon tableau, mais sans aucun explication et en intervertissant lignes et colonnes)
remplir le tableau en poursuivant les boucles jusqu'à ce que on obtienne u = 1
tu n'as visiblement pas compris ce que j'ai fait dans mon tableau
et pourtant je me suis fendu de rajouter des commentaires à chaque ligne !!!
j'ai exécuté une par une les instruction de l'algorithme donné, en remplissant le tableau par les valeurs successives que prennent chacune des variables au fur et à mesure de l'exécution
cette exécution n'est pas terminée, c'est à toi de continuer (puisque pour l'instant u contient 10)
que ce tableau soit "en lignes" ou "en colonnes" ne change rien à sa signification
j'aurais pu me contenter du résultat brut de mon tableau en n'en gardant que l'essentiel (en rouge) sans aucune explication
instruction u p commentaires
Saisir u 6
Affecter à p la valeur 1 6 1
Tant que u different 1 6 1 c'est vrai donc je fais
Si u est pair alors 6 1 oui 6 est pair, je fais
Affecter à u la valeur u/2 3 1
(sinon etc. bein .. je ne fais pas)
Affecter à p la valeur p + 1 3 2
(Fin Tant que je reviens au début de la boucle)
Tant que u different 1 3 2 c'est vrai donc je fais
Si u est pair alors 3 2 non 3 n'est pas pair, je fais le sinon
Affecter à u la valeur 3u + 1 10 2
Affecter à p la valeur p + 1 10 3
(Fin Tant que je reviens au début de la boucle)
Tant que u different 1 10 3 c'est vrai donc je fais
...
etc à compléter (poursuivre cette exécution pas à pas)
c'est à dire
u p
6 1
3 2
10 3
...ou en échangeant les lignes et les colonnes pour obtenir le peu pratique tableau exigé de l'énoncé par un prof qui n'a visiblement jamais fait d'informatique pour poser son tableau dans ce sens là. (que ce soit ton prof perso ou celui qui a écrit le bouquin)
u 6 3 10 ... etc à compléter
p 1 2 3 ...
ton calcul est faux
u est toujours tout le temps un nombre entier
si tu trouves des virgules c'est que tu n'as pas suivi les instructions correctement (c'est tout de même assez simple et évident ces instructions !!!)
on divise par deux si u est pair (la valeur actuelle de u à cet instant) et uniquement dans ce cas.
la division d'un nombre pair par 2 donne toujours un nombre entier
et sinon (si u est actuellement impair) on ne divise pas par 2 ! on multiplie par 3 et on ajoute 1 !!
ce qui en partant d'un nombre entier donne forcément encore un nombre entier
donc u reste tout le temps entier.
en continuant à partir de la dernière valeur trouvée (le 19-03-16 à 19:25) 16 on n'obtient pas 9
16 est pair donc on le divise par 2 et 16 divisé par 2 ça fait 8, pas 9 (réviser ses tables de multiplication ??? faute de frappe ??)
8 étant encore pair, on le divise par 2 ce qui donne 4
et 4 étant encore pair on le divise par 2 etc
et pas ton calcul 3*4+1 = 13
de toute façon 13 étant impair si on en était à 13 on ne le diviserait pas par 2 !!
celui là (13) on le multiplierait : 3*13+1 = 39+1 = 40, pas 13/2 = 6,5
Cela veut dire qu'il y aura beaucoup de valeurs
il est impossible de prédire en général la valeur de p sans exécuter effectivement l'algorithme.
la valeur de p c'est le nombre de valeurs calculées
des fois peu, des fois beaucoup
les valeurs initiales de u données dans l'exo ne donnent pas "beaucoup de valeurs" (moins de 30)
vu que le calcul de ces valeurs se fait "comme on respire" de façon quasiment ludique, c'est très rapide.
et le nombre le plus grand pris par u dans les calculs de l'exo est 100
donc tout ça se fait à la main très vite. (de tête même !!)
on ne t'a pas demandé u = 54 (qui donnerait p = 112 !! en passant par la valeur maximale de u = 9232)
au pire si tu es "un peu paresseux" pour faire une trentaine d'opérations au maximum sur des nombres de deux chiffres ou moins, tu peux programmer cet algorithme sur machine (calculette ou Algobox)
mais comme il ne te donnera que le résultat final, il faut ajouter un affichage supplémentaire des valeurs de u et de p dans la boucle pour pouvoir remplir le tableau demandé !!
Variables : u et p sont des nombres entiers naturels non nuls.
Entrée : Saisir u
Traitement : Affecter à p la valeur 1
Tant que u different 1
Si u est pair alors
Affecter à u la valeur u/2
Sinon
Affecter à u la valeur 3u + 1
Fin Si
Affecter à p la valeur p + 1
Afficher u et p // affiche les valeurs à mettre dans le tableau
Fin Tant que
Sortie : Afficher p (inutile puisqu'on vient déja de le faire dans la dernière boucle)
D'acord c'est bon j'ai tout compris, mais on fait comment pour celle la ?
Quelle est la valeur de p affichée en sortie ?
donc tu n'as rien compris
c'est quoi le tableau que tu trouves maintenant ?
la "valeur de p affichée en sortie" est dedans
c'est pour ça qu'on a fait ce tableau
pour pouvoir la connaitre.
tant que u différent de 1 n'est ce pas
alors c'est quoi ton 4 à la fin ??? et tant qu'à faire pourquoi tu n'as pas continué en bouclant éternellement sur 1 4 2 1 4 2 1 4 2 1 4... jusqu'à la fin des temps ?
(et plutot que des petits bouts où il faut lire tous les messages pour vérifier, j'attendais le tableau complet en entier)
ton tableau est par principe faux car non, pas du tout "si je continue ceci cela" est FAUX
parce que justememnt la conditein "tant que" fait que on ne continue pas. et on s'arrête ici :
u 6 3 10 5 16 8 4 2 1
p 1 2 3 4 5 6 7 8 9
à cet instant u vaut 1 et la condition tant que u différent de 1 devient donc à ce moment fausse et on sort de la boucle
ça s'arrête donc là
l'algorithme justement ne continue pas ensuite.
tout ça parce que tu ne regardes pas ce que fait l'algorithme à chaque instant, à chaque instruction, à chaque colonne du tableau
comme dans MON tableau où je mets en commentaire exactement ce qui est fait à chaque instant
"oui, à cet instant u est différent de 1", "oui à cet instant u est pair" ou "non à cet instant u n'est pas pair" etc
et c'est à faire jusqu'à la fin, tout le temps, même si on ne l'écrit pas explicitement dans "le tableau" parce qu'il est "simplifié"
et ça se termine si on se pose la question
question écrite explicitement dans les instructions de l'algorithme,
encore faut-il les lire et pas les ignorer en se disant "ouais j'ai compris je continue jusqu'à plus soif"
non. je continue jusqu'à ce que le test du tant que me dise que à cet instant ça s'arrête.
et "ce qui est sorti par l'algorithme" c'est la valeur de p à cet instant , une fois que les boucles se sont terminées tout simplement
c'est à dire la valeur 9
c'est tout.
tu n'as plus qu'à faire pareil pour les valeurs de départ u = 14 et u = 100
Ah d'accord donc je refais la meme chose en commencant par u = 14 et p= 1 jusqu'a que j'obtienne u= 1 .
Annuler
connectez vous