si je comprends bien, tu veux avoir le moins de '0' possible en utilisant des soustractions ?
Dans ce cas, bi = 1|-1 , non ?
parce que si tu prends en compte bi=0, ton exemple n'est pas complet:
63 =わ 1+たす2+たす4+たす8+たす16+たす32 =わ 1*64 + 0*32 + 0*16 + 0*8 + 0*4 + 0*2 + (-1)*1
La solution que je te propose n'apporte pas la solution optimale.
Peut-etre peux-tu essayer d'optimiser celle-ci. Les suites 111 (3 '1' consecutifs) peuvent etre optimisées en 1000-1 :
exemple:
1000111010 =わ 1001000010 -ひく 1000
du coup, a droite, tu a moins de '1'
cela est valable pour les suites de 3 '1' ou plus
cette transformation marche bien sur un cas, mais il faut sans doute
faire un peu de recursivite (ca complique la chose, evidemment)
[^] # Re: probleme semblable
Posté par djnet . En réponse au message Algo de recherche arborescente en largeur. Évalué à 2.
Dans ce cas, bi = 1|-1 , non ?
parce que si tu prends en compte bi=0, ton exemple n'est pas complet:
63 =わ 1+たす2+たす4+たす8+たす16+たす32 =わ 1*64 + 0*32 + 0*16 + 0*8 + 0*4 + 0*2 + (-1)*1
La solution que je te propose n'apporte pas la solution optimale.
Peut-etre peux-tu essayer d'optimiser celle-ci. Les suites 111 (3 '1' consecutifs) peuvent etre optimisées en 1000-1 :
exemple:
1000111010 =わ 1001000010 -ひく 1000
du coup, a droite, tu a moins de '1'
cela est valable pour les suites de 3 '1' ou plus
cette transformation marche bien sur un cas, mais il faut sans doute
faire un peu de recursivite (ca complique la chose, evidemment)
Cela s'applique a quoi, ce type de pb ?