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

[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]

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

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

[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 ), c'était juste l'efficacité niveau temps de codage... Donc assez fainéant sur ce coup

[siegfried64]

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

[Sve@r]

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 :

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

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 :

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

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 :

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

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

[AuraHxC]

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

[Rukia]

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

si elle est en vie

[AuraHxC]

Pourtant je n'ai pas mis un code tueur

[aoyou]

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

Code :

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

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 :

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

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.

[nalia]

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

[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

[Garulfo]

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.

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

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

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

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