Ben314 a écrit:Pour moi, ton truc ne prouve absolument rien concernant ton algorithme : ce n'est pas parce qu'il est "optimal" sur les nombre à k chiffres que ça prouve qu'il vaut mieux descendre le nombre de chiffres le plus rapidement possible.
La "clef de voute" de ton algo., c'est que, lorsque tu as le choix entre entre dire que N=p*10^n+r ou bien N=p'*10^n- r', tu dit qu'il faut choisir selon que r<r' ou pas pour l'ordre usuel sur les entiers naturels. Alors que la seule chose triviale, c'est qu'il faut choisir selon que r<r' ou pas pour le "presque ordre" induit par le nombre de coups pour arriver à zéro.
Qu'est ce qui te permet d'affirmer que c'est la même chose, c'est à dire qu'il est impossible de tomber sur un truc du style r=3 r'=4 où 3<4 pour l'ordre usuel mais 3>4 pour celui du "nombre de coups" ?
(et je redit que je pense que c'est vrai, mais... c'est pas du tout trivial...)
EDIT : en fait tu as r+r'=(p+p')10^n donc ce qu'il faut montrer, c'est que dans ce cas, r et r' sont dans le même ordre pour l'ordre usuel sur N que pour l'ordre "du nombre de coup"
L'idée de la preuve, c'est qu'on ne peut pas faire mieux que si on avait les 10 chiffres disponibles.
Si on avait les 10 chiffres disponibles, à chaque étape on réduit le nombre de chiffre et on aurait
autant d'étapes que de chiffres non nuls. Donc une chose est sûr, on ne peut pas faire mieux que ça.
Donc si on se restreint seulement aux chiffres 1,2,4,8 : il y a des cas où il faudra plusieurs étapes pour réduire le nombres de chiffres, et on est optimal si ce "plusieurs" est égal à 2.
Pour faire simple, si on a un nombre avec n chiffres non nuls, alors on ne peut faire mieux que n étapes.
chaque étape supprimera aux mieux un chiffre, et au pire il faudra 2 étape pour réduire d'un chiffre :
Il est impossible de faire mieux. (on ne pourra jamais réduire de deux chiffres ou plus en même temps).
Le seule cas où on peut réduire de plusieurs chiffres en même temps c'est si certain chiffres sont nuls.
Mais ça ne change en rien au raisonnement.
Où autrement dit on aura une sorte décomposition en base 10 sauf que pour certaines puissances de 10,
au lieu d'avoir qu'un terme, on aura 2 termes (à cause de la restriction des chiffres).
On veut donc minimiser les puissances de 10 pour lesquels il faut deux termes, donc pour ça si on peux
supprimer un chiffre en une étapes eh bien on le fait.
Comment peut-on faire mieux ?
Autre manière d'expliquer : le but est de supprimer le plus rapidement possible le chiffre de plus haut rang.
ça ne sert à rien de laisser traîner cette étape car comme on multiplie par la puissance de 10 adéquate, les
chiffres du reste sont "inchangés" (ou alors "compléter à 10" mais ce n'est qu'une question de signe, ça n'influe pas sur le nombre d'étapes), et donc ne changera en rien le nombre d'étape
ensuite.
Je ne vois pas trop comment expliquer autrement...
