Algo de Heron d'Alexandrie récursif en C

Résolu/Fermé

alfonseldric Messages postés 8 Date d'inscription lundi 13 avril 2009 Statut Membre Dernière intervention 15 avril 2009 - 13 avril 2009 à 19:19
thierry - 23 nov. 2009 à 11:43

Bonjour,
je suis en train d'essayer de programmer le calcul d'une racine carrée approché au moyen de l'algorithme de Heron d'Alexandrie en C, le tout en récursif.
J'ai beau me creusé la tête depuis quelques heures le seul code que j'arrive à trouver est celui-ci dessous qui, comme vous vous en doutez, ne marche pas. Je me sis donc résolut à venir demander de l'aide ici, mais aussi et surtout des explication et aide pour que je puisse me débrouiller à l'avenir.
Merci d'avance.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

float racine_carree(int a, int n)
{
    float x,b,z;
    x=1;
    while((x*x)<a)
    {
        x=x+1;
    }
    b=x;
    if((x*x)==a)
    {
        return x;
    }
    else
    {
        if(n==0)
        {
            return a;
        }
        else
        {
            if(n==1)
            {
                x=(1/2)*(x+(a/x));
                return x;
            }
            else
            {
                z=(1/2)*((racine_carree(b,n-1))+(a/(racine_carree(b,n-1))));
                printf("Voila x= %0.4f \t pour l'etape n= %d \n",b,n);
                return z;
            }
        }
    }
}

int main(){
    int a,n;
    float x;
    printf("rentrez le nombre :");
    scanf("%d",&a);
    printf("\n rentrez le nombre d'iteration :");
    scanf("%d",&n);
    x=racine_carree(a,n);
    printf("voila la racine carree %0.4f \t",x);
    printf("la racine carree trouvee par sqrt est: %f",sqrt(a));
    }

A voir également:

Algo de Heron d'Alexandrie récursif en C
Telecharger algo pour pc - Télécharger - Édition & Programmation
Grep récursif - Forum Programmation
Ccf algo bts sio ✓ - Forum Études / Formation High-Tech
Algo poker - Forum Algorithmes / Méthodes
Jouer à alexandra ledermann 6 gratuitement en ligne - Forum Jeux vidéo

11 réponses

Réponse 1 / 11

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
14 avril 2009 à 14:40

Salut,
Ton programme me paraît bien compliqué pour un algorithme aussi simple.
Formulé simplement, l'algorithme consiste à calculer la suite :
Soit N la racine à calculer
x0=a (avec a assez proche de racine de N, la partie entière par exemple). A la limite tu peux mettre 0.
x(n+1)=0.5*(x(n)+A/x(n)).

La fonction, en version récursive donnerait donc :

double racine_carree(const double chiffre, double xn, int iteration){
    if(iteration==0)
        return xn;
    else
        return racine_carree(chiffre,0.5*(xn+chiffre/xn),iteration-1);
}

Réponse 2 / 11

lucieb31 Messages postés 345 Date d'inscription mercredi 14 janvier 2009 Statut Membre Dernière intervention 28 juillet 2012 62
13 avril 2009 à 19:42

l'erreur que je vois est que tu divise un int par un float, et ceci peut te donner des resultats faux, donc pour eviter ce genre d'erreur, je te conseil de tout mettre en float, ou alors de convertir lorsqu'il le faut tes int en float. de meme que lorsque tu refais appelle a ta fonction, elle prend un int en entré, et toi tu lui rentre un float.
@+

Réponse 3 / 11

alfonseldric Messages postés 8 Date d'inscription lundi 13 avril 2009 Statut Membre Dernière intervention 15 avril 2009
13 avril 2009 à 19:58

En effet, merci de la remarque, voila le code une fois cela corrigé (j'ai aussi changé le nom des variable pour le rendre peut être un peu plus lisible ^^) :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

float racine_carree(float chiffre, int iteration)
{
    float CasBase,CasUn,Racine,b;
    CasBase=1.0;
    while((CasBase*CasBase)<chiffre)
    {
        CasBase=CasBase+1.0;
    }
    b=CasBase;
    if((CasBase*CasBase)==chiffre)
    {
        return CasBase;
    }
    else
    {
        if(iteration==0)
        {
            return chiffre;
        }
        else
        {
            if(iteration==1)
            {
                CasUn=(1.0/2.0)*(CasBase+(chiffre/CasBase));
                return CasUn;
            }
            else
            {
                Racine=(1.0/2.0)*((racine_carree(b,iteration-1))+(chiffre/(racine_carree(b,iteration-1))));
                printf("Voila x= %0.4f \t pour l'etape n= %d \n",b,iteration);
                return Racine;
            }
        }
    }
}

int main(){
    int etape;
    float num,racine;
    printf("rentrez le nombre :");
    scanf("%f",&num);
    printf("\n rentrez le nombre d'iteration :");
    scanf("%d",&etape);
    racine=racine_carree(num,etape);
    printf("voila la racine carree %0.4f \t",racine);
    printf("la racine carree trouvee par sqrt est: %f",sqrt(num));
    }

Réponse 4 / 11

alfonseldric Messages postés 8 Date d'inscription lundi 13 avril 2009 Statut Membre Dernière intervention 15 avril 2009
14 avril 2009 à 13:58

Je tien à préciser, j'ai bien corriger selon la remarque que m'a fait lucieb31 cependant mon algo est toujours loin de marché, et de mon coté je n'arrive toujours pas a trouver de solution, je suis donc toujours à la recherche d'un coup de main :D

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question

Réponse 5 / 11

alfonseldric Messages postés 8 Date d'inscription lundi 13 avril 2009 Statut Membre Dernière intervention 15 avril 2009
14 avril 2009 à 16:18

Merci beaucoup pour ton coup de main fiddy, grâce à ta solution mon programme marche (j'ai mis le code ci-dessous, ça peut toujours aider si quelqu'un ce retrouve dans la même galère que moi ^^). Pour info, la première partie de la fonction, qui ce retrouve maintenant dans le main, sert juste a optimiser le programme. Enfin, ma consigne exacte été de " Écrire une fonction prenant en paramètre un réel a et un entier n, qui calcule et affiche les n premiers termes de la suite. On affichera également la racine carrée de a, à titre de comparaison (on utilisera pour cela la fonction sqrt de la bibliothèque math.h)." or, avec cette solution j'ai 3 paramètres :s donc si quelqu'un a une idée je suis preneur parce que je vois pas comment faire ...

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double racine_carree(double chiffre, int iteration, double xn)
{
    double CasUn,Racine;

    if(iteration==0){
        return xn;
    }
    else{
        if(iteration==1){
            CasUn=(1.0/2.0)*(xn+(chiffre/xn));
            return CasUn;
        }
        else
        {
            Racine=racine_carree(chiffre,iteration-1,(0.5*(xn+(chiffre)/xn)));
            printf("Voila x%d= %0.4lf \t pour l'etape n= %d \n",iteration,xn,iteration);
            return Racine;
        }
    }
}

int main(){
    int etape;
    float num, CasBase,b;
    double racine;
    printf("rentrez le nombre :");
    scanf("%f",&num);
    printf("\n rentrez le nombre d'iteration :");
    scanf("%d",&etape);
    CasBase=0.0;
    if(num==0){
        b=0;
    }
    else{
        do{
            CasBase=CasBase+1.0;
        }while((CasBase*CasBase)<num-1);

        b=CasBase;
    }
    if((b*b)==num){
        printf("La racine carree de %.0f est %.0f , resultat trouve apres 0 iteration.\t",num,b);
    }
    else{
        racine=racine_carree(num,etape,b);
        printf("Voila la racine carree %lf . \t",racine);
    }
    printf("La racine carree trouvee par sqrt est: %lf \n",sqrt(num));
    system("PAUSE");
}

Réponse 6 / 11

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
14 avril 2009 à 16:49

Utilise plutôt des double, c'est mieux ;-))). Ou alors utilise fsqrt au lieu de sqrt pour renvoyer un float.
Attention à la comparaison entre nombres à virgules flottantes.
if((CasBase*CasBase)==num)
Il faut s'assurer que la valeur absolue de la différence est très proche de 0.
Par exemple avec un epsilon absolu cela donne : if( (fabs(CasBase*CasBase-num)<1e-5) { ...
N'oublie pas le return 0; final.

Sinon, si tu dois le faire avec deux arguments, tu peux t'en sortir en définissant une variable statique (static double xn=b;)

Réponse 7 / 11

alfonseldric Messages postés 8 Date d'inscription lundi 13 avril 2009 Statut Membre Dernière intervention 15 avril 2009
14 avril 2009 à 17:53

Voila mon code après modification via tes conseils, qu'en pense tu cela a l'air de marcher et de remplir les conditions de mon énoncé, si tu vois des bugs hésite pas a me le signalé, en tout cas merci beaucoup, encore.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

static float chiffre;

double racine_carree(double xn, int iteration)
{
    double CasUn,Racine;
    if(iteration==0){
        return xn;
    }
    else{
        if(iteration==1){
            CasUn=(1.0/2.0)*(xn+(chiffre/xn));
            return CasUn;
        }
        else
        {
            Racine=racine_carree((0.5*(xn+(chiffre)/xn)),iteration-1);
            printf("Voila x%d= %0.4lf \t pour l'etape n= %d \n",iteration,xn,iteration);
            return Racine;
        }
    }
}

int main(){
    int etape;
    float CasBase,b;
    double racine;
    printf("rentrez le nombre :");
    scanf("%f",&chiffre);
    printf("\n rentrez le nombre d'iteration :");
    scanf("%d",&etape);
    CasBase=0.0;
    if(chiffre==0){
        b=0;
    }
    else{
        if(fabs(chiffre-2.0)<1e-5){
            CasBase=1;
        }
        else{
            do{
                CasBase=CasBase+1.0;
            }while((CasBase*CasBase)<chiffre-1);
            b=CasBase;
        }
    }
    if(fabs((b*b)-chiffre)<1e-5){
        printf("La racine carree de %.0f est %.0f , resultat trouve apres 0 iteration.\t",chiffre,b);
    }
    else{
        racine=racine_carree(b,etape);
        printf("Voila la racine carree %lf . \t",racine);
    }
    printf("La racine carree trouvee par sqrt est: %lf \n",sqrt(chiffre));
    system("PAUSE");
    return 0;
}

Réponse 8 / 11

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
14 avril 2009 à 18:19

Mets tout en double plutôt ;-))). Sauf cas très particulier, le float est moins bien que le double.

scanf("%lf",&chiffre);

printf("Voila la racine carree %f . \t",racine);
printf("La racine carree trouvee par sqrt est: %f \n",sqrt(chiffre));

Mets le prototype int main(void).

Remarques facultatives mais conseillées ^^:
Après, tu peux simplifier l'écriture de code en ajoutant des fonctions statiques (par exemple pour le calcul de b.
Tu n'as pas besoin de créer une variable pour la retourner juste après.

return (0.5)*(xn+chiffre/xn); /*pas besoin de CasUn*/

Et pour finir, rajoute des commentaires (vivement conseillés, surtout si c'est noté par le prof ^^).

Cdlt

Réponse 9 / 11

alfonseldric Messages postés 8 Date d'inscription lundi 13 avril 2009 Statut Membre Dernière intervention 15 avril 2009
14 avril 2009 à 19:39

Voilà le programme final (normalement), j'ai essayer de travailler la mise en page source/programme et je n'ai pas relevé de bugs particulier, j'ai aussi essayé d'appliquer tes bons conseils a tout mon programme :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//Déclaration de variable globale
static double chiffre;
static int etape;

//Déclaration de la fonction
double racine_carree(double xn, int iteration)
{
    double Racine;
    if(iteration==0){
        return xn;                  //Cas de base de la fonction
    }
    else{
            printf("\t%d)\t Pour l'etape n= %d \n",etape-iteration,etape-iteration);    //Affiche l'étape de la suite mathématique
            printf("\t|____________________________________________|\n");   //Mise en Page
            printf("\t\t voila x%d= %0.15lf \n ",etape-iteration,xn);                   //Affiche la valeur de x(n)
            printf("\t|____________________________________________|\n");   //Mise en page
            return racine_carree((0.5*(xn+(chiffre)/xn)),iteration-1);                  //Retourne la valeur de la racine carrée grace à un appel récursif
    }
}

//Déclaration du Main
int main(){
    double racine,CasBase,b;
    printf("rentrez le nombre :");
    scanf("%lf",&chiffre);          //Saisie du chiffre dont l'utilisateur veut la racine carrée
    printf("\n rentrez le nombre d'iteration :");
    scanf("%d",&etape);             //Saisie du nombre d'itération a produire (précision)
    system("echo,Pour voir le calcul de la racine carree selon la methode de Heron d'Alexandrie "); //Mise en page
    system("PAUSE");                        //Mise en page
    CasBase=0.0;                    //initialisation de CasBase
    if(chiffre==0){
        b=0;                        //cas particulier 1
    }
    else{
        if(fabs(chiffre-2.0)<1e-5){
            b=1;              //cas particulier 2
        }
        else{
            do{
                CasBase=CasBase+1.0;
            }while((CasBase*CasBase)<chiffre-1);
            b=CasBase;              //valeur approché par default de la racine carrée recherché pour optimiser le programme
        }
    }
    if(fabs((b*b)-chiffre)<1e-5){
        printf("La racine carree de %.0f est %.0f , resultat trouve apres 0 iteration.\n",chiffre,b);   //cas particulier où la racine carré est un entier naturel
    }
    else{
        printf("\t_____________________________________________\n");        //Mise en page
        racine=racine_carree(b,etape);      //Appel de la fonction racine carrée
        printf("La racine carree de %lf, d'apres mon programme, est donc %lf. \n",chiffre,racine);   //Affichage de la racine carrée trouvée par la fonction racine_carree
    }
    printf("La racine carree trouvee par sqrt est: %lf. \n",sqrt(chiffre)); //Affichage de la racine carrée trouvée par la fonction sqrt() de la bibliothèque math.h
    system("PAUSE");
    return 0;
}

Merci encore pour tout, et je mettrai en résolut demain si personne n'y a relevé de bug entre temps :).

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
14 avril 2009 à 20:12

T'as pas tout corrigé ma remarque pour printf :
printf("La racine carree de %f, d'apres mon programme, est donc %f \n",chiffre,racine); pas de %lf

En C, le prototype sans argument d'une fonction est type fonction(void).
Appliqué au main, cela donne : int main(void)

Sinon évite les variables globales. Pour chiffre effectivement, tu ne pouvais pas faire autrement vu que tu ne pouvais pas la passer en arguments de fonction et que tu devais l'initialiser par une valeur non constante. Par contre, pour la variable etape, tu peux t'en passer ;-)))).

Bon je vais faire encore mon chieur, je suis là pour ça après tout. T'as trop commenté ^^. Et du coup, c'est moins lisible. Il faut commenter juste les prototypes de fonctions, éventuellement expliquer l'algorithme s'il est compliqué. Aucun commentaire dans le code, à moins bien sûr d'une astuce que tu juges important d'expliquer.
Par exemple :

/*
 *Cette fonction permet de comparer deux entiers
 * 
 * Param a : entier, élément à comparer
 * Param b : entier, élément à comparer
 *
 * Return : 0 si les nombres sont égaux,
 *                1 si a > b
 *                -1 sinon
*/
int cmp(int a, int b) {

Réponse 10 / 11

alfonseldric Messages postés 8 Date d'inscription lundi 13 avril 2009 Statut Membre Dernière intervention 15 avril 2009
14 avril 2009 à 20:54

En effet certaine de tes remarques été passé à la trappes ^^" désolé, par contre la variable etape je l'ai déclarée en globale même si je sais que c'est très déconseillé pour un soucis de mise en page, pour ce qui est des commentaires, j'arrive jamais à savoir ce qui vaux le coup d'etre commenté ou pas -_-".
Voilà donc le code maintenant :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//Déclaration de variable globale
static double chiffre;
static int etape;

/*Déclaration de la fonction
Cette fonction sert à appliquer la formule de Heron d'Alexandrie pour le calcul d'une racine carrée
xn: Reel correspondant au cas x0 trouver grâce a la structure dans le main
    qui donne une approximation par defaut de la racine carrée du "chiffre"
*/
double racine_carree(double xn, int iteration)
{
    double Racine;
    if(iteration==0){
        return xn;
    }
    else{
            printf("\t%d)\t Pour l'etape n= %d \n",etape-iteration,etape-iteration);
            printf("\t|____________________________________________|\n");
            printf("\t\t voila x%d= %0.15lf \n ",etape-iteration,xn);
            printf("\t|____________________________________________|\n");
            return racine_carree((0.5*(xn+(chiffre)/xn)),iteration-1);
    }
}

//Déclaration du Main
int main(void){
    double racine,CasBase,b;
    printf("rentrez le nombre dont vous voulez connaitre la racine carree:");
    scanf("%lf",&chiffre);
    printf("\n rentrez le nombre d'iteration (nombre entier):");
    scanf("%d",&etape);
    system("echo,Pour voir le calcul de la racine carree selon la methode de Heron d'Alexandrie ");
    system("PAUSE");
    CasBase=0.0;
    if(chiffre==0.0){
        b=0.0;
    }
    else{
        if(fabs(chiffre-2.0)<1e-5){
            b=1.0;
        }
        else{
            do{
                CasBase=CasBase+1.0;
            }while((CasBase*CasBase)<chiffre-1);
            b=CasBase;
        }
    }
    if(fabs((b*b)-chiffre)<1e-5){
        printf("La racine carree de %.0f est %.0f , resultat trouve apres 0 iteration.\n",chiffre,b);
    }
    else{
        printf("\t_____________________________________________\n");
        racine=racine_carree(b,etape);
        printf("La racine carree de %f, d'apres mon programme, est donc %f. \n",chiffre,racine);
    }
    printf("La racine carree trouvee par sqrt est: %lf. \n",sqrt(chiffre));
    system("PAUSE");
    return 0;
}

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
14 avril 2009 à 23:14

Un lf est passé à la trappe :p
printf("La racine carree trouvee par sqrt est: %f. \n",sqrt(chiffre));

Et enfin, je suis pas fan des sytem("PAUSE"). Ton programme respecte la norme et est portable. Et le system("PAUSE") casse tout ^^. Utilise getchar() à la place. Cela attendra que l'utilisateur tape une touche et la valide. Mais si ton prof est ok pour system("PAUSE"), ben laisse comme ça ^^.

Après, il manquerait de prendre en compte les cas où l'utilisateur ne rentre pas des nombres mais bon, cela complique un peu.

Voilà, j'ai fini mes critiques ;-))).

Réponse 11 / 11

alfonseldric Messages postés 8 Date d'inscription lundi 13 avril 2009 Statut Membre Dernière intervention 15 avril 2009
15 avril 2009 à 00:18

j'ai corrigé le dernier lf qui m'avait échappé :)
Pour les system("PAUSE") je les ai laissé parce que getchar(), j'ai eu beau essayer toute les façons et endroit qui me venez a l'esprit pour le placer, ne figeait pas le programme et donc sous windows le prog ce ferme desuite après avoir effectué l'opération.... donc a défaut ^^.
Enfin, pour le cas où l'utilisateur ne rentre pas de chiffre .... j'oublie parce que j'ai déjà largement outrepassé le programme que je suis censé connaitre de la matière, je pense que ça suffira :)

voila donc le code final définitif, point final etc :

/*
------------------------------------------------------------------------------------------------------------
--Nom: ************* Prenom: ***********                                                           --
--But du programme: Calcul d'une racine carrée d'après l'algorithme de Heron d'Alexandrie  --
--Lic 1 Info ****** : Devoir                                                                                            --
--Date de creation: Mardi 14 Avril 2009                                                                             --
--Date de modification:                                                                                                    --
--Raison de la modification:                                                                                             --
------------------------------------------------------------------------------------------------------------
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//Déclaration de variable globale
static double chiffre;
static int etape;

//Déclaration de la fonction
/*Cette fonction sert à appliquer la formule de Heron d'Alexandrie pour le calcul d'une racine carrée
xn: Reel correspondant au cas x0 trouver grâce a la structure dans le main
    qui donne une approximation par defaut de la racine carrée du "chiffre"
*/
double racine_carree(double xn, int iteration)
{
    double Racine;
    if(iteration==0){
        return xn;
    }
    else{
            printf("\t%d)\t Pour l'etape n= %d \n",etape-iteration,etape-iteration);
            printf("\t|____________________________________________|\n");
            printf("\t\t voila x%d= %0.15lf \n ",etape-iteration,xn);
            printf("\t|____________________________________________|\n");
            return racine_carree((0.5*(xn+(chiffre)/xn)),iteration-1);
    }
}

//Déclaration du Main
int main(void){
    int a;
    double racine,CasBase,b;
    printf("rentrez le nombre dont vous voulez connaitre la racine carree:");
    scanf("%lf",&chiffre);
    printf("\n rentrez le nombre d'iteration (nombre entier):");
    scanf("%d",&etape);
    printf("Pour voir le calcul de la racine carree selon la methode de Heron d'Alexandrie ");
    system("PAUSE");
    CasBase=0.0;
    if(chiffre==0.0){
        b=0.0;
    }
    else{
        if(fabs(chiffre-2.0)<1e-5){
            b=1.0;
        }
        else{
            do{
                CasBase=CasBase+1.0;
            }while((CasBase*CasBase)<chiffre-1);
            b=CasBase;
        }
    }
    if(fabs((b*b)-chiffre)<1e-5){
        printf("La racine carree de %.0f est %.0f , resultat trouve apres 0 iteration.\n",chiffre,b);
    }
    else{
        printf("\t______________________________________________\n");
        racine=racine_carree(b,etape);
        printf("La racine carree de %f, d'apres mon programme, est donc %f. \n",chiffre,racine);
    }
    printf("La racine carree trouvee par sqrt est: %f. \n",sqrt(chiffre));
    system("PAUSE");
    return 0;
}

fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 835
15 avril 2009 à 01:06

Pour les getchar(), c'était normal. C'est à gauche du buffer clavier qui contient '\n' à la suite des scanf.
Il suffisant donc de mettre un getchar() supplémentaire ^^.
Enfin en tout cas, bon travail ;-))).

thierry > fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022
23 nov. 2009 à 11:43

salut j ai bel et bienn essaye votre programme et il fonctionne parfaitement .
Cependant j amerais savoir comment faire pour modifier le programme de tel sorte ce soit l utilisateur qui entre la premiere approximation de la racine carre du nombre entrer et affiche le resultat apres cinq iterations
merci d avance.

thierry > fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022
23 nov. 2009 à 11:43

thierry
23 nov. 2009 à 11:40

Discussions similaires

Algorithme avec alg 32

Erreur de récupération de l'image sur première pro

Recherche récursive en UNIX

dichotomie recursive en c

[algorithme calcul pgcd]

Discussions similaires

Newsletters