ALGO pour le calul du PGCD (par la calculatrice)

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: mostdu95

bonjour
j'arrive pas à programmer ma calculatrice pour le calcul du PGCD
J'ai fait un algorithme ( algo d'euclide qui consiste a remplacer la recherche du PGCD de a et b par la recherche du PGCD de b et r avec r le reste de la division euc de a par b ) mais maleureusement il ne marche pas ...ptet je l'ai pas bien ecris par ce que à un moment donné je dois dire definir r et moi j'ai tt simplement ecris r ->a-bq
quelqu'un peut il m'aider s'il vous plait
et merci d' avance


Posted by: bruce.ml

Salut,

ton algorithme semble correct, il faudrait que tu nous montres ton code pour qu'on puisse te corriger. C'est sur TI ou casio ?


Posted by: mostdu95

d'accord c'est sur TI 83
voiçi mon algorithme :
Prompt a,b,r,y
a->x
b->y
If y \no{=} 0
r->x-yq (c'est pour dire que r est le reste de la division euclidienne de a par b)
y->x
r->y
end
disp x


Posted by: lapras

salut,
si tu as une TI tu as une fonction toute faire GCD :
MATH > NUM > 9: GCD




Posted by: mostdu95

ah oui?? c'est super ...............!!!merci bien Lapras
et bah je comprend pas pourquoi lorsqu'on a fait l'algorithme d'Euclide ds le cours on nous a demonder de trouver un algothme pour le programmer ds nos calculatrices ?? ( ou ptet par ce que on le fera avec mapple ....!!!)
en se moment je reflechi sur un algo qui me permettera de trouver une solution particuliere de ax+by=c t'aurai pas d'idees??


Posted by: gol_di_grosso

Citation:
Posté par mostdu95
ah oui super merci bien Laras

"lapras" pas grave (enfin je suppose)

pour l'algo c'est aussi intéressant de voir comment il est fait dans la calculatrice (m^me si c'est un peu plus compliqué que ça)
arf vous avez Maple au lycée ???


Posted by: ghghgh

ax+by=c t'aurai pas d'idees??

où c est le pgcd de a et b ?

dans ce cas :

EUCLIDE-ETENDU(a,b)
si b = 0
alors retourner(a,1,0)
FIN DU SI
(c',x',y') <- EUCLIDE-ETENDU(b, a mod b)
(c,x,y) <- (c',y',x' - partie_entière(a/b)y')
retourner (c,x,y)

donc, ton algo prend en entrée une paire, et te renvoie un triplet :)

le pgcd, c, puis ton x et y, de là tu as ton équation ax+by = c


Posted by: lapras

je savais pas qu'on voyait euclide étendu (pour bezout) au lycée !


Posted by: mostdu95

Citation:
Posté par ghghgh
ax+by=c t'aurai pas d'idees??

où c est le pgcd de a et b ?

dans ce cas :

EUCLIDE-ETENDU(a,b)
si b = 0
alors retourner(a,1,0)
(c',x',y') <- EUCLIDE-ETENDU(b, a mod b)
(c,x,y) <- (d',y',x' - partie_entière(a/b)y')
retourner (d,x,y)

donc, ton algo prend en entrée une paire, et te renvoie un triplet :)

le pgcd, c, puis ton x et y, de là tu as ton équation ax+by = c

ok mais partie_entière je l'écris comme ça sur ma calculatrice ??
et "retourner" aussi ??
et le cas où b \no{=}0 ??
s' il nous renvoie un triplet; ce n'est plus une solution particuliere par ce que ce genre d'equation ( dianphontienne ) a toujours un couple de solutions..!!! non ??


Posted by: ghghgh

bah, je t'ai donné le pseud-code, à toi de te débrouiller pour l'implémenter, mais j'ai pas l'impression que t'ai bien compris...
ça te renvoi un triplet, mais dans ce triplet, un nombre c'est le pgcd, et les deux autres c'est ton couple x et y pour l'identité de bézout ax+by=d, où d est le pgcd de a et b
partie_entiere, si t'as un TI, tu fais int(ton_expression)

sinon, j'ai pas l'impression que tu aies vraiment compris...
retourner, c'est return, mais y a de fortes chances que t'as calto supporte par la récurrence, donc faut que tu modifies tout ça :)

le cas où b différent de 0 ?? oO
non, mais b vaudra forcément 0, tôt ou tard, puisque tu vois bien qu'à chaque fois on fait : b = a mod b =^p


EUCLIDE-ETENDU
tant que b n'est pas 0

tu modifs :)

fin tant que

et tu as d (où d est le pgcd), et le couple (x;y)


Posted by: ghghgh

tiens :)
http://fr.wikipedia.org/wiki/Algorithme_d'Euclide_étendu
une belle implémentation en itératif javascript, tu ne devrais avoir aucun mal à l'adapter pour ta calto ;)

to Lapras : hé, si tu n'étais sensé savoir que ce que tu vois au lycée, tu ne saurais pas grand chose xD


Posted by: lapras

Ca tu l'as dit !



Posted by: ghghgh

by the way, tu fais des olympiades de maths, ou autres trucs dans le genre Lapras ?


Posted by: lapras

j'vais essayé de passer le concour pour entrer dans l'équipe...
je fais les stages animath pour me préparer !
Et toi, tu les as passées ? Tu fais le concour général ?


Posted by: ghghgh

écoute, j'aimerais bien tenter pour voir... mais j'suis pas très au courant de tout ça... comment on fait pour se qualifier aux stages animath ?
concours général, on se fait inscrire par son bahut, n'est-ce pas ?
ils ne nous en ont pas parlé... sinon, j'aime bien les maths... mais j'en fais pas excessivement :) j'suis plutôt orienté algo/info :-)

ceci dit, si c'est possible... j'aimerais bien tenter, si t'as des infos à me lâcher, n'hésite pas ;)


Posted by: lapras

Salut,
moi je connais un peu les profs d'animaths donc je n'ai pas de problemes pour faire les stages, en général c'est eux qui me proposent les stages et on s'inscrit si on veut
je pense que toutes les infos des stages peuvent se trouver sur www.animath.fr
Le concour général : si tu es le meilleur de ta classe (ou un des meilleurs), le prof peut te proposer de t'inscrire au concour général et dans ce cas tu as le droit de t'inscrire.
Info/algo c'est bon pour fairee réfléchir je pense, tu dois etre logique
je m'entraine régulierement avec des anales des olympiades disponibles sur animath.fr, c'est des exos d'olympiades proposées à l'équipe francaise de mathématique.

Je poste régulierement des exos sur "Olympiades" dans le forum, tu peux lesregarder pour t'entrainer, mais ce n'est absolument pas du niveau concour général, il me semble que le concour général c'est un niveau tres élevé, je vais d'ailleurs commencer à m'entrainer.


Bon courage,
A + !


Posted by: ghghgh

:) merci pour toutes ces infos... on verra bien, mais j'ai l'impression que mon bahut (lycée Kléber, Strasbourg) n'est pas très concours au niveau lycée, bien sûr prépa... c'est autre chose xD


Posted by: ghghgh

tu sais où on peut se procurer ses livres ?
http://www.animath.fr/biblio.html
j'ai regardé vite fait, les 3/4 sont sold out :/


Posted by: lapras

Désolé je ne sais pas où se les procurer, je demanderai au prof samedi prochain les livres interessants et disponibles, je t'enverrai un MP


Posted by: ghghgh

thx mec ;)










-