+ Répondre à la discussion
Affichage des résultats 1 à 9 sur 9
  1. #1
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 606
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 606
    Points : 5 855
    Points
    5 855

    Par défaut Les nombres parfaits

    Bonjour

    je me suis amusé à écrire un code pour calculer les nombres parfaits (nombre dont la somme des diviseurs propres est égale à lui-même exemple 6 = 1 +2 + 3)

    Voici mon code
    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
    import List
    
    -- creation de la liste des diviseurs possibles
    lst_nb :: Int -> [Int]
    lst_nb n = let x = div n 2 in [1..x] 
    
    -- Teste si y est un diviseur de x
    is_diviseur :: Int -> Int -> Bool
    is_diviseur x y = 0 == mod x y
    
    -- renvoie
    -- y si x divise y
    -- 0 sinon
    -- pour pouvoir effectuer la somme des diviseurs
    -- on doit surement pouvoir faire beaucoup mieux
    -- avec une fonction comme filter de Scheme
    diviseur :: Int -> Int -> Int
    diviseur x y = 
    	case (is_diviseur x y) of
    		True -> y
    		False -> 0
    	
    -- retourne la somme des diviseurs d'un nombre	
    somme_div :: Int -> Int
    somme_div x = foldl (+) 0 (map (diviseur x) (lst_nb x))
    
    -- teste la "perfection" d'un nombre
    is_perfect :: Int -> Bool
    is_perfect x = x == somme_div x
    
    -- liste des nombres parfaits
    -- J'aurais aimé l'écrire sous forme de filter 
    list_perfect :: Int -> [Int]
    list_perfect 2 = []
    list_perfect x = 
    	case (is_perfect x) of
           True -> x : list_perfect (x - 1)
           False -> list_perfect (x - 1)
    Je ne suis pas très content des fonctions diviseur et list_perfect mais je manque de connaissances Haskell pour pouvoir faire mieux.

    Pouvez-vous m'indiquer une piste ?

    Merci
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  2. #2
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 606
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 606
    Points : 5 855
    Points
    5 855

    Par défaut

    Pas la peine, je viens de trouver
    filter existe aussi en Haskell
    Désolé

    code final
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    import List
    
    -- creation de la liste des diviseurs possibles
    lst_nb :: Int -> [Int]
    lst_nb n = let x = div n 2 in [1..x] 
    
    -- Teste si y est un diviseur de x
    is_diviseur :: Int -> Int -> Bool
    is_diviseur x y = 0 == mod x y
    	
    -- retourne la somme des diviseurs d'un nombre	
    somme_div :: Int -> Int
    somme_div x = foldl (+) 0 (filter (is_diviseur x) (lst_nb x))
    
    -- teste la "perfection" d'un nombre
    is_perfect :: Int -> Bool
    is_perfect x = x == somme_div x
    
    -- liste des nombres parfaits
    list_perfect :: Int -> [Int]
    list_perfect y = filter (is_perfect) [1..y]
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  3. #3
    Membre du Club

    Inscrit en
    novembre 2005
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 17
    Points : 65
    Points
    65

    Par défaut

    Il y a plus court (pas forcément mieux ) :
    [ q | q <- [1..], q == sum [ p | p <- [1..q-1], q `mod` p == 0]] !! N

    Cette ligne te donne le Nème nombre parfait :
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Prelude> let np = [ q | q <- [1..], q == sum [ p | p <- [1..q-1], q `mod` p == 0]]
    Prelude> np !! 0
    6
    Prelude> np !! 1
    28
    Prelude> np !! 2
    496
    Prelude> np !! 3
    8128
    ++

  4. #4
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 606
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 606
    Points : 5 855
    Points
    5 855

    Par défaut

    Merci de ton code.
    Comme je débute en Haskell, j'ai encore besoin d'écrire du code "qui me parle".
    Mais je commence à comprendre des lignes qui me paraissaient totalement absconses au début !
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  5. #5
    Membre du Club

    Inscrit en
    novembre 2005
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 17
    Points : 65
    Points
    65

    Par défaut

    Je débute aussi l'haskell et c'est vrai qu'au début ça fait un peut bizzard !
    Par contre, si je peux te donner un conseil, ça serait d'oublier tout ce que tu as appris en programmation impérative et mettre a profit tout ce que le lambda calcul t'offre.
    En effet, le gros problème de l'haskell (à mon sens), c'est qu'il faut des bases en lambda calcul pour le pratiquer correctement.

    Je pense notamment à l'évaluation paresseuse, une usage agressif de la récursivité, et les lambda fonctions. Je te conseil de te renseigner là dessus. Les conférences du collège de France sont absolument génial à ce sujet !

    Pour finir, n'oublie jamais que l'Haskell est un des langages les moins "verbeux" et qu'un programme long signifie souvent un programme mal conçu !

    Bonne continuation !

  6. #6
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 606
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 606
    Points : 5 855
    Points
    5 855

    Par défaut

    Citation Envoyé par DigitalGuru Voir le message
    Par contre, si je peux te donner un conseil, ça serait d'oublier tout ce que tu as appris en programmation impérative et mettre a profit tout ce que le lambda calcul t'offre.
    Pour ce qui est du grand saut conceptuel, je l'ai fait lorsque je suis passé du C au Prolog !
    Mais c'est vrai que j'ai fait pas mal de Scheme à un moment et je m'aperçois maintenant que je n'avais pas pigé le paradigme fonctionnel (si tant est que je l'ai vraiment bien compris)

    Pour ce qui est du lambda calcul, j'en fait un peu il y a très longtemps, c'était extrêmement théorique et j'ai un peu tout oublié !
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  7. #7
    Invité de passage
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2012
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Indre et Loire (Centre)

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

    Informations forums :
    Inscription : septembre 2012
    Messages : 6
    Points : 4
    Points
    4

    Par défaut

    Je ne sais pas trop si un programme hyper-concis est pour autant mieux.
    L'exemple des nombres parfaits est intéressant, car le code donné dans les messages précédents relève assez de la force brute.
    Et le moins qu'on puisse dire est qu'il est vraiment très lent.
    Je me suis amusé à passer par la recherche des facteurs premiers en les composants pour retrouver les diviseurs.
    Cette approche est bien plus rapide (8 fois pour 10 000 nombres et je ne suis pas sûr qu'elle soit quadratique contrairement à ton code). C'est moins déclaratif (je me méfie des solutions compactes souvent peu efficaces) et surtout cela illustre une des grandes forces d'Haskell : la composition. Ici, on passe par les fonctions sur les listes pour regrouper les facteurs par puissance croissante puis les monades opèrent la composition finale qu'il n'y a plus qu'à sommer...
    C'est pas mal de code, mais si vous pouvez faire mieux et plus vite... (quoique je me suis demandé si dans le code précédent on 'chassait' jusqu'à la racine carrée cela n'accélererait pas grandement aussi... à tester)

    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
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    -- creation de la liste des diviseurs possibles
    lst_nb :: Int -> [Int]
    lst_nb n = let x = div n 2 in [1..x] 
    
    -- Teste si y est un diviseur de x
    is_diviseur :: Int -> Int -> Bool
    is_diviseur x y = 0 == mod x y
    	
    -- retourne la somme des diviseurs d'un nombre	
    somme_div :: Int -> Int
    -- somme_div x = foldl (+) 0 (filter (is_diviseur x) (lst_nb x))
    somme_div x = div (sum $ divisors x False) 2
    
    -- teste la "perfection" d'un nombre
    is_perfect :: Int -> Bool
    is_perfect x = x == somme_div x
    
    -- liste des nombres parfaits
    list_perfect :: Int -> [Int]
    list_perfect y = filter (is_perfect) [1..y]
    
    -- Integral square root of an Integral
    -- long division method 
    isqrtLD :: Integral i => i -> i
    isqrtLD n =
     let lDiv n b 
          | n<0 = b - 1
          | otherwise =
             let n' = n - b
                 b' = b + 1
                 n'' = n' - b'
             in lDiv n'' b'
     in lDiv n 0
     
    -- list of prime numbers
    primes :: [Int]
    primes = sieve (2:[3,5..])
      where
        sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
        
    -- prime factors of an integer
    -- e.g. 1,008 -> [2,2,2,2,3,3,7]
    primeFactors :: Int -> [Int]
    primeFactors nb =
     factors primes nb
      where
       sqr = isqrtLD nb
       factors qs@(p:ps) n
        | p > sqr = if n == 1 then [] else [n] 
        | m == 0 = p : factors qs d
        | otherwise = factors ps n
        where (d,m) = n `divMod` p
     
    -- take nb and gets a list of its factors listed in successive powers
    -- e.g. 504
    --      primeFactors -> [2, 2, 2, 3, 3, 7]
    --      group -> [[2, 2, 2], [3, 3], [7]]
    --      result -> [[1,2,4,8],[1,3,9],[1,7]]
    powersOfPrimeFactors :: Int -> [[Int]]
    powersOfPrimeFactors nb =
      let pfct = group $ primeFactors nb
          mapAcc accSameFactor =
            snd $ mapAccumL (\acc x-> let m = acc*x in (m, m)) 1 accSameFactor
      in map (1:) $ map mapAcc pfct
    
    -- gives the list of divisors (unsorted or sorted depending on bool) of
    -- an integer
    -- e.g. 496 False -> [1,31,2,62,4,124,8,248,16,496]   
    --      8128 True -> [1,2,4,8,16,32,64,127,254,508,1016,2032,4064,8128]   
    divisors :: Int -> Bool -> [Int]  
    divisors n bSort =
     let p = powersOfPrimeFactors n
         multList fct1 fct2 =  -- fct1 >>= \x -> map (x*) fct2
           do
            x <- fct1
            y <- fct2
            return (x*y)
         r = foldl multList [1] p
     in if bSort then (sort r) else r

  8. #8
    Rédacteur/Modérateur
    Avatar de Trap D
    Inscrit en
    septembre 2003
    Messages
    4 606
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 4 606
    Points : 5 855
    Points
    5 855

    Par défaut

    Bonjour

    Merci de ta réponse. Malheureusement, je n'ai pratiquement plus fait d'Haskell depuis que j'ai posté ici.
    J'ai essayé de compiler avec WinGHCI et j'ai obtenu ces erreurs :
    Prelude> :cd C:\a-travail\developpements\Haskell
    Prelude> :load "perfect-1.hs"
    [1 of 1] Compiling Main ( perfect-1.hs, interpreted )

    perfect-1.hs:61:14: Not in scope: `group'

    perfect-1.hs:63:15: Not in scope: `mapAccumL'

    perfect-1.hs:79:20:
    Not in scope: `sort'
    Perhaps you meant `sqrt' (imported from Prelude)
    Failed, modules loaded: none.
    Prelude>
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

  9. #9
    Invité de passage
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2012
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Indre et Loire (Centre)

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

    Informations forums :
    Inscription : septembre 2012
    Messages : 6
    Points : 4
    Points
    4

    Par défaut

    Oups, désolé, j'ai oublié les imports :

    Code :
    1
    2
    import List
    import Monad

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •