décomposition d'un entier en somme de cubes avec reste <=7
Bonjour,
Je me demande si quelqu’un peut m'aider à écrire un programme en matlab pour décomposer un entier donné en somme de cubes avec un reste <7, par exemple :
65536 = 40^3 + 11^3 + 5^3 + 4^3 + 2^3 + 2^3 ici le reste est nul. En effet, le calcul est assez simple il suffit de calculer la partie entière de la racine cubique du nombre et faire une soustraction et ainsi de suite jusqu’à aboutir à un nombre <7.
Et merci
Il y a plusieurs façons de faire, mais une façon possible pourrait être :
Soit x
Tant que x > 7, faire :
Calculer la racine cubique de x
En prendre la partie entière, notée y
Afficher (ou enregistrer) y, c'est un élément de la décomposition
faire x = x-y
fin tant que
Après ça n'est pas toujours la méthode la plus économe.
Par exemple :
65536 = 39^3 + 18^3 + 7^3 + 3^3 + 2^3 (+ 7), donc un facteur de moins
65536 = 38^3 + 22^3 + 2^3 + 2^3, deux facteurs de moins
oui Tryss merci, ça pourrais marcher, mais l'algo que t'a posé donne les résultats que j’ai donné pour le nombre 65536 et non comme tu l’a décomposé à la fin, non ?
Exact
C'est un problème de type "problème du sac à dos", enfin une variante. Il existe tout un tas d'algorithmes et de méthodes pour résoudre ce genre de problèmes. Ici l'algorithme assez simple que j'ai décris et que tu as peut être fait dans ta tête sans t'en rendre vraiment compte est appelé "algorithme glouton" : on prend le plus gros morceau qui rentre jusqu’à arriver au bout
