Inscription / Connexion Nouveau Sujet
algorithme
Bonjour,
Pourriez-vous m'aider à faire cet algorigramme svp car je ne comprend pas
Énoncé : Écrire un algorigramme qui à partir d'un entier strictement positif donné, retourne le résultat booléen VRAI ou FAUX selon que le nombre est parfait ou non.
Liste des nombres parfaits < 10000 : 6, 28, 496, 8128
non !
on me dit dans l'énoncé qu'un nombre est parfait s'il est égal à la somme de ses diviseurs stricts
ex : 28= 1+2+4+7+14
Ensuite on me dit dans l'énoncé que la liste des nombres parfaits < 10000 sont
6, 28, 496, 8128
Bonjour,
il y aurait à priori deux façons de satisfaire à l'énoncé au sens strict
- un algorithme un peu sot qui répond si le nombre saisi est dans la liste donnée directement à l'initialisation une fois pour toute
cet algorithme ne marchera pas si on lui donne un entier > 10000.
- ou le vrai travail effectivement demandé qui est de calculer la liste de tous les diviseurs d'un nombre saisi en entrée et d'en faire la somme pour savoir si oui ou non il est parfait de par la définition
(valeur maxi du nombre entré = limité par les seules capacités de calcul de la machine)
donc déja avant de rédiger un algorithme il faut se poser la vraie question :
comment je ferais à la main pour savoir si par exemple 360 est un nombre parfait sans utiliser la liste fournie
(cette liste n'est fournie que pour donner des exemples qui permettront de "tester" l'algorithme)
comment je ferais pour trouver tous les diviseurs (propres) de 360 ?
il sera alors relativement facile de rajouter à ce processus (rédigé sous forme d'algorithme) le calcul de la somme de ces diviseurs là et tester si c'est égal ou pas au nombre donné
Bonjour Mathafou
360 a 24 diviseurs
1 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360
On peut aussi décomposer 360 en facteurs premiers
360= 2^3 x 3^2 x 5
mais cela ne nous donne pas le nombre de diviseurs
le résultat on s'en fiche
c'est avec quelle méthode, quels calculs détaillés, tu as obtenu ces diviseurs
(et puis leur nombre on s'en fiche aussi, ce qu'on veut c'est leur somme, le dernier 360 étant exclus puisqu'on veut les diviseurs propres de n, c'est à dire strictement inférieurs à n)
excusez moi mais je n'ai vu aucune méthode pour savoir comment calculer les diviseurs d'un nombre. j'ai procédé à tâtons
je comprends bien que c'est cette méthode qui va me permettre de faire mon algorithme mais là je ne sais pas 
à tâtons ? tu veux dire que tu as essayé des nombres réellement au hasard sans avoir aucune certitude de ne pas en oublier ?
certainement pas !!
quelle logique as tu utilisée pour "choisir" les nombres que tu as essayé prétendument "à tâtons" ???
(réponse évidente, le problème est que tu n'en as pas conscience :
on n'est pas des machines et il faut être conscient des calculs que l'on fait et pourquoi on les fait)
une réponse possible est : j'ai essayé systématiquement (et pas à tâtons) tous les nombres entiers de 1 à ...
en ne gardant que ceux qui divisent 360
cela donne traduit en algorithme :
pour d de 1 à ... ça, ça va parcourir tous les nombres entiers pour les "essayer"
si d divise n je le garde c'est un diviseur
dans tous les cas je continue
reste à trouver quand je m'arrête (la borne du "pour")
et éventuellement une méthode "plus efficace", mais celle ci suffira pour tester des nombres jusque à de l'ordre du million
(sur machine, pas à la main !!) parce que au delà effectuer plusieurs millions de boucles peut être ... long, voir carrément rejeté
par exemple sur Algobox, il limite le nombre de boucles exécutées pour des raisons "de sécurité" (arrêter un programme mal foutu qui ne se terminerait jamais)
pour des améliorations, on verra plus tard
pour l'instant il reste à finaliser ce premier algorithme
en précisant les bornes et ce qu'on fait des diviseurs trouvés : à savoir les cumuler dans la somme de ces diviseurs
A tester ceci :
VARIABLES
n EST_DU_TYPE NOMBRE
i EST_DU_TYPE NOMBRE
d EST_DU_TYPE NOMBRE
S EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE n
S PREND_LA_VALEUR 0
POUR i ALLANT_DE 1 A n-1
DEBUT_POUR
d PREND_LA_VALEUR n/i
SI (d==floor(d)) ALORS
DEBUT_SI
S PREND_LA_VALEUR S+i
FIN_SI
FIN_POUR
SI (S==n) ALORS
DEBUT_SI
AFFICHER "Le nombre entre est parfait"
FIN_SI
SINON
DEBUT_SINON
AFFICHER "Le nombre entre n'est pas parfait"
FIN_SINON
FIN_ALGORITHMEOn peut aisément améliorer en limitant plus fort le nombre de boucles ...
le processus de recherche mentale personnelle fait partie du processus d'élaboration d'un algorithme
le court-circuiter en donnant un algorithme tout fait ne permettra pas de faire cette sorte "d'introspection" consistant à être conscient de l'enchainement des calculs que l'on ferait à la main pour résoudre le problème.
reste donc maintenant à Link06 uniquement à comprendre l'algorithme écrit par quelqu'un d'autre
(vu que si ça se trouve en faisant le processus d'élaboration lui-même il aurait peut être obtenu un algorithme différent ...)
"le processus de recherche mentale personnelle ..." ne fait plus partie de l'enseignement actuel.
On remplace la réflexion par des "recettes" à utiliser sans en comprendre la portée.
C'est triste, mais c'est comme cela...
Il faut s'en prendre aux décideurs, mais c'est peine perdue.
on s'en fiche des décideurs.
ça va sembler être de l'anarchisme mais je suis partisan d'une responsabilité personnelle et pas de se décharger sur des "décideurs" quels qu'ils soient
la qualité de l'enseignement est l'affaire personnelle de chaque enseignant et pas de programmes édictés par des caciques.
après il faut certes composer avec ce qui est imposé (sinon ce serait effectivement l'anarchie).
mais il est hors de question d'accepter qu'on impose de fabriquer des "petits robots"
Proposition de modification de l'algo pour permettre de manipuler de beaucoup plus grands nombres... Et rien n'empêche Link06 de réfléchir au pourquoi de ces modifications.
VARIABLES
n EST_DU_TYPE NOMBRE
i EST_DU_TYPE NOMBRE
d EST_DU_TYPE NOMBRE
S EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE n
S PREND_LA_VALEUR 1
POUR i ALLANT_DE 2 A floor(sqrt(n))
DEBUT_POUR
d PREND_LA_VALEUR n/i
SI (d==floor(d)) ALORS
DEBUT_SI
S PREND_LA_VALEUR S+i+d
FIN_SI
FIN_POUR
SI (S==n) ALORS
DEBUT_SI
AFFICHER "Le nombre entre est parfait"
FIN_SI
SINON
DEBUT_SINON
AFFICHER "Le nombre entre n'est pas parfait"
FIN_SINON
FIN_ALGORITHME-----
Juste pour tester, voici les quelques nombres parfaits qui suivent ceux donnés dans l'énoncé :
33550336
8589869056
137438691328
Pour le suivant, soit : 2305843008139952128, l'algo coince en nombre de boucles
salut, juste une remarque,
avec cet algo, si n= 4 alors S=5.
Un algo balance sans explication a-t-il un interet pedagogique ?
Un algo balance sans explication a-t-il un interet pedagogique ?
Bien évidemment.
Celui de pousser l'élève à en comprendre le mécanisme et à le justifier... voire à le modifier pour en augmenter les performances (comme par exemple ici permettre d'explorer jusque des nombres plus élevé) ...
Si l'élève ne le fait pas, on a alors effectivement perdu son temps ... mais c'est uniquement de la responsabilité de l'élève.
Il n'y a pas pas qu'une manière d'aider à progresser et la mienne vaut bien celle qui consiste à donner des pistes successives jusqu'à quand même faire l'essentiel (ce qui est archi fréquent) et donner la fausse impression à l'aidé qu'il y est arrivé par son travail.
bonsoir,
alb12 a raison; cet algorithme est en défaut pour les carrés parfaits, même si ça n' a aucune conséquence.
"avec cet algo, si n= 4 alors S=5."
Oui, il faut justifier que cela n'altère pas l'affichage du résultat "parfait ou non" (dans ce cas et dans les autres).
Voila encore un travail à faire ... pour l'élève.
alb12 a raison; cet algorithme est en défaut pour les carrés parfaits, même si ça n' a aucune conséquence.
Le but n'est pas que l'algo fournisse une bonne valeur de S dans tous les cas, mais bien affiche un résultat correct sur le fait que le nombre soit ou non parfait.
L'algo serait en défaut si ce n'était pas le cas ... et ce n'est pas le cas.
Mais c'est à justifier et/ou à corriger si besoin était.
Oui, ça peut se corriger facilement puisque le problème est parfaitement commu.
1 VARIABLES
2 n EST_DU_TYPE NOMBRE
3 k EST_DU_TYPE NOMBRE
4 S EST_DU_TYPE NOMBRE
5 d EST_DU_TYPE NOMBRE
6 DEBUT_ALGORITHME
7 LIRE n
8 S PREND_LA_VALEUR 1
9 POUR k ALLANT_DE 2 A floor(sqrt(n))
10 DEBUT_POUR
11 d PREND_LA_VALEUR n/k
12 SI (floor(d)==d) ALORS
13 DEBUT_SI
14 S PREND_LA_VALEUR S+k+d
15 FIN_SI
16 FIN_POUR
17 SI (floor(sqrt(n))==sqrt(n)) ALORS
18 DEBUT_SI
19 S PREND_LA_VALEUR S-sqrt(n)
20 FIN_SI
21 AFFICHER S
22 SI (S==n) ALORS
23 DEBUT_SI
24 AFFICHER "n est parfait"
25 FIN_SI
26 SINON
27 DEBUT_SINON
28 AFFICHER "n n'est pas parfait"
29 FIN_SINON
30 FIN_ALGORITHME
Résultats
***Algorithme lancé***
Entrer n : 4
3
n n'est pas parfait
***Algorithme terminé***
A savoir :
Une des propriétés des nombres parfaits est :
Le nombre de diviseurs d'un nombre parfait N (pair ou impair) est pair, puisque N ne peut être un carré parfait.
C'est noté sur le lien
et a été démontré. (je ne cherche pas la démo)
le dialogue initie entre Link06 et mathafou montre bien que la bonne methode
consiste à amener petit à petit le demandeur à regler les problemes les uns apres les autres.
Un algo tout fait n'apporte rien.
La preuve Link06 ne participe plus ...
Comment va-t-il expliquer l'algo à son professeur ?
Qui ne sera pas dupe, cet algo peut etre obtenu en 2 clics sur le web.
le dialogue initie entre Link06 et mathafou montre bien que la bonne methode
consiste à amener petit à petit le demandeur à regler les problemes les uns apres les autres.
Un algo tout fait n'apporte rien.
FAUX
La preuve Link06 ne participe plus ...
Comme que l'ai noté, si le demandeur reste passif après les réponses, c'est uniquement de sa responsabilité.
Mon premier algo aurait du être décortiqué, compris et critiqué par le poseur de question.
S'il ne le fait pas ... c'est son problème.
Toute la discussion qui a suivi mon 2eme algo aurait du être à l'initiative du poseur de question et cela l'aurait alors fait progresser. S'il ne le fait pas ... c'est son problème.
Si on veut afficher la vraie somme S (pas demandé), on peut modifier ainsi :
VARIABLES
n EST_DU_TYPE NOMBRE
i EST_DU_TYPE NOMBRE
d EST_DU_TYPE NOMBRE
S EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
LIRE n
S PREND_LA_VALEUR 1
POUR i ALLANT_DE 2 A floor(sqrt(n))
DEBUT_POUR
d PREND_LA_VALEUR n/i
SI (d==floor(d)) ALORS
DEBUT_SI
S PREND_LA_VALEUR S+i+d
SI (d==i) ALORS
DEBUT_SI
S PREND_LA_VALEUR S-i
FIN_SI
FIN_SI
FIN_POUR
SI (S==n) ALORS
DEBUT_SI
AFFICHER* "Le nombre entre est parfait"
FIN_SI
SINON
DEBUT_SINON
AFFICHER* "Le nombre entre n'est pas parfait"
FIN_SINON
AFFICHER S
FIN_ALGORITHME... Et il est encore possible d'améliorer en temps de calcul.
Mais c'est encore à l'initative du poseur de question que cela devrait être fait.
Notez que cet algo ne repond pas au pb pose, il doit renvoyer un booleen.
Ca c'est vrai aussi et peut être modifié par le poseur de question.
Cela ne devrait pas être trop difficile.
Gain de temps en boucle :
DEBUT_ALGORITHME
LIRE n
S PREND_LA_VALEUR 1
POUR i ALLANT_DE 2 A floor(sqrt(n))
DEBUT_POUR
d PREND_LA_VALEUR n/i
SI (d==floor(d)) ALORS
DEBUT_SI
S PREND_LA_VALEUR S+i+d
FIN_SI
FIN_POUR
SI (d==i-1) ALORS
DEBUT_SI
S PREND_LA_VALEUR S-d
FIN_SI
SI (S==n) ALORS
DEBUT_SI
AFFICHER* "Le nombre entre est parfait"
FIN_SI
SINON
DEBUT_SINON
AFFICHER* "Le nombre entre n'est pas parfait"
FIN_SINON
AFFICHER S
FIN_ALGORITHMEC'est bien ...
vous avez transformé l'exo de Link06 en petit concours personnel de programmation ...
alors que le but de cet exo est bien d'apprendre à chercher et concevoir un algorithme.
tant qu'à faire puisque ça vous amuse :
On peut aussi décomposer 360 en facteurs premiers
360= 2^3 x 3^2 x 5
mais cela ne nous donne pas le nombre de diviseurs
peut on obtenir la somme des diviseurs de n à partir de sa décomposition en facteurs premiers
réaliser un algorithme correspondant
comparer le nombre total de boucles exécutées avec celui du dernier algorithme publié ici.
notas :
- pour connaitre le nombre de boucles total exécuté par Algobox, point besoin de les compter soi-même
la variable interne ALGOBOX_COMPTEUR_BOUCLE_GLOBAL le fait pour nous.
- évidemment dans la dernière variante, à écrire, "l'efficacité" de l'algorithme dépendra de la méthode de décomposition en facteurs premiers utilisée
on ne cherchera pas à utiliser des méthodes sophistiquées, mais uniquement des méthodes accessibles à ce niveau.
- de toute façon Algobox étant basé en interne sur JavaScript, la valeur maximale possible d'un nombre entier est 9007199254740991
au dela il fait n'importe quoi car les nombres entiers plus grands seront alors représenté par une approximation en virgule flottante.
On ne pourra donc pas tester avec Algobox et sans bidouillages affreux si 2305843008139952128 est parfait ou pas, et pas franchement à cause du nombre de boucles, mais simplement parce que les calculs ne riment à rien et par conséquent la boucle ne se termine en fait jamais.
On ne pourra donc pas tester avec Algobox et sans bidouillages affreux si 2305843008139952128 est parfait ou pas, et pas franchement à cause du nombre de boucles, mais simplement parce que les calculs ne riment à rien et par conséquent la boucle ne se termine en fait jamais.
Oui, et alors ?
Personne n'a écrit que la seule limitation d'algobox était le nombre de boucles.
Ma remarque "Pour le suivant, soit : 2305843008139952128, l'algo coince en nombre de boucles " pourrait avantageusement être remplacée par une introduisant la longueur max des entiers manipulables par algobox.
Ce n'est pas une raison pour ne pas soigner un peu l'écriture de l'algo pour limiter le nombre de boucles et permettre la manipulation de nombres plus grands.
La 1ere écriture proposée de l'algo bloque à cause de la limite du nombre de boucles permis par algobox bien avant celle imposée par la "taille" du nombre entré.
Les algos suivants permettent d'utiliser des nombres beaucoup plus grands ...
Mais il est vrai que c'est sans grande importance quand on débute dans l'étude des algos, on n'est alors pas censé, à ce stade, se préoccuper des limitations matérielles et logicielles.
bonjour,
juste pour vous dire que mon exercice est à faire pour dans 10 jours : je voulais juste m'avancer.
Cette semaine, j'ai le bac blanc de français : ce qui explique que je n'ai pas encore répondu !
Mais pas d'inquiétude, je ne recopierai pas qq chose que je ne comprends pas (pas dans mes habitudes) et c'est totalement inutile car je ne saurais pas le refaire en interro (donc aucun intérêt)
Mais pour l'instant nous ne sommes qu'au début des algorithmes donc si problème : je reviendrai vers vous.
Mais merci pour votre aide à tous
Annuler
connectez vous