Discussion :

[Jean-Marc.Bourguet]

Meme s'il s'agit de l'initialisation faite qu'une fois, ne pas utiliser un algo exponentiel quand un algo lineraire existe, ce n'est pas de l'optimisation prematuree.

[Zavonen]

Il me semble que ton Cpn appelé avec les paramètres (13,33) donne:
242784340.
Il me semble que la valeur correcte est 573166440.
NB: la mienne échoue aussi mais elle n'a pas besoin de valeurs si grandes.
Note bien qu'on reste largement dans le domaine des unsigned.
L'explication est simple ta dernière multiplication provoque un débordement que la division qui suit n'arrive pas à récupérer.
Résultat des courses. Si on veut une fonction Cpn qui marche (autant que possible) il ne faut utiliser que des additions:

Code python :

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
#génération du triangle de Pascal au moyen d'un générateur
def Pascal():
    n,C=0,[1]
    yield n,C # retour du premier appel
    while True: # exécution des appels suivants
        n+=1
        D=C[:]
        D.insert(0,1)
        for i in xrange(1,len(C)):
            D[i]=C[i-1]+C[i] # relation de récurrence du Triangle de Pascal
        C=D
        yield n,C
 
# coefficients Cp,n
def Cpn(p,n):
    TP=Pascal()
    for i in range(0,n+1):
        L=TP.next()[1]
    return L[p]
 
def main():
    TP=Pascal()
    #voir le début du triangle de Pascal
    for i in xrange(0,11):
        print TP.next()
    # calculer un coefficient
    x=Cpn(13,33)
    print x
 
if __name__ == '__main__':
    main()

[Jean-Marc.Bourguet]

L'explication est simple ta dernière multiplication provoque un débordement que la division qui suit n'arrive pas à récupérer.

Il y a des jours ou on est distrait, j'ai oublie que (a OP b) mod n == (a mod b) OP (b mod n) n'est vrai que pour l'addition, la soustraction et la multiplication.

Résultat des courses. Si on veut une fonction Cpn qui marche (autant que possible) il ne faut utiliser que des additions:

Mais non, on est sur que soit result soit n-i est multiple de i+1, donc:

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
unsigned Cpn(unsigned p, unsigned n)
{
   unsigned result = 1;
   unsigned i;
   assert(p <= n);
   for (i = 0; i < p; ++i) {
       if (result % (i+1) == 0) {
           result /= (i+1);
           result *= (n-i);
       } else {
           assert((n-i) % (i+1) == 0);
           result *= (n-i)/(i+1);
       }
   }
   return result;
}

Pas meme besoin de passer en precision etendue (ce que je ferais avant d'utiliser un algo quadratique comme l'utilisation du triangle de Pascal).
Et sauf erreur, ca devrait etre bon tant que le resultat final est representable par un unsigned.

[zhao]

Bonjour a Tous :-)

En tout cas j'espère qu'ont auras le plaisir de voir ce problème sous forme d'algo génétique en C :-)

Pour info l'algo de Zavonen est plus performant que notre algo glouton :-)
son algo trouve le minimum connu pour 10 et 11 on se rapproche doucement mais surement d'une solution optimal "minimum connu " quel que soit le chiffre :-)

@+ :-)

[OpTim]

Bonjour à tous,

Tout d'abord, je tenais à vous remercier, vos échanges m'ont vraiment été d'un grand secours pour l'avancement de mon projet personnel.

Je me permet de dépoussiérer ce post car je m'intéresse à ce problème et je ne trouve que très peu de sources (avec algorithme) sur le sujet.
Je suis très intéressé par l'algorithme de Zavonen. Je souhaite moi-même intégrer un système réducteur dans un de mes projets personnels en C#.
J'ai pour cela besoin de rendre plus dynamique la génération de tels systèmes. Mon intégration de l'algorithme est quasiment terminée.
Seul un point me pose problème : il y a une valeur dans l'algorithme que je n'arrive pas à rendre plus dynamique.

En effet, je ne parvient pas à calculer convenablement le nombre de fois que Step() doit être répété dans la boucle principal (main).
Dans le cas de 10-6, il faudrait 13 (d'après le post 91)
Dans le cas de 11-6, il faudrait 22 (d'après le post 95)
Dans le cas de 12-6, il faudrait 41 (d'après le post 96)
S'agit-il d'un nombre évaluable ? Ou dois-je déterminer une condition d'arrêt pour l’exécution en boucle de Step() ?

Merci d'avance pour vos réponses.

[toki127]

bonjour à tous,

j'essaie de modifier le code donné dans ce post, mais j'aurai besoin d'aide...
si quelqu'un passe par là...

il ne s'agit pas de modifier l'algo en lui meme, mais les paramètres d'entrée, donc normalement, pas de grosse difficulté pour un connaisseur.

Un grand merci d'avance!

[Aguire_]

Post tres interressant !

Je Rejoint toki127 sur les modifications qu'il serait sans doute possible d'ajouter.
Une Explication de base en pseudocode serait sans doute elle aussi interessante !