Compléter et expliquer un algorithme

[kenymi]

Bonsoir,

On considère le jeu de nombre suivant :
On choisit un nombre entier entre 1 et 99. À chaque étape, le remplace par la somme des carrés de ses chiffres.
Exemple: je choisis n = 7.
Étape 1: 49.
Étape 2: 97
...


1) Poursuivre la procédure pour n=7 [FAIT].
2) Recommencer avec n= 4. [FAIT]
3) Emettre une conjecture sur les suites de nombres obtenus.

Ma réponse : Ces suites aboutissent à une boucle ?

5) Voici un algorithme [BESOIN D'AIDE POUR CES QUESTIONS] :

Variables
q, r, n et s

Entrée
Saisir le nombre entier n

Traitement
Affecter 0 à s

Tant que n>0

q prend la partie entière de n/10
r prend la valeur n- 10q
s prend la valeur s + r^2
n prend la valeur q

Fin du Tant que

Sortie
Afficher s

a) Expliquer le rôle de cet algorithme [aide svp]
b) Compléter cet algorithme afin qu'il puisse valider la conjecture émise [aide svp]

Merci !

[kenymi]

J'ai testé avec 403915 .
Voilà ce que j'obtiens :

n = 403915
s = 0
q = n/10 = 403915/10 = 40391
r = n-10q = 403915-10*40391= 5
s = 0 + 5^2 = 25
n = 40391

Je trouve bien n=0

...Mais je ne comprends toujours pas comment expliquer et compléter l'algorithme...:(

[kenymi]

? Personne pour aider ?

[fatal_error]

salut,

alors je conjecture comme toi
ensuite, par rapport à l'algorithme, le but n'est pas de trouver n=0, le but c'est de dire à quoi sert l'algo.
Au pifomètre intuité, il correspond à ton énoncé à savoir, s correspond à la somme des digits au carré de n.

pour valider ta conjecture (je trouve le mot extremement mal choisi, pe je rate quelque chose), il faut que tu fasses une boucle, pour générer pleins de fois le nombre, et que tu les mémorises, jusqu'à retomber sur un nombre déjà trouvé.

Typiquement, si tu nommes

Code: Tout sélectionner

fonction step(n)
  Tant que n>0

  q prend la partie entière de n/10
  r prend la valeur n- 10q
  s prend la valeur s + r^2
  n prend la valeur q

  Fin du Tant que
retourner n


alors tu dois faire un truc du genre

Code: Tout sélectionner

Tant que continuer
  n = step(n)
  si n est dans listeNombres
    retourner n
  sinon
   ajouter n dans listeNombres
finTantque

[kenymi]

D'accord, merci beaucoup. Par contre, je n'ai pas très bien compris la validation de la conjecture. Le 2eme fragment est- il la suite du 1er ?

[kenymi]

Et qu'est-ce qu'un 'digit'...? Par quoi puis-je le remplacer ?

[kenymi]

? ? ? ? ?

[fatal_error]

donc déjà évites les posts intempestifs c'est considéré comme flood.

Ensuite, un digit est un chiffre, tu dois en trouver la signification sur le net...

Enfin, on ne valide pas la conjecture, on l'illustre.
Si tu veux valider ta conjecture, c'est pas par un algo que tu y arriveras (ou alors des trucs probablement un peu trop élaborés pour cette discussion et ton exercice)

Le 2eme fragment est- il la suite du 1er ?

le 2eme fragment de code, oui. Ca ne veut pas dire qu'il est correct, c'est juste pour expliquer comment faire. La syntaxe, le détail, c'est pour toi et ton cours

[chan79]

Ma réponse : Ces suites aboutissent à une boucle ?

oui, il y a toujours une boucle
C'est en partant de 6 ou de 60 qu'il faut faire le plus d'itérations pour la mettre en évidence, en obtenant deux fois 89.


On remarque que la boucle est souvent obtenue avec 89 comme ci-dessus (38 fois sur 99)

[mathafou]

Bonjour,

oui, il y a toujours une boucle
C'est en partant de 6 ou de 60 qu'il faut faire le plus d'itérations pour la mettre en évidence, en obtenant deux fois 89
On remarque que la boucle est souvent obtenue avec 89 comme ci-dessus (38 fois sur 99)

en fait il faut remarquer surtout qu'on obtient "fatalement" soit 1 soit 4 qui donnent tous deux des boucles
1 donne la boucle très courte 1, 1, 1 ...
4 donne la boucle un peu plus longue :
4, 16, 37, 58, 89, 145, 42, 20, 4, ...

ceci simplifie fortement l'écriture d'un algorithme pour vérifier (je dis bien vérifier exactement) la conjecture qui serait donc :
pour tout n entre 1 et 99, on finit toujours par tomber sur 1 ou 4, et donc sur une boucle.
on ne parle bien entendu pas de vérifier pour tout N entier (comment le pourrait-on ??), mais seulement dans le cadre de cet exo, donc entre 1 et 99

nota :
l'erreur de principe consistant à croire que le but de cet algorithme est d'obtenir n = 0 est la même que celle sur l'ile des maths, il s'agit donc vraisemblablement du même posteur
ce n'est pas gênant sauf s'il faisait croire sur un forum qu'il a trouvé lui même quelque chose alors qu'il l'a recopié depuis l'autre...

[nodjim]

C'est facile de prouver que pour 1 nombre à 3 chiffres au moins, la somme des carrés des chiffres est toujours inférieure à ce nombre. La boucle n'est donc pas une conjecture, mais une réalité !

[nodjim]

De plus, compte tenu de ce qui vient d'être écrit, le nombre de boucles n'est pas infini: il suffit de les chercher dans les nombres inférieurs à 100.

[kenymi]

Fatal_error, je ne comprends pas l' algo...Je trouve un nombre à 3 chiffres...Comment faire pour obtenir un nombre <à 100 ?

[kenymi]

Faut-il que je remplace " si n est dans liste nombres " par "si 0

[chan79]

Faut-il que je remplace " si n est dans liste nombres " par "si 0<n<99" ?

Si n varie en 1 et 999, il y a forcément une boucle puisque la somme des carrés est au maximum égale à 3*9²=243 qui a 3 chiffres.
Tu veux qu'il te donne quoi, ton algo, exactement ?

[chan79]

Quel que soit le nombre de départ, on arrive à la boucle 1-1-.... ou à la boucle
145; 42; 20; 4; 16; 37; 58; 89 ;145
On peut le démontrer par récurrence sur le nombre n de chiffres.
On suppose que c'est vrai jusqu'à un rang n-1
La somme des carrés des chiffres d'un nombre à n chiffres est inférieure ou égale à 81n
Le nombre de chiffres de 81n est inférieur ou égal à n-1
car dès que n est supérieur ou égal à 4
Il suffit de vérifier les boucles pour n=1,2 et 3