PGCD et Bezout

Version imprimable

06/12/2007, 22h44
nalia

PGCD et Bezout

Bonsoir,
j ai un programme a realiser en C d'ici qlq jour, et je n y comprend rien!!!
En gros j aurai besoin que qlq un m'aide a faire ce programme que je dois rendre ( je precise je ne suis pas du tout informaticenne)
cependant j ai qlq parties de ce prog.
le programme doit :
-calculer les nombres de Bezout (ie. il existe u, v tel que ua+vb=pgcd(a,b)
-calculer le pgcd et nb de bezout de n entiers
-il existe ui vi=pgcd(v1,...,vn)

MERCI D AVANCE
06/12/2007, 22h46
smilingFrog

C'est vraiment abuser.....................
06/12/2007, 23h07
Garulfo

Citation:

Envoyé par nalia

Bonsoir,
j ai un programme a realiser en C d'ici qlq jour, et je n y comprend rien!!!
En gros j aurai besoin que qlq un m'aide a faire ce programme que je dois rendre ( je precise je ne suis pas du tout informaticenne)
cependant j ai qlq parties de ce prog.
le programme doit :
-calculer les nombres de Bezout (ie. il existe u, v tel que ua+vb=pgcd(a,b)
-calculer le pgcd et nb de bezout de n entiers
-il existe ui vi=pgcd(v1,...,vn)

MERCI D AVANCE

Il aurait peut être fallu écouter en classe :mur:
06/12/2007, 23h07
siegfried64

si tu n a pas deja trouvé quelqun pour t aider sur ce projet envoie moi un pm, je serai ravie de t'aider a le realiser
06/12/2007, 23h08
Garulfo

Citation:

Envoyé par siegfried64

si tu n a pas deja trouvé quelqun pour t aider sur ce projet envoie moi un pm, je serai ravie de t'aider a le realiser

8O
06/12/2007, 23h35
siegfried64

Citation:

Envoyé par Garulfo

Il aurait peut être fallu écouter en classe :mur:

c'est simple a dire 8-)
si je me rappelle bien l autre jour un certain prof avait posté ici demandant de l'aide sur un sujet que je trouve pas si difficile que ca. Alors vaut mieux l'assister un peu dans son projet

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <math.h>
 
typedef struct solution_ {
    int d;
    int x;
    int y;
}Solution;
 
int pgcd(int a, int b) {
    return (b == 0) ? a : pgcd(b,a%b);
}
 
Solution euclide_etendu(int a, int b) {
    Solution s;
    Solution tmp;
 
    if (b == 0) {
        s.d = a;
        s.x = 1;
        s.y = 0;
 
        return s;
    }
 
    else {
        tmp = euclide_etendu(b,a%b);
        s.d = tmp.d;
        s.x = tmp.y;
        s.y = tmp.x-(floor(a/b)*tmp.y);
 
        return s;
    }
}
 
int main(void) {
    Solution s = euclide_etendu(5,49);
 
    printf("pgcd(5,49) = %d = (5*%d) + (49*%d)\n",s.d,s.x,s.y);
 
    return 0;
}

Sortie du programme :

Code:

1
2
 
pgcd(5,49) = 1 = (5*10) + (49*-1)

07/12/2007, 02h04
Sve@r
Citation:
Envoyé par AuraHxC

Code:

1 2 3 int pgcd(int a, int b) { return (b == 0) ? a : pgcd(b,a%b); }
Mis à part que tu lui as écrit tout son programme (ce qui est contraire à la charte du forum) pourquoi utiliser la récursivité ? Ca mobilise énormément de ressources alors qu'on pourrait, en se creusant à peine un peu la tête, faire un code itératif plus long certe mais paradoxalement moins gourmand...
Code:

1 2 3 4 5 6 7 8 9 10 int pgcd(int a, int b) { int mem; while (b != 0) { mem=a; a=b; b=mem%b; } return a; }
07/12/2007, 07h45
Melem

Citation:

Envoyé par Sve@r

pourquoi utiliser la récursivité ? Ca mobilise énormément de ressources alors qu'on pourrait, en se creusant à peine un peu la tête, faire un code itératif plus long certe mais paradoxalement moins gourmand...

Parce qu'il n'a pas envi de se creuser la tête :lol:. Bon, en fait parce qu'un algorithme récursif est plus facile à lire et à trouver (je pense) qu'un algorithme itératif, comme tu l'as dit toi-même il faut un peu se creuser la tête pour écrire la version avec itération. Dans beaucoup de cas, comme dans celui-ci, un algorithme récursif formule directement la définition même de la solution du problème. Une fois qu'on a trouvé la solution récursive il devient plus facile de passer à la solution itérative en décortiquant l'algorithme.
07/12/2007, 12h37
AuraHxC

Effectivement, je l'ai fait pour une raison évidente => Il était tard donc je suis aller à la version la plus rapide a coder (1 ligne) et je trouve que c'est assez lisible si bien entendu elle cherche au moins la signification d'une syntaxe blabla ? blabla : blabla; en C.
Sinon j'aurais peut être pas du donner mon code mais bon j'étais dans une journée de réussite au niveau de mes cours, donc je dirais que j'étais généreux... On va dire qu'elle est tombé sur le bon jour lol.

EDIT : D'ailleurs je trouve pas que la version itérative soit si compliqué à trouver (faut pas un effort intellectuel extraordinaire :D ), c'était juste l'efficacité niveau temps de codage... Donc assez fainéant sur ce coup :P
07/12/2007, 13h18
siegfried64

et j'ajoute : "Premature optimization is the root of all evil" 8-)

Citation:

Envoyé par Melem

Bon, en fait parce qu'un algorithme récursif est plus facile à lire et à trouver (je pense) qu'un algorithme itératif

Oui, presque toujours. Mais hyper dangereux. Pense à Fibonacci ou chaque nombre est la somme des deux nombres précédents !!!
Code:

1 2 3 4 5 ulong fib(ulong n) { if (n == 0 || n == 1) return n; return fib(n - 2) + fib(n - 1); }
Pour calculer fib(6) il ira calculer fib(5) + fib(4). Pour calculer fib(5) il ira recalculer fib(4) + fib(3). Pour calculer fib(4) il ira recalculer fib(3) + fib(2) etc etc. Quand ton code mettra 45 sec pour te sortir fib(8) tu commenceras à te poser des questions...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ulong fib(ulong n) { ulong res[3]={0, 1}; ulong i; if (n == 0 || n == 1) return n; for (i=2; i <= n; i++) { res[2]=res[0] + res[1]; res[0]=res[1]; res[1]=res[2]; } return res[2]; }
Une simple boucle. Tu vas sans fatigue jusqu'à fib(26). Après tu perds de la précision...

Citation:

Envoyé par Melem

Une fois qu'on a trouvé la solution récursive il devient plus facile de passer à la solution itérative en décortiquant l'algorithme.

Exact mais l'algo récursif est lui-même issu d'un algo mathématique qui peut aussi servir de base pour créer l'algo itératif.

Je dis pas que la récursivité "c'est le mal" mais qu'il faut sans-cesse se demander si on aurait pas avantage à passer par l'itératif (quitte à un peu de réflexion).

Malheureusement il existe des fonctions récursives qu'on n'arrive pas à mettre en itératif
Code:

1 2 3 4 5 6 ulong Ackerman(ulong n, ulong m) { if (m == 0) return n + 1; if (n == 0) return Ackerman(m - 1, 1); return Ackerman(m - 1, Ackerman(m, n - 1)); }

07/12/2007, 21h34
AuraHxC

Vous croyez que l'on va avoir au moins un ptit merci pour l'aide que lui a fournit :lol:
07/12/2007, 22h52
Rukia

Citation:

Envoyé par AuraHxC

Vous croyez que l'on va avoir au moins un ptit merci pour l'aide que lui a fournit :lol:

si elle est en vie :lol:
08/12/2007, 01h19
AuraHxC

Pourtant je n'ai pas mis un code tueur :D

Citation:
Envoyé par Sve@r
Oui, presque toujours. Mais hyper dangereux. Pense à Fibonacci ou chaque nombre est la somme des deux nombres précédents !!!
Code:

1 2 3 4 5 ulong fib(ulong n) { if (n == 0 || n == 1) return n; return fib(n - 2) + fib(n - 1); }
Pour calculer fib(6) il ira calculer fib(5) + fib(4). Pour calculer fib(5) il ira recalculer fib(4) + fib(3). Pour calculer fib(4) il ira recalculer fib(3) + fib(2) etc etc. Quand ton code mettra 45 sec pour te sortir fib(8) tu commenceras à te poser des questions...
Sauf que rien n'empêche de réfléchir aussi un peu pour coder en récursif. Je te propose ceci à la place.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 ulong fib_rec (ulong un, ulong un1, ulong n) { if (n == 0) { return un; } else { return fib_rec (un1, un1 + un, n-1); } } ulong fibrec (ulong n) { return fib_rec (1, 1, n); }
Elle est équivalente en nombre de calculs à la version itérative et elle est à mi-chemin entre la définition mathématique et la version itérative, donc plus lisible à mon avis.

De cette version en découle naturellement la version itérative. En compilant en O2, le compilateur la trouve même par lui-même.

En faisant quelques tests de performances en O2 (gcc + Cygwin), j'ai remarqué que l'utilisation d'un tableau dans ta version itérative ralentit fortement l'exécution (genre fois deux). En utilisant des variables à la place, on trouve alors des performances équivalentes entre version récursive et itérative, avec effectivement une toute légère avance pour la version itérative. Même en O0, c'est équivalent en temps de calcul.

Codé correctement, la récursivité n'est donc pas "hyper dangereuse" mais il faut savoir ce qu'on fait et quelles en sont les limites.

08/12/2007, 14h13
nalia

merci

merci a tout le monde pour cette aide; desoler de vous ecrire seulement maintenant;
cependant ce n ai pas vraiment ce que je cherche je crois, je vais vous ecrire plus de details tt a l heure
merci encore
08/12/2007, 17h46
AuraHxC

Ben tu as bien demandé l'identité de bezout : ax+by = d avec d pgcd(a,b) => ben mon programme te fournie le pgcd et les entiers relatifs x et y.
Après peut être que tu voulais autre chose hein :D
09/12/2007, 20h39
Garulfo

Citation:

Envoyé par Sve@r

Oui, presque toujours. Mais hyper dangereux. Pense à Fibonacci ou chaque nombre est la somme des deux nombres précédents !!![...]

Tu confonds le besoin pratique et la pratique des notions conceptuelles.
Il faut d'abord apprendre à faire un algorithme et à le penser: la récursivité est un plus en général à ce moment. Après on voit qu'il est dangeureux (cours de complexité) et on apprend à l'optimiser (forme itérative ou forme récursive terminale). Le fait d'avoir pris le temps de voir chaque étape est un plus pédagogiquement. Car si on lui avait fait faire directement le « bon » choix, l'étudiant n'aurait pas compris le piège en général.

Surtout qu'en pratique, personne ne code Fibonacci.

@aoyou ce que tu écris est aussi difficile que de penser la forme itérative, puisque finalement écrire une forme récursive terminale c'est de penser de manière itérative sous un certain angle.

Finalement, je note la dernière technique pour améliorer fibonacci qui n'a pas été dite : la memoization. En sachant que dans des langages comme scheme, on peut complètement l'automatiser. Dès lors, ça utilise de la mémoire, mais on ne calcule d'un fois chaque fibonacci.
09/12/2007, 22h26
aoyou

Citation:

Envoyé par Garulfo

ce que tu écris est aussi difficile que de penser la forme itérative, puisque finalement écrire une forme récursive terminale c'est de penser de manière itérative sous un certain angle.

C'est bien pour cela que j'ai écrit

Citation:

De cette version en découle naturellement la version itérative.

Pour preuve, un compilateur sait très bien le faire.