ALGO pour le calul du PGCD (par la calculatrice)

[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

[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 ?

[mostdu95]

d'accord c'est sur TI 83
voiçi mon algorithme :
Prompt a,b,r,y
a->x
b->y
If y 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

[lapras]

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

:happy2:

[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??

[gol_di_grosso]

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 ???

[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

[lapras]

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

[mostdu95]

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 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 ??

[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)

[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

[lapras]

Ca tu l'as dit !
:happy2:

[ghghgh]

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

[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 ?

[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 ;)

[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 http://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 + !

[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

[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 :/

[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 :happy2:

[ghghgh]

thx mec ;)