Algo basé sur des nombres

**Kijer** · 10/12/2006, 17h09

Salut à tous..

J'en demande à vous car après avoir fait moultes essais, je n'arrive tjrs pas à ce que je souhaite.

J'explique :

Prenons l'exemple que nous avons 5 chiffres, par exemple

1 - 2 - 3 - 4 - 5

Puis j'ai un total de 10 que je dois trouver avec ma liste des 5 chiffres.

ensuite j'ai un nombre x que je pourrai modifier qui définit le nombre de chiffres que je dois utiliser, par exemple 3

A partir de ses infos, je vous montre un exemple concret.

chiffres = 1-2-3-4-5
total = 10
nbre_a_utiliser = 3

ce qui ferai :

5 + 3 + 2 = 10

mais aussi

5 + 4 + 1 = 10

donc en espérant ne pas me tromper, nous avons 2 possibilités pour un total de 10 avec les chiffres imposés. je rajouterai que le chiffre doit être utilisé qu'une seule fois dans la même ligne.

Donc à partir de ce raisonnement j'essaie de faire un script qui calcule ceci en me donnant le nbre de possibilités et les lignes possibles de façon automatique.

Mon pb est comment ...

Merci d'avance de m'aiguiller sur la marche à suivre..

**jobherzt** · 10/12/2006, 17h20

le plus simple est de faire un algorithme recursif, qui va tester toutes ls possibilité. le nombre de nombre sera la profondeur max a atteindre, et pense a sortir de la fonction des que tu atteins une somme superieur au nombre que tu veux atteindre, sinon tu vas perdre du tps de calcul.

**Kijer** · 10/12/2006, 21h21

j'suis pas un expert en algo même pas du tout, alors pourrez tu développez plus profondément stp

**Matthieu Brucher** · 11/12/2006, 10h53

http://www.developpez.net/forums/sho...d.php?t=246233

**Kijer** · 11/12/2006, 13h37

Merci du lien d 'un post super intéressant ! je vais l'étudier.
Pour ce qui est de rechercher avant de poster, il y a tellement d'appellation différente que à la fin je ne savais pas à quel mot rechercher.

**Aitone** · 11/12/2006, 15h36

Et il ne faut surtout pas oublier les opérations autorisées. Car si tu on peut prendre la multiplication et la division
Avec 1-2-3-4-5, pour faire 10, il y a bien plus que 2 solutions

**Kijer** · 11/12/2006, 15h56

Oui tu as raison, mais dans mon cas, seule l'addition est autorisée

**Zavonen** · 11/12/2006, 18h27

Voici une façon de résoudre votre problème. (Pour peu que je l'ai compris).
Vous pouvez donc recoder tout cela dans votre langage favori.

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
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
# La liste initiale des nombres que vous donnez en exemple
ListeNombres=[1,2,3,4,5]
 
# restitue la décomposition de n en système binaire sous forme de liste
# exemple si n=32
# la valeur retournée est [1,0,0,0,0]
def binaire (n): 
    L=[]
    while n:
        L.insert(0,n%2)
        n=n/2
    return L
 
 
#même chose que précédemment mais avec normalisation sur p chiffres
# en rajoutant au besoin des 0 devant
# exemple si n=32 et p = 7
# la valeur retournée est [0,0,1,0,0,0,0]
def normalise (n, p):
    L=binaire(n)
    while(len(L)<p):
        L.insert(0,0)
    return L
 
 
# fournit la liste des décompositions binaires
# des nombres de 0 à n-1
def enumbase2 (n):
    L=[]
    p=len(binaire(n))
    for i in range(0,n):
        L.append(normalise(i,p-1))
    return L
 
# effectue la somme des produits des éléments des 2 listes
def sommeprod(L1,L2):
    n=len(L1)
    s=0
    for i in range(0,n):
        s=s+L1[i]*L2[i]
    return s
 
# calcule le nombre d'éléments non nuls dans une liste
def nbtermes (L):
    s=0
    n=len(L)
    for i in range(0,n):
        if L[i]!=0:
            s=s+1
    return s
 
# recherche les possiblités d'obtenir la somme k
# avec p termes pris dans la liste donnée au début
def recherche (p,k):
    L=enumbase2(32)
    n=len(L)
    for i in range(0,n):
        M=L[i]
        nbt=nbtermes(M)
        sp=sommeprod(M,ListeNombres)
        if nbt==p and sp==k:
            print M
    return
 
 
# effectue la recherche que vous donnez en exemple
print recherche(3,10)

**reggae** · 11/12/2006, 20h13

Peut-être que le posteur ne l'est pas, mais moi je suis largué sur un point:
Pourquoi tout transformer en binaires? Et dernière question: pourquoi un p?

Quant à ma contribution, j'aurais simplement fait une petite boucle commençant par 1 et allant jusqu'à 5, en essayant chaque fois "10-(n+n+y)" où y est inclus dans une boucle "intérieure"... Ensuite, une fois les solutions trouvées, je les comparerais aux précédentes trouvées que j'aurais au préalable stockées dans un tableau...

Moins élégant...

**Nemerle** · 11/12/2006, 20h52

Envoyé par reggae

Peut-être que le posteur ne l'est pas, mais moi je suis largué sur un point:
Pourquoi tout transformer en binaires? Et dernière question: pourquoi un p?

parce que zavonen refuse de comprendre qu'il est sur un forum d'algorithmie

Malgré son passage en binaire pour aller plus vite, son code est loin d'être optimisé, car il n'a pas cherché à poser son algorithme...

**Zavonen** · 11/12/2006, 20h59

Envoyé par reggae

Peut-être que le posteur ne l'est pas, mais moi je suis largué sur un point:
Pourquoi tout transformer en binaires? Et dernière question: pourquoi un p?

En fait tout revient à trouver toutes les parties à 3 (ou p) éléments de l'ensemble disons {1,2,3,4,5} pour lesquelles la somme des éléments constituant la partie en question vaut k (disons ici 10).
De fait les parties d'un ensemble sont en bijection avec l'ensemble des applications de cet ensemble dans {0,1}. Ainsi une partie de l'ensemble s'identifie à un 5-uple {0,1,1,0,0} par exemple correspondant à {2;3}
L'utilisation du système binaire n'est ici qu'un moyen commode de générer toutes ces suites de façon automatique. La représentation binaire n'est pas exploitée en tant que telle.
Le paramètre p correspond donc au nombre d'éléments de la suite devant donner la somme k, on peut passer en paramètre 3 ou 4 ou 5, etc...
Il y a bien d'autres manières de faire et je ne doute pas que votre méthode fonctionne aussi.

**Kijer** · 11/12/2006, 23h12

Merci de votre aide, mais par contre pour le script qui transforme en binaire, aie j'ai mal au crane

, je suis loin loin d'avoir le niveau de l'exploiter ni même de le comprendre..

Bon mon php est moyen mais je me débrouille, par contre les algos je trouve ça super passionnant mais à chaque fois que je dois faire en faire un, c'est page blanche.. je ne sais jamais par ou commencer, savoir quel questions me poser, j'ai l'impression d'être con

sisi je vous assure ...

Bref pour en revenir a nos moutons.
La récursivité, j'emploie ce mot alors que je ne suis pas sur de sa définition..
Ce n'est pas par exemple le fait qu'une fonction s'auto rappelle dans elle même ?

Bref si c'est ça, je n'ai pas encore le niveau requis, alors on se contentera des boucles imbriquées, mais même la, je ne sais pas par où commencer...

Merci de votre aide..

**Kijer** · 12/12/2006, 10h28

Voila j'ai essayé de faire un pseudo code, j'ai essayé de poser la méthode que je ferai sur papier pour calculer.

Je déclare la variable tableau nombres avec comme valeur [1-2-3-4-5]
Je déclare la variable somme avec comme valeur 10
Je déclare la variable nbre_chiffres avec comme valeur 3

Je prend le premier chiffre du tableau nombres et j'ajoute les 2 nombres qui suivent (nbre_chiffres(3) - 1).
Je teste si le total vaut somme, si oui alors stocker dans une nouvelle variable tableau resultats la ligne correcte.
Ensuite prendre les 2 chiffres suivants (4 et 5) et réaliser la même chose que ci dessus.

Une fois tous les chiffres passés, nous prenons le second chiffre (2) et ensuite je refait l'étape 1 et 2 ( 2-1-3 puis 2.3.4 etc..)

Une fois toutes les combinaisons réalisées, nous avons toutes nos lignes dans la variable resultats.

Ensuite nous prenons ce dernier, et le trions par ordre croissant, puis nous vérifions si il y a des doublons (obligé) et les retirons.

Ensuite compter le nombre de lignes et afficher le résultat.

Dites moi si je suis sur la bonne piste au moins

et si je fais des conneries ou des trucs inutiles, ou si tout simplement il y a plus simple.

**Zavonen** · 12/12/2006, 12h05

Envoyé par Kijer

Voila j'ai essayé de faire un pseudo code, j'ai essayé de poser la méthode que je ferai sur papier pour calculer.

Dites moi si je suis sur la bonne piste au moins

et si je fais des conneries ou des trucs inutiles, ou si tout simplement il y a plus simple.

Il me semble que vous manquez des possibilités:
il faut partir de 1-2-3
puis ensuite pousser le dernier tant que c'est possible
123
124
125
quand on ne peut plus, pousser le deuxième
134
135
puis le troisième
145
quand on a épuisé toutes les possibilités avec le 1 on passe à 2
234
et on recommence
245

**Zavonen** · 12/12/2006, 12h23

Envoyé par Nemerle

parce que zavonen refuse de comprendre qu'il est sur un forum d'algorithmie

Malgré son passage en binaire pour aller plus vite, son code est loin d'être optimisé, car il n'a pas cherché à poser son algorithme...

Et oui ! il y a des têtes dures sur ce forum. Certains refusent d'intégrer que le mot "algorithmie" n'existe pas

L'algorithmique, quant à elle, existe certainement depuis celui qui lui a donné son nom, Muhammad ibn Musa al Kharezmi, il y a plus de 1000 ans. De fait on connaissant l'algorithme d'Euclide, le crible d'Erathostène, la méthode du calcul de pi pde Pythagore encore 1000 ans auparavant. Il y a fort à parier que tous ces braves gens ignoraient les: Faire tant que ... Fin Faire.
Ils devaient exprimer leurs idées dans la langue de l'époque, qui en grec, qui en arabe, et il semble qu'ils aient réussi à se faire comprendre.
Bien sûr que ce code nest pas optimisé, mais il utilise une technique générale donnant des sous-produits intéressants, par exemple l'ensemble de toutes les parties d'un ensemble donné, l'ensemble des parties à p éléments.
Voici une version meilleure, encore non optimisée.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# retourne la liste de toutes les parties de l'ensemble L (implémenté comme liste)
def parties (L):
    k=1
    n=len(L)
    for i in range(0,n):# calcule le cardinal de l'ensemble des parties de n
        k=k*2
    FoncCar=enumbase2(k) # toutes les fonctions caractéristiques
    m=len(FoncCar)
    Parties=[]
    for i in range (0,m):
        P=[]
        F=FoncCar[i]
        for j in range (0,len(F)):
            if (F[j]!=0):
                P.append(L[j])# reconstruit la partie à partir de sa f. c.
        Parties.append(P)
    return Parties
 
# retourne la liste de toutes les parties à p éléments de L
def partiesp (L,p):
    k=1
    n=len(L)
    for i in range(0,n):
        k=k*2
    FoncCar=enumbase2(k)
    m=len(FoncCar)
    Partiesp=[]
    for i in range (0,m):
        P=[]
        F=FoncCar[i]
        for j in range (0,len(F)):
            if (F[j]!=0):
                P.append(L[j])
        if(len(P)==p): #seule différence avec la précédente
             Partiesp.append(P)
    return Partiesp
 
# calcule la somme des éléments d'une liste
def somme (L):
    s=0
    for i in range (0,len(L)):
        s=s+L[i]
    return s
 
# recherche les possibilités d'obtenir la somme k
# avec p termes pris dans la liste donnée au début
def recherche2 (p,k):
    L=partiesp(ListeNombres,p)
    n=len(L);
    for i in range (0,n):
        P=L[i]
        if somme(P)==k:
            print P
    return
 
 
 
# effectue la recherche que vous donnez en exemple
recherche2(3,10)

**Nemerle** · 12/12/2006, 12h46

Envoyé par Zavonen

Il y a fort à parier que tous ces braves gens ignoraient les: Faire tant que ... Fin Faire.
Ils devaient exprimer leurs idées dans la langue de l'époque, qui en grec, qui en arabe, et il semble qu'ils aient réussi à se faire comprendre.

Oui, ils s'exprimaient dans leurs languages, avec un réel formalisme logique (= algorithme!!). Tu peux prendre par exemple Aristote, qui a produit la base de la logique la plus élémentaire (logique aristotélicienne). L'explication de al Kharezmi concernant la construction des fractions continues est aussi un exemple d'algorithme (pas de "Faire tant que", mais "réitérer ces calculs jusqu'à ce que...")

Tu te tires une balle dans le pied: quoi de plus simple qu'une explication en FRANCAIS, plutôt que du code à décripter??? Je ne lis quasiment jamais ton code, car je n'ai pas le temps de me fatiguer à comprendre ton raisonnement, alors qu'une explication en français est bien meilleure, même avec des Faire tant que!!

Algo basé sur des nombres

Algorithmes et structures de données

Discussions similaires

Partager

Partager