Décomposer un entier en somme

[nodgim]

Curieux, Doraki cette façon de travailler en modulo 20.
@anthony: je ne vois pas la recherche de l'optimisation aussi difficile que toi. Pour un nombre à 10 ou même 20 chiffres, ça me semble même assez rapide d'arriver au résultat optimal à la main. En revanche, la programmation me parait assez compliquée.

[anthony_unac]

Calculs des intérêts : METHODE DES PARTIES ALIQUOTES DU TEMPS

Décomposons 83 j en parties aliquotes de 90 j, à chaque fraction de 90 j correspond,
en intérêts, la même fraction de 108,45

Nombre xxxxx Fraction xxxxx intérêts xxxxx Montant
de jours xxxxx xxxxx xxxxx calculs xxxxx intérets

45 xxxxx 1/2 xxxxx 108,45*1/2 = xxxxx 54,225
30 xxxxx 1/3 xxxxx 108,45 *1/3 = xxxxx 36,150
5 xxxxx 1/6 de 1/3 xxxxx 36,15*1/6 = xxxxx 6,025
3 xxxxx 1/10 de 1/3 xxxxx 36,15*1/10 = xxxxx 3,615
83 xxxxx xxxxx xxxxx xxxxx xxxxx 100,015

D'accord, c'était bien calculatoire comme exercice. On voit nettement qu'il faut maîtriser la division par 2 et par 3 de tête (du tac au tac) pour aboutir rapidement au résultat.

[anthony_unac]

@anthony: je ne vois pas la recherche de l'optimisation aussi difficile que toi. Pour un nombre à 10 ou même 20 chiffres, ça me semble même assez rapide d'arriver au résultat optimal à la main. En revanche, la programmation me parait assez compliquée.

Ok voici un entier construit en piochant dans les décimales de pi (par exemple) :

9937510582097494459

Je ne pense pas que sa décomposition soit si aisée que ça. Bien malin celui qui en deux minutes prétend avoir trouvé sa décomposition optimale.
Le problème ne réside pas seulement dans la prise en compte des digits une par une, mais également des digits qui suivent ou qui précèdent d'ou la complexité à mon sens.

[anthony_unac]

D'après mon programme il y aurait une stratégie optimale super simple, qui décide de quelles unités (1,2,4,8) on prend en regardant n mod 20
)

Je reste surpris par ce mod 20.
Concrètement que faites vous pour décomposer mettons 14159 ?

[Ben314]

Je reste surpris par ce mod 20.
Concrètement que faites vous pour décomposer mettons 14159 ?

Ben... tu applique bêtement ce que dit Doraki... :
14159 = 9 mod 10 donc [-1] et il reste 14160
1416 = 6 mod 10 donc [-4] et il reste 1420
142 = 2 mod 10 donc [+2] et il reste 140
14 = 4 mod 10 donc [+4] et il reste 10

Bilan : 14159 = 10000 + 4000 + 200 - 40 - 1

Et le modulo 20, il me semble évident : dans certains cas, tu peut atteindre soit le multiple de 10 suivant, soit le précédent avec le même nombre de "coups" et dans ce cas, il faut (au minimum) regarder lequel des deux est multiple de 20 pour conclure.
A mon avis, la logique, c'est clairement de regarder lequel des deux permet le plus rapidement d'obtenir un multiple de 100 et s'il y a de nouveau plusieurs possibilités de même "cout" de regarder pour les multiple de 1000, etc
Et ce "etc", c'est ce qu'a déjà écrit Doraki : "il n'y a pas de limite sur le nombre de chiffres à regarder pour obtenir les différents choix d'unités possibles"

[anthony_unac]

14159 = 9 mod 10 donc [-1] et il reste 14160
1416 = 6 mod 10 donc [-4] et il reste 1420
142 = 2 mod 10 donc [+2] et il reste 140
14 = 4 mod 10 donc [+4] et il reste 10

Bilan : 14159 = 10000 + 4000 + 200 - 40 - 1

La c'est clair, en revanche je ne vois pas ou est le modulo 20 dans tout ceci ?!

[anthony_unac]

Je crois avoir trouvé un exemple qui cause du tort à la méthode de Doraki (qui semblait pourtant efficace sur bon nombres d'exemples) :
67=1(-3)(-3)=100-20-10-2-1 (soit 5 termes avec la dite méthode)
et au feeling on peut décomposer comme suit :
67 = 40+20-8+1 (soit 4 termes) J'ignore si c'est la décomposition optimale pour autant

[Doraki]

Non, 67 est à égale distance de 70 et de 60 (dans les deux cas il faut 2 morceaux pour y aller), donc on choisit de décomposer 67 en 60+7 plutôt qu'en 70-3 parceque 60 est multiple de 20 et pas 70.

Ou si on regarde la table, 67 est congru à 7 mod 20 donc on choisit la décomposition en 7+...

[anthony_unac]

Ok je commence à comprendre ce fameux modulo 20.
Reprenons un exemple : 57 = 17 [20] = -3 [20] donc on décomposera sous la forme 57=-3+60=40+20-2-1 (soit 4 termes au total)

[nodgim]

9937510582097494459
...62489417902505541
...42489417902505541
....2489417902505541
.....489417902505541
......89417902505541
.......9417902505541
........582097494459
........182097494459
.........82097494459
..........2097494459
............97494459
.............2505541
..............505541
..............105541
................5541
................1541
.................459
..................59
..................19
...................1

21 coups pour ce 19 chiffres. Sans trop réfléchir.

[anthony_unac]

humm c'est plus compliqué que ça car tous vos 9,5,7,6 et 3 finaux se redécomposent en deux termes soit près d'une trentaine de termes in fine pour la décomposition de cet entier à 19 chiffres.

[chan79]

9937510582097494459
...62489417902505541
...42489417902505541
....2489417902505541
.....489417902505541
......89417902505541
.......9417902505541
........582097404459
........482097404459
.........82097404459
..........2097404459
............97404459
.............2505541

salut
ça doit être 2595541 à la dernière ligne

[nodgim]

Merci Chan79 pour ta remarque, ça fait gagner 1 coup, j'ai corrigé msg 1013.

@Anthony: regarde bien, nb de lignes = nb de termes

[anthony_unac]

Non car à la fin, la décomposition doit être composée uniquement de termes de la forme ϵ×k×10^j où ϵ∈{−1,1}, k∈{1,2,4,8} et j∈N donc exit le 3,5,6,7 et autres 9.

[nodgim]

En relecture, j'ai trouvé une autre erreur, donc 21.

@anthony: donne moi un exemple où ça coince selon toi, stp.

[anthony_unac]

@anthony: donne moi un exemple où ça coince selon toi, stp.

Exemple : 718
-----------------
718 = 800-100+10+8 (soit 4 termes) mais il est possible de faire mieux :
718 = 8(-8)(-2) = 800-80-2 (soit 3 termes) et certainement la décomposition (une des décompositions) optimale.

Vous remarquerez qu'il n'y a ni 3,5,6,7 ou 9 dans mes termes.
En espérant avoir été suffisamment clair avec cet exemple tout bête.

[nodgim]

Il faudrait que tu me donnes un endroit dans la liste que j'ai fournie où ça te semble incorrect.

[anthony_unac]

Il faudrait que tu me donnes un endroit dans la liste que j'ai fournie où ça te semble incorrect.

Partout en fait, à toutes les lignes vous utilisez soit du 3,5,6,7 ou 9 ou un mélange de ces chiffres qui sont "interdits" car la décomposition doit être uniquement composée de termes de la forme ϵ×k×10j où ϵ∈{−1,1}, k∈{1,2,4,8} et j∈N.

[anthony_unac]

Une décomposition possible pourrait être (par exemple) :
9937510582097494459 =
1*10^19-4*10^16-2*10^16-2*10^15-4*10^14-8*10^13-8*10^12-1*10^12-4*10^11-1*10^10-8*10^9+1*10^9-8*10^8-1*10^8-2*10^6-4*10^5-1*10^5-4*10^3-1*10^3-4*10^2-1*10^2-4*10^1-1*10^0
(soit 23 termes pour cette décomposition)

[nodgim]

Si c'est partout, alors c'est aussi la seconde ligne:
9937510582097494459
...62489417902505541

signifie que je suis passé de la 1ère à la 2ème ligne en faisant: 10^19-
9937510582097494459 = 62489417902505541