IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Que fait produit cet algorithme ?


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Inscrit en
    Avril 2006
    Messages
    48
    Détails du profil
    Informations forums :
    Inscription : Avril 2006
    Messages : 48
    Points : 24
    Points
    24
    Par défaut Que fait produit cet algorithme ?
    Bonjour à tous, lundi, je passe un concours et il y a un peu d'algorithmique, j'ai des exemples de programmes et je n'arrive pas à en comprendre certains.

    Si quelqu'un peut m'expliquer pas à pas le programme que j'ai mit dessous
    il est dit que : / est l'opérateur de division entière
    mod est l'opérateur modulo

    Soit le programme suivant :

    FONCTION h(a :entier, b :entier) RESULTAT val :entier
    DEBUT
    SI a = 0 ALORS val <- 0 FIN SI
    SI (a mod 2) =1 ALORS
    val <- b + h(a/2, b*2)
    SINON
    val <- h(a/2, b*2)
    FIN SI
    FIN

    QCM : ce programme calcule :
    a) a*b
    b) a+b
    c) a^b
    d) a*2^b
    e) 2^(ab)

    J'avais une autre question, c'est quel est le résultat produit par 1,5 mod 2 ? ou bien encore 5,5 mod 2 ?
    Merci

  2. #2
    Membre éclairé
    Inscrit en
    Juin 2005
    Messages
    644
    Détails du profil
    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2005
    Messages : 644
    Points : 754
    Points
    754
    Par défaut
    résultat de cette récursion :
    a * b


    2eme demande :
    EXISTE pas
    l'opération modulo opère sur des entiers uniquement donc
    1.5 mod 2 tout comme 5.5 mod 2 n'a pas de sens.

  3. #3
    Membre à l'essai
    Inscrit en
    Avril 2006
    Messages
    48
    Détails du profil
    Informations forums :
    Inscription : Avril 2006
    Messages : 48
    Points : 24
    Points
    24
    Par défaut
    Merci pour ton aide j.p.mignot, peux tu m'expliquer pas à pas comment tu fais pour obtenir a*b ?

    J'y ai réfléchi pendant 1heure et impossible, je ne comprends pas le sens de fonction(a,b) si on ne sait pas ce que cette fonction doit exécuter.
    sin(pi) est une fonction définie, on doit exécuter le sinus de pi qui donne 0, mais FONTION(a,b) n'est pas une fonction définie.

  4. #4
    Membre éclairé
    Inscrit en
    Juin 2005
    Messages
    644
    Détails du profil
    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2005
    Messages : 644
    Points : 754
    Points
    754
    Par défaut
    Si elle est définie puisqu'elle donne a*b !
    mais elle l'est par récurrence. Evidemment cela est un exo car
    fire sa multiplication comme cela n'est pas le top!
    prenons un exemple a= 8*15= 120 et b=3 a*b=360

    a= 2^3 * 15
    appelons h(a,b)
    a mod 2 =0 donc on appelle h(a/2,2b) soit h(2^2 * 15,6)
    maintenant a=2^2 *15 et b=6
    a mod 2 =0 donc on appelle h(a/2,2b) soit h(2^1*15,12)
    maintenant a=2^1*15 et b=12 a mod 2 =0 donc
    on appelle h(a/2,2b) soit h(15,24)
    maintenant a=15 et b=24 ( ici on a en quelques sortes "transféré" le 2^n de a dans b ce qui ne change rien au produit a.b )

    maintenant a mod 2 = 1 pour tout le reste du cycle donc
    on retourne b + h(a/2,b*2) soit
    24 + h(7, 48 ) =
    24 + 48 + h(3,96 )=
    24 + 48 + 96 + h(1,192 )=
    24+48+96+192 = 360 = a*b d'origine

  5. #5
    Expert éminent

    Profil pro
    Fabricant et casseur d'avions
    Inscrit en
    Avril 2004
    Messages
    3 807
    Détails du profil
    Informations personnelles :
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Fabricant et casseur d'avions
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2004
    Messages : 3 807
    Points : 7 613
    Points
    7 613
    Par défaut
    Salut,

    Citation Envoyé par jeje00
    Merci pour ton aide j.p.mignot, peux tu m'expliquer pas à pas comment tu fais pour obtenir a*b ?
    Je me permets d'amener un petit complément...

    Tu peux faire ça par élimination.
    Tu prends a=0. En suivant l'algorithme, le résutat donne 0.
    Tu peux donc éliminer les réponses b (résultat b) et e (résultat 1)

    Ensuite, tu prends a=1. L'algo donne comme résultat b
    Tu peux éliminer les réponses c (qui donne 1) et d (qui donne 2^b, donc différent de b)

    Il ne reste que la a. Tu vérifies quand même...
    Si a=0, a*b=0, ok
    Si a/2=1 (c'est à dire a mod 2=1, ou a=2*c+1 avec c=a/2. Tu as alors a*b=(2*c+1)*b=2*c*b+b=b+2*c*b=b+h(c,2*b)=b+h(a/2,2*b)
    Sinon, a/2=0 (c'est à dire a=2*c, avec c=a/2), donc a*b=2*c*b=h(c,2*b)=h(a/2,2*b)

    Citation Envoyé par jeje00
    J'y ai réfléchi pendant 1heure et impossible, je ne comprends pas le sens de fonction(a,b) si on ne sait pas ce que cette fonction doit exécuter.
    sin(pi) est une fonction définie, on doit exécuter le sinus de pi qui donne 0, mais FONTION(a,b) n'est pas une fonction définie.
    Si l'informatique se limitait à utiliser des fonctions définies, on serait vite limités... C'est un peu le rôle du programmeur de créer des fonctions qui vont faire ce qu'il veut, et qui n'existent pas déjà (car le programmeur est fainéant... donc si ça existe déjà, il ne va pas le réinventer!).
    "Errare humanum est, sed perseverare diabolicum"

    Ma page sur DVP.com

  6. #6
    Membre éclairé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Points : 763
    Points
    763
    Par défaut
    J'ai même l'impression que tu calcules a*b pour a et b positifs.
    Aucune réponse à une question technique par MP.
    Ce qui vous pose problème peut poser problème à un(e) autre

    http://thebrutace.labrute.fr

  7. #7
    Membre à l'essai
    Inscrit en
    Avril 2006
    Messages
    48
    Détails du profil
    Informations forums :
    Inscription : Avril 2006
    Messages : 48
    Points : 24
    Points
    24
    Par défaut
    Merci pour vos explications. C'est plus claire comme cela.

    Cependant, j'ai fait une erreur dans la consigne, en fait, / est l'opérateur de division réelle et non entière, excusez moi, cela change t'il quelque chose ? Et c'est pour cela que j'avais demandé le résusltat 1,5 mod 2 tout au début.

  8. #8
    Membre éclairé
    Inscrit en
    Juin 2005
    Messages
    644
    Détails du profil
    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2005
    Messages : 644
    Points : 754
    Points
    754
    Par défaut
    ce n'est pas possible que se soit une division réelle!
    on arriverait à a/2 non entier si a n'est pas une puissance de 2 et ne serait plus un argument compatible avec le prototype de la fonction h.
    l'opérateur modulo n'est défini que sur les entiers...
    la récurence marche aussi pour a et / ou b négatif. Dans ce cas il faut juste ne pas utiliser a mod 2 mais abs(a) mod 2 et s'assurer que le compilateur resorte par exemple -7 ( et non -8 ) pour -15 div 2 !

  9. #9
    Membre éclairé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Points : 763
    Points
    763
    Par défaut
    Je disais juste par rapport à l'algo donné, qu'il se limitait aux nombres positifs. Mais l'explication supplémentaire est intéressante .
    Par contre, ça va pour de petits nombres, mais pour des nombres importants...
    Aucune réponse à une question technique par MP.
    Ce qui vous pose problème peut poser problème à un(e) autre

    http://thebrutace.labrute.fr

  10. #10
    Membre à l'essai
    Inscrit en
    Avril 2006
    Messages
    48
    Détails du profil
    Informations forums :
    Inscription : Avril 2006
    Messages : 48
    Points : 24
    Points
    24
    Par défaut
    Merci à vous tous pour ces explications, maintenant que je sais comment ça marche je vais réfléchir sur les autres. Peut etre que je reviendrais vous poser des questions tout à l'heure

  11. #11
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par j.p.mignot
    Si elle est définie puisqu'elle donne a*b !
    mais elle l'est par récurrence. Evidemment cela est un exo car
    fire sa multiplication comme cela n'est pas le top!
    C'est pourtant comme ça (ou plus précisément avec la variante itérative et la boucle dans l'autre sens, mais ça ne change rien au fond pour moi) que j'ai implémenté la multiplication quand je travaillais (en assembleur) avec un processeur n'ayant pas d'instruction de multiplications. C'est aussi comme ça que certains processeurs implémente leur instruction de multiplication.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  12. #12
    Membre éclairé
    Inscrit en
    Juin 2005
    Messages
    644
    Détails du profil
    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2005
    Messages : 644
    Points : 754
    Points
    754
    Par défaut
    Je ne savais pas que certains systèmes implémentaient la multiplication comme cela!
    Les quelques fois où j'ai programmé en ASM, j'avais des ordres MUL ou DIV que j'ai utilisé "as it"
    Je pensais sans y avoir réfléchi que l'on additionnait une série de shl de l'1 des 2 chiffres à partir de" l'expression" binaire de l'autre pour arriver à a*b
    (a et b >=0 ici).

    Je ne connaissais pas cet algorithme préalablement

    Merci du renseignement!

  13. #13
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par j.p.mignot
    Je pensais sans y avoir réfléchi que l'on additionnait une série de shl de l'1 des 2 chiffres à partir de" l'expression" binaire de l'autre pour arriver à a*b
    (a et b >=0 ici).
    : Cet algo ne fait rien d'autre (shl c'est *2, tester le bit de poid faible, c'est mod 2 == 1, shr c'est /2).
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  14. #14
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Sauf qu'ils l'implémentent en itératif et non en recursif

  15. #15
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par Miles
    Sauf qu'ils l'implémentent en itératif et non en recursif
    Comme je l'ai déjà écrit, ça ne change rien au fond pour moi. On peut passer mécaniquement d'une version à l'autre (prendre de préférence un compilateur pour un langage fonctionnel, ceux pour les langages impératifs implémentant rarement cette transformation).
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  16. #16
    Membre éclairé
    Inscrit en
    Juin 2005
    Messages
    644
    Détails du profil
    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2005
    Messages : 644
    Points : 754
    Points
    754
    Par défaut
    Cet algo ne fait rien d'autre (shl c'est *2, tester le bit de poid faible, c'est mod 2 == 1, shr c'est /2).
    Evidemment.
    Je pensais plutôt à une implémentation non récursive comme par exemple:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    function MUL &#40;a,b &#58; integer &#41; &#58; integer; // a et b >=0 si non shl,  shr ne sont pas utilisables
    var resultat &#58; integer; k &#58; byte;
       begin
       resultat&#58;=0;
       k&#58;=0;
       while b <> 0 do
          begin
          if b and 1 = 1 then inc&#40;resultat,a shl k&#41;;
          inc&#40;k&#41;;
          b&#58;= b shr 1;
          end;
       MUL&#58;=resultat;
       end;
    Comme vous le présentez, l'approche récursive doit être plus fonctionnelle . Cela me surprend juste un peu à priori.

  17. #17
    Membre à l'essai
    Inscrit en
    Avril 2006
    Messages
    48
    Détails du profil
    Informations forums :
    Inscription : Avril 2006
    Messages : 48
    Points : 24
    Points
    24
    Par défaut
    Bonjour, je voulais vous remercier pour l'algorithme d'hier. J'ai posté un nouveau sujet pour ne pas polluer celui la car ça n'a rien à voir avec les algorithmes. Si vous voulez voir http://www.developpez.net/forums/viewtopic.php?t=481203

    A bientot

  18. #18
    Inactif   Avatar de Médiat
    Inscrit en
    Décembre 2003
    Messages
    1 946
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 946
    Points : 2 227
    Points
    2 227
    Par défaut
    Citation Envoyé par j.p.mignot
    l'opérateur modulo n'est défini que sur les entiers...
    Quelque soit a et b des réels, il existe un couple unique (n, r) où n est un entier, et r un réel vérifiant 0 <= r < b et tel que :
    a = b*n + r, l'opérateur modulo est donc parfaitement défini par
    a mod b = r.
    Cette opérateur est implémenté sous forme de fonction sous le nom fmod en C et en PHP.
    MOD sous ORACLE et % sous SQLServer fonctionne très bien avec des "réels".
    Par contre aussi bien ORACLE que SQLServer se plantent avec les négatifs (Pour le C il y a trop longtemps que je n'ai pas utilisé cette fonction pour me souvenir si il y a aussi ce problème).
    J'affirme péremptoirement que toute affirmation péremptoire est fausse
    5ième élément : barde-prince des figures de style, duc de la synecdoque
    Je ne réponds jamais aux questions techniques par MP

  19. #19
    Membre à l'essai
    Inscrit en
    Avril 2006
    Messages
    48
    Détails du profil
    Informations forums :
    Inscription : Avril 2006
    Messages : 48
    Points : 24
    Points
    24
    Par défaut
    D'après ce que tu dis médiat, et si j'ai bien compris, 1,5 mod 2 = 1,5 ???

  20. #20
    Membre éclairé
    Inscrit en
    Juin 2005
    Messages
    644
    Détails du profil
    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2005
    Messages : 644
    Points : 754
    Points
    754
    Par défaut
    avec C / C++ ( borland )
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    Double a;
    void xx&#40;void&#41;;
    &#123;
    a = 3.2;
    a = a % 2;
    &#125;
    donne [C++ Erreur] Unit1.cpp( 21 ): E2060 Utilisation incorrecte de la virgule flottante

    Avec Delphi
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
     
    var a &#58; Real;
    procedure xx;
    begin
    a&#58;=3.2;
    a &#58;= a mod 2;
    end;
    donne
    [Erreur] Unit1.pas( 28 ): Opérateur non applicable à ce type d'opérande

    FreePascal lui aussi conduit à une erreur de compilation.


    MOD n'existe que sur des entiers.

    Il est possible que certains compilateurs proposent des fonctions qui étendent mod pour des floattingpoints ( fmod ) mais cela serait conjoncturel et non portable.
    en math en tout cas ne pas utiliser mod sur des non entiers !!
    Avec les mots clefs arithmétique, modulo, congruence, on trouve quantité d'articles sur le WEB.

Discussions similaires

  1. Que fait cet algorithme ?
    Par fiboulle dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 11/11/2009, 15h59
  2. Réponses: 9
    Dernier message: 28/03/2005, 00h29
  3. mais que fait upper_range() dans un multimap?
    Par porcher dans le forum C++
    Réponses: 7
    Dernier message: 18/02/2005, 23h21
  4. comment savoir ce que fait mon pointeur??
    Par elekis dans le forum C++
    Réponses: 9
    Dernier message: 30/11/2004, 13h42
  5. Mais que fait static ???
    Par elsargento dans le forum C
    Réponses: 4
    Dernier message: 25/09/2003, 10h55

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo