Exercice - Divisibilite et Division euclidienne - Algorithme

[mathsnico]

Bonjour a tous,

Je demande de l'aide pour la resolution d'un exercice sur lequel j'ai rencontre beaucoup de difficultes a resourdre.

NOTE: L'exercice est dans la partie de specialite pour la terminale S.

L'exercice est sur le chapitre 1 de la specialite: "Divisibilite et Division Euclidienne".
C'est un algorithme.

C'est l'exercice 121 de cette page:
http://s7.postimage.org/3zsv69fcb/Picture.jpg




MERCI BEAUCOUP :lol3:

[Kikoo <3 Bieber]

Salut mathsnico,

Pour quelles questions rencontres-tu des problèmes ?

[mathsnico]

Salut mathsnico,

Pour quelles questions rencontres-tu des problèmes ?

Salut Kikoo,
C'est certainement tout l'exercice, mais je vais etre plus precis;
PARTIE A:
1. Dois-je remplacer a et b dans l'algorithme avec ces nombres. Si oui, quelle serait la formule?
2. Je ne comprend pas la question du tout.
3. J'ai des difficultes a faire un algorithme.

4 et 5. Questions tres faciles, mais je dois avoir besoin de la reponse de la question 3, donc je ne demandes pas la reponse a ces questions.

PARTIE B:
Toute la partie est compliquee et imcomprehensible.

[Kikoo <3 Bieber]

Salut Kikoo,
C'est certainement tout l'exercice, mais je vais etre plus precis;
PARTIE A:
1. Dois-je remplacer a et b dans l'algorithme avec ces nombres. Si oui, quelle serait la formule?
2. Je ne comprend pas la question du tout.
3. J'ai des difficultes a faire un algorithme.

4 et 5. Questions tres faciles, mais je dois avoir besoin de la reponse de la question 3, donc je ne demandes pas la reponse a ces questions.

PARTIE B:
Toute la partie est compliquee et imcomprehensible.

Tout d'abord, pour la première question :

Tu effectues la div euclidienne de a par b : ton algorithme prend tout d'abord deux nombres a et b, a>b. Tu soustrais autant de fois que possible la quantité b à a, et tu retournes à chaque fois la valeur du reste de la diveuc' du reste précédent par b. A chaque étape, tu incrémentes le compteur m de 1, qui compte le nombre d'étapes (de soustractions) qui mènent à un reste inférieur à b.

PS : c'est le principe de la méthode de la divisions euclidienne :

Tant que tu n'obtiens pas un reste négatif (dans ton exo) ou un reste inférieur strictement à b et toujours positif, tu répètes l'opération de soustraction de a par b, afin d'obtenir un reste final tel que :



Présentons un exemple :

Faisons la division euclidienne de 94 par 13.
Soustrayons une fois, puis deux, puis trois, ... autant que nécessaire :
94-13=81 et m=1
81-13=68; m:=m+1=2
68-13=55; m:=m+1=3
55-13=42; m:=m+1=4
42-13=29; m:=m+1=5
29-13=16; m:=m+1=6
16-13=3; m:=m+1=7
r=3<13
On stoppe.

Donc au final, 94=7*13+3

[mathsnico]

[quote="Kikoo b. Tu soustrais autant de fois que possible la quantité b à a, et tu retournes à chaque fois la valeur du reste de la diveuc' du reste précédent par b. A chaque étape, tu incrémentes le compteur m de 1, qui compte le nombre d'étapes (de soustractions) qui mènent à un reste inférieur à b.

PS : c'est le principe de la méthode de la divisions euclidienne :

Tant que tu n'obtiens pas un reste négatif (dans ton exo) ou un reste inférieur strictement à b et toujours positif, tu répètes l'opération de soustraction de a par b, afin d'obtenir un reste final tel que :



Présentons un exemple :

Faisons la division euclidienne de 94 par 13.
Soustrayons une fois, puis deux, puis trois, ... autant que nécessaire :
94-13=81 et m=1
81-13=68; m:=m+1=2
68-13=55; m:=m+1=3
55-13=42; m:=m+1=4
42-13=29; m:=m+1=5
29-13=16; m:=m+1=6
16-13=3; m:=m+1=7
r=3<13
On stoppe.

Donc au final, 94=7*13+3[/quote]

Ah. Explication parfaite.
Donc retournons a l'exercice, ca serait comme ca?

a) a=4 et b=2
4-2=2 et m=1
2-2=0; m: =m+1=2
Au final: 4=2*2+0.

b) a=3 et b=2
3-2=1 et m=1
Au final: 3=1*1+2

c) a=8 et b=6
8-6=2 et m=1
Au final: 8=1*6+2

[Kikoo <3 Bieber]

Ah. Explication parfaite.
Donc retournons a l'exercice, ca serait comme ca?

a) a=4 et b=2
4-2=2 et m=1
2-2=0; m: =m+1=2
Au final: 4=2*2+0.

b) a=3 et b=2
3-2=1 et m=1
Au final: 3=1*1+2

c) a=8 et b=6
8-6=2 et m=1
Au final: 8=1*6+2

Attention ! Le calcul du a) est bon mais tu as inversé le rôle de b et de r(a,b) pour la question b).
Sinon c'est bon pour la c)



Ah au fait, je remarque que dans ton exo, la sortie ('print', c'est-à-dire ce que l'algo doit afficher au final) correspond à a*m, donc tu sais ce que tu dois faire.

[Kikoo <3 Bieber]

Je t'ai présenté la méthode de la div euclidienne pour que tu comprennes mieux.

Au final, notre exo présente un autre algorithme. Lis le bien et essaie de me dire ce qu'il fait en toutes lettres.

[mathsnico]

[quote="Kikoo 0, ON A: r=a+r-b et m=m+1
SORTIE: mxa

Ce que j'ai compris;
a=4 et b=2, m=1,

a-b=4-2=2; m=1
2-2=0; m=m+1=1+1=2
donc 4=2*2+0
Sortie: mxa = 2 x 4 = 8.

C'est comme ca? Je ne suis pas sur.

[Kikoo <3 Bieber]

Ah oui. Je m'excuse. Donc c'est:

b) a=3 et b=2
3-2=1 et m=1
Au final: 3=1*2+1

Retournons a notre exo, J'ai pas tres bien saisi de quoi il s'agit, mais c'est ca ce que j'ai compris:

ENTREE: On doit sasir la valeur de a et b
INIT: r= a-b et m=1
TRAITEMENT: Tant que r>0, ON A: r=a+r-b et m=m+1
SORTIE: mxa

Ce que j'ai compris;
a=4 et b=2, m=1,

a-b=4-2=2; m=1
2-2=0; m=m+1=1+1=2
donc 4=2*2+0
Sortie: mxa = 2 x 4 = 8.

C'est comme ca? Je ne suis pas sur.

C'est bien !

Si tu continues pour a=3 et b=2, tu auras :
a-b=3-2=1=r
r est positif, donc on affecte à r la valeur de r(a+r;b), ce que l'on note formellement
r:=r(a+r,b)
Ici, r:=r(4,2)=0
m:=m+1=2
Donc nous avons a*m=6

Et je te laisse continuer pour les autres !

[mathsnico]

C'est bien !

Si tu continues pour a=3 et b=2, tu auras :
a-b=3-2=1=r
r est positif, donc on affecte à r la valeur de r(a+r;b), ce que l'on note formellement
r:=r(a+r,b)
Ici, r:=r(4,2)=0
m:=m+1=2
Donc nous avons a*m=6

Et je te laisse continuer pour les autres !

Ah bon.
Pour c)
a-b=8-6=2=r
r: =(a+r,b) =(10,6)

J'ai une question ici, vous avez dit: "r:=r(4,2)=0" pour la question b),
Je ne comprend pas d'ou viens la valeur finale de 0 ici? et comment on a arrive a "m:=m+1=2"?

[Kikoo <3 Bieber]

Ah bon.
Pour c)
a-b=8-6=2=r
r: =(a+r,b) =(10,6)

J'ai une question ici, vous avez dit: "r:=r(4,2)=0" pour la question b),
Je ne comprend pas d'ou viens la valeur finale de 0 ici? et comment on a arrive a "m:=m+1=2"?

A chaque fois que tu n'obtiens pas un reste nul ou négatif (mais négatif n'est pas un réel problème car on travaille souvent avec les congruences), alors ta variable r prend la valeur reste(a+r,b), et on incrémente du même coup m de 1. On sait de même trivialement que 2 divise 4 donc la div euclidienne de 4 par 2 laisse un reste nul.
D'où mon cheminement.

J'en profite pour faire remonter ce message, je m'en vais désormais. En attendant que quelqu'un d'autre prenne mon relais, hopefully.
Bonne soirée

PS : et pour répondre une dernière fois à ce que tu as fait pour la c, c'est bon jusqu'à là.
On sait ensuite que r(10,6)=4 et on incrémente m (m:=m+1=2).
Or r(8,4)=0 donc on incrémente enfin m:=3
m*a=3*8=24

Etc.

[mathsnico]

A chaque fois que tu n'obtiens pas un reste nul ou négatif (mais négatif n'est pas un réel problème car on travaille souvent avec les congruences), alors ta variable r prend la valeur reste(a+r,b), et on incrémente du même coup m de 1. On sait de même trivialement que 2 divise 4 donc la div euclidienne de 4 par 2 laisse un reste nul.
D'où mon cheminement.

J'en profite pour faire remonter ce message, je m'en vais désormais. En attendant que quelqu'un d'autre prenne mon relais, hopefully.
Bonne soirée

PS : et pour répondre une dernière fois à ce que tu as fait pour la c, c'est bon jusqu'à là.
On sait ensuite que r(10,6)=4 et on incrémente m (m:=m+1=2).
Or r(8,4)=0 donc on incrémente enfin m:=3
m*a=3*8=24

Etc.

Ah bon. Merci beaucoup. Je vais essayer de me faire comprendre les autres questions jusqu'a ce que quelqu'un arrive pour m'aider.
Mais est-ce que vous allez etre present demain? Si oui, je vous demande de retourner a ce Topic pour qu'on continue l'exercice.
Mille mercis pour vous.
A bientot.

[mathsnico]

Quelqu'un d'autre peut m'aider? Merci.