Discussion :

[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

[smilingFrog]

C'est vraiment abuser.....................

[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

[Garulfo]

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

[Garulfo]

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

[siegfried64]

Il aurait peut être fallu écouter en classe

c'est simple a dire
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

[AuraHxC]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Sve@r]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

[Melem]

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