programme équations diophantienes

Publié le 25 avr. 2015 il y a 8A par Anonyme - Fin › 5 mai 2015 dans 8A
6

Sujet du devoir

bonjour je cherche a programmer sur ma calculette TI83 un algorithme qui trouverais des solutions particulières pour les équations diophantienes (du type Ax+By=C avec A,B,C des entiers relatifs)

 

Où j'en suis dans mon devoir

j ai deja réussi a éliminer les cas ou il n y a pas de solutions ( pour qu il existe une solution il faut que le PGCD(A,B) divise C) mais je n'arrive pas a continuer

j essaye d'utiliser l'algorithme d'euclide mais je n'arrive pas a l'intégrer dans le programme peut être faut il utiliser une autre méthode je suis un peu perdu 

merci d'avance pour votre aide




5 commentaires pour ce devoir


Little Bear 7334
Little Bear 7334
Posté le 26 avr. 2015

Bonjour,

je ne suis pas sûr d'avoir compris le sens de la demande et votre attente.

Essayez de préciser, car il y a des plusieurs solutions pour une équation.

lisez ça : http://fr.wikipedia.org/wiki/%C3%89quation_diophantienne_ax_%2B_by_%3D_c

pour voir si cela réponds à la question

Faites signe

Sinon donnez un exemple.

Anonyme
Posté le 26 avr. 2015

oui il existe plusieurs solutions et je connais la méthode pour les trouver mais je voudrais rédiger un programme sur ma calculatrice qui me permettrais d'automatiser la recherche d'une solutions particulières

par exemple l'equation 25x-108y=1

 

on recherche avec l'algorithme d'euclide une solution particulière : 

108=4*25+8 <=> 8=108-4*25 (1)

25=3*8+1 <=> 1=25-3*8 <=>(d'apres (1)) 1=13*25-3*108

on a donc comme solutions le couple (13;3)

et c'est cette partie que je n'arrive pas a mettre sous forme d'algorithme

Little Bear 7334
Little Bear 7334
Posté le 26 avr. 2015

1 VARIABLES
2 a EST_DU_TYPE NOMBRE
3 b EST_DU_TYPE NOMBRE
4 c EST_DU_TYPE NOMBRE
5 d EST_DU_TYPE NOMBRE
6 e EST_DU_TYPE NOMBRE
7 f EST_DU_TYPE NOMBRE
8 g EST_DU_TYPE NOMBRE
9 h EST_DU_TYPE NOMBRE
10 i EST_DU_TYPE NOMBRE
11 j EST_DU_TYPE NOMBRE
12 AA EST_DU_TYPE NOMBRE
13 BB EST_DU_TYPE NOMBRE
14 pgcd EST_DU_TYPE NOMBRE
15 DEBUT_ALGORITHME
16 LIRE a
17 LIRE b
18 d PREND_LA_VALEUR 10
19 e PREND_LA_VALEUR 0
20 f PREND_LA_VALEUR 0
21 g PREND_LA_VALEUR 1
22 h PREND_LA_VALEUR 1
23 i PREND_LA_VALEUR 1
24 j PREND_LA_VALEUR 1
25 SI (abs(a)!=abs(b)) ALORS
26 DEBUT_SI
27 SI (abs(a)<abs(b)) ALORS
28 DEBUT_SI
29 c PREND_LA_VALEUR a
30 a PREND_LA_VALEUR b
31 b PREND_LA_VALEUR c
32 c PREND_LA_VALEUR 0
33 FIN_SI
34 FIN_SI
35 SINON
36 DEBUT_SINON
37 AFFICHER "erreur de saisie"
38 FIN_SINON
39 pgcd PREND_LA_VALEUR F2(abs(a),abs(b))
40 AFFICHER pgcd
41 a PREND_LA_VALEUR a/pgcd
42 b PREND_LA_VALEUR b/pgcd
43 AA PREND_LA_VALEUR a
44 BB PREND_LA_VALEUR b
45 j PREND_LA_VALEUR -floor(a/b)
46 AFFICHER "i="
47 AFFICHER i
48 AFFICHER " , j= "
49 AFFICHER j
50 c PREND_LA_VALEUR floor(a/b)
51 d PREND_LA_VALEUR round(((a/b)-c)*b)
52 a PREND_LA_VALEUR b
53 b PREND_LA_VALEUR d
54 f PREND_LA_VALEUR h
55 h PREND_LA_VALEUR j
56 AFFICHER "0000000000000000"
57 TANT_QUE (d>1) FAIRE
58 DEBUT_TANT_QUE
59 c PREND_LA_VALEUR floor(a/b)
60 d PREND_LA_VALEUR round(((a/b)-c)*b)
61 i PREND_LA_VALEUR e-g*c
62 j PREND_LA_VALEUR f-h*c
63 AFFICHER "d="
64 AFFICHER d
65 a PREND_LA_VALEUR b
66 b PREND_LA_VALEUR d
67 AFFICHER "i= "
68 AFFICHER i
69 AFFICHER " , j= "
70 AFFICHER j
71 e PREND_LA_VALEUR g
72 g PREND_LA_VALEUR i
73 f PREND_LA_VALEUR h
74 h PREND_LA_VALEUR j
75 AFFICHER "0000000000000000"
76 FIN_TANT_QUE
77 AFFICHER "a= "
78 AFFICHER a
79 AFFICHER "Résultat : "
80 AFFICHER pgcd
81 AFFICHER " * ("
82 AFFICHER AA
83 AFFICHER " ) x ( "
84 AFFICHER i
85 AFFICHER " ) + ( "
86 AFFICHER BB
87 AFFICHER " ) x ( "
88 AFFICHER j
89 AFFICHER " ) = "
90 AFFICHERCALCUL (AA*i+BB*j)*pgcd
91 AFFICHER "fin"
92 FIN_ALGORITHME

Little Bear 7334
Little Bear 7334
Posté le 26 avr. 2015

Ci-dessus le programme que j’ai écrit pour donner le couple.
J’ai testé une dizaine d’équations trouvées sur le net avec leurs solutions.
Il a donné la solution à chaque fois.

Explications sur le prog.
Le prog a été fait sur Algobox.

il peut etre simplifier au niveau de l'affichage.
Abs() = valeur absolue
Floor() = partie entière
Round() = arrondi valeur entiere la plus proche.
F2() = fonction intégrée qui donne le pgcd.

Valeurs d’entrée : a et b
Valeurs de sortie : AA, BB, i et j
Le couple est i et j mais avec a>b (en valeur absolue)
Si a = -108 et b = 25 alors AA=a=-108 , BB=b=25 , i = 3 et j = 13
Si a = 25 et b = -108 alors AA=b=-108 , BB=a=25 , i = 3 et j = 13

J’espère que c’est clair.
Je vous laisse comprendre et analyser mon prog.
S’il y a des questions , il ne faut pas hésiter.

Faites signe pour savoir si j'ai repondu à la question.

Little Bear 7334
Little Bear 7334
Posté le 30 avr. 2015

Où en êtes vous?

Est ce que mon aide a été utile?

faites un signe.


Ils ont besoin d'aide !

Il faut être inscrit pour aider

Crée un compte gratuit pour aider

Je m'inscrisOU

J'ai déjà un compte

Je me connecte