Résoudre «l'échange de pièces» pour les pièces de puissance des valeurs par algorithme gourmand

Question

Lorsque Résoudre le problème de l'échange de pièces par algorithme gourmand, pourquoi aurons-nous toujours le bon résultat si les valeurs de la pièce sont 1 $, a, a ^ 2, cdots, a ^ n $, où $ a ge 2 $ et $ n gt 0 $?

Par exemple, si $ a = 3 $, $ n = 3 $, nous obtenons les valeurs de pièce suivantes: 1, 3, 9, 27. Lorsque l'échange total est de 16, la réponse est de 4 pièces, comme retourné par l'algorithme gourmand, $16=9+3+3+1$.