Exercices : Euclide vs Programme

[invited2c73cb1]

Bonjour,

Je fait appel à votre aide et à vos conseils pour m'aider à résoudre quelques questions d'un DM. Voici l'énoncé ci joint.

J'ai déjà répondu aux questions "c" et "d". J'ai trouvé un PGCD de 1 pour les deux. J'ai tenté de répondre à la question "e", comme vous pouvez le constater mais le programme ne marche pas, je ne sais pas pourquoi, il me dit qu'il y a un dépassement du nombre de boucles autorisées.

Pour la question "a", je n'arrive à trouver un exemple qui marche comme les précédents. Je tombe sans cesse sur des fractions.

Pour la "b", faut-il le démontrer avec des chiffres, ou de manière plus générale avec des lettres ?

Pour la "2", je ne sais pas du tout.

Pour la "3", j'ai peut-être une idée, mais je vais continuer à y réfléchir, en attendant vos réponses pour les questions précédentes.

Merci pour votre aide

Cordialement
-----

[invited2c73cb1]

J'ai réussi à terminer le programme avec a = 2013 et b = 123. Je trouve un PGCD = 3 pour la question "a". Est-ce suffisant comme justification ?

[invite0c8d8548]

Bonjour,
On ne voit pas ta pièce jointe...

[invited2c73cb1]

Bizzare, quand je clique, j'arrive à la lire

Peut-être car elle est en cours de validation

[A voir en vidéo sur Futura]

[invited2c73cb1]

http://www.hebergeurfichier.com/down...91d88fb83.html

Voici un lien qui mène à l'énoncé

[invited2c73cb1]

http://www.hebergeurfichier.com/down...0da07d750.html

Voici mon algorithme

Cordialement

[invite0c8d8548]

Rebonjour,
Désole mais que signifie "retourner a"? ( j'ai fait de la programmation mais seulement 1 mois et j'ai jamais vu ça)...
C'est retourner la fraction ?

[invited2c73cb1]

Justement, je ne sais pas du tout. Le prof nous a donné ça comme ça, le 25 en nous souhaitant joyeux noel par mail xd

[invited2c73cb1]

Car quand je fais cet algo pour 1053 et 325, je trouve 13. Or 13 est le pgcd de 1053 et 325. Donc je ne vois pas pourquoi il faudrait inverser.

[invited2c73cb1]

Et si on trouve une fraction, cela ne va pas car on ne peut pas dire si le nb est pair ou non. D'où la question "2"...

Je suis perplexe

[invite6997af78]

Salut,

j'ai pas tout tout bien lu, mais "retourner" signifie "renvoyer" (ce que tu as traduis "afficher" dans ton code).

Pour la a., il faut montrer que quelque soit le a et le b, le programme se termine ! Tu peux essayer de faire tourner "à la main" le programme, de regarder les valeurs à chaque tour (ceci te donne une suite... je te laisse finir)

Il nous manque ce que tu appelles "algorithme d'Euclide".

Pour ton programme, je pense qu'il y a une boucle infinie, c'est quel langage au fait ?

[invited2c73cb1]

Il s'agit d'algobox. J'ai choisi "afficher a" à la fin car je ne sais pas comment faire pour "retourner".

[invited2c73cb1]

En revanche, je ne vois pas comment tu peux créer ta suite car je n'ai aucune valeur de départ.

Je veux dire par là que une suite arithmétique par exemple c'est : Un = U0 + nr. Pour poursuivre la suite, j'ai besoin de U0. Or ici, je n'ai aucune valeur à part a et b.

[invite6997af78]

Il s'agit d'algobox. J'ai choisi "afficher a" à la fin car je ne sais pas comment faire pour "retourner".

"afficher" c'est bon.

Par contre, je vois pas l'erreur dans ton code. Désolé.

[invited2c73cb1]

Mais pour la suite je n'ai rien compris ^^. DSL

PS : je compte finir ce DM cet après midi, donc je serais TRES réactif dès que n'importe qui me répondra

[invite6997af78]

En revanche, je ne vois pas comment tu peux créer ta suite car je n'ai aucune valeur de départ.

Je veux dire par là que une suite arithmétique par exemple c'est : Un = U0 + nr. Pour poursuivre la suite, j'ai besoin de U0. Or ici, je n'ai aucune valeur à part a et b.

On s'en fiche de la nature (geometrique, arithmétique...) de la suite !
Regarde les valeurs de a et essaie de conclure.

[invited2c73cb1]

Voilà l'erreur dans algobox :http://www.hebergeurfichier.com/down...3971de1a1.html

[invited2c73cb1]

La seule chose que je constate pour a c'est qu'il est toujours impair... Le programme ne fonctionne que pour a et b impairs. Après il va falloir trouver un programme qui marche aussi pour les nombres pairs...

[invite6997af78]

Ecris la suite des valeurs de a, que constates-tu ?

D'ailleurs a impair c'est faux !!!

[invited2c73cb1]

((a-b)/2)*(1/2)^n ?? ça cogite mais cela m'étonnerai que ce soit cela...

[invite6997af78]

((a-b)/2)*(1/2)^n ?? ça cogite mais cela m'étonnerai que ce soit cela...

C'est quoi ca ?

Prend sur un exemple ! a= 123 et b= 99.

[invited2c73cb1]

- a = 12/2 = 6/2 = 3

- a = 99 et b = 3

Donc a = 48/2 = 24/2 = 12/4 =3

Donc je tombe sur 3

[invite6997af78]

- a = 12/2 = 6/2 = 3

- a = 99 et b = 3

Donc a = 48/2 = 24/2 = 12/4 =3

Donc je tombe sur 3

C'est faux : 12/2 est différent de 6/2...

Arrete de vouloir aller trop vite ! Et ecris a chaque itération la valeur de a.

[invited2c73cb1]

Dsl pour les annotations, je devrais remplacer mes = par des =>

[invited2c73cb1]

Au final je tombe sur 3. J'ai fais un programme sur ma calculatrice qui me donne le pgcd et c'est bien 3. Dsl pour ma rédaction. J'ai juste peur que tu te déco ^^

[invited2c73cb1]

a = a0*1/2^n avec n le nombre de fois que l'on divise a0. Dans l'exemple précédent c'est 12 et 48.

[invite6997af78]

Je prefere que tu fasses ce que je te demande que de rusher pour ecrire des bêtises...

Alors ma suite des a ?

[invited2c73cb1]

a = a0*1/2^n avec n le nombre de fois que l'on divise a0, jusqu'à ce que a soit impair

[sylvainc2]

Ce dm traite de l'algo binaire du pgcd. Il est basé sur les 3 propriétés suivantes:
1- si a et b sont pairs, pgcd(a,b) = 2*pgcd(a/2, b/2)
2- si a est pair et b impair, pgcd(a,b)=pgcd(a/2,b) (et si a est impair et b est pair, pgcd(a,b)=pgcd(a,b/2))
3- si a et b sont impairs, pgcd(a,b) = pgcd( (|a-b|/2, b)

La question 1 implémente la propriété 3 seulement, mais c'est facile de le compléter avec les propriétés 1 et 2.
Je te conseille d'écrire l'algo en implémentant les prop. 1,2,3 dans cet ordre.

(Si tu veux tricher, cherche "algorithme pgcd binaire" ou "binary gcd algorithm" en anglais sur le net. Tu vas trouver des tonnes d'exemples)

[danyvio]

Je n'ai pas approfondi les divers posts, mais ce qui me gêne dans l'algo, c'est la "traduction" de "échanger a et b " par : a prend la valeur de b , puis b prend la valeur de a . Si on code, on n'échange pas, on écrase la valeur de a