Obtenir une somme fixée
Bonjour,
je suis en difficulté pour écrire un algorithme qui résolve le problème suivant :
J'ai une liste de dix entiers naturels $A = [a_0, ..., a_9]$ et une somme décimale $S$.
Je voudrais énumérer toutes les manières d'obtenir l'égalité :
$$\sum_{k=0}^9 n_k 10^{-p_k} a_k = S$$
où :
- les $p_k$ appartiennent à $\{0,1,2,..., P\}$ (en première approximation $P=4$),
- les $n_k$ sont des entiers naturels dont la somme est raisonnable (disons $\sum_k n_k\leq N$, avec $N$ qui vaut par exemple 5, 6 ou 7, je pense que ça devrait suffire).
Est-ce que ça peut s'écrire en général ?
Par exemple une fonction Python sommeFixe(A,S, P, N)
qui me renvoie la liste des [p_k, n_k] satisfaisants.
A défaut est-ce que ça peut s'écrire pour des cas particuliers (N=7, P=4 par exemple)....?
Je séche pour l'écriture, même pour le cas particulier...
Merci pour toute aide !
PS :
Je sais juste qu'on peut éviter les flottants, travailler partout avec des entiers pour éviter des problèmes !
On multilplie tout par $10^P$, et plus de problème d'arrondi.
je suis en difficulté pour écrire un algorithme qui résolve le problème suivant :
J'ai une liste de dix entiers naturels $A = [a_0, ..., a_9]$ et une somme décimale $S$.
Je voudrais énumérer toutes les manières d'obtenir l'égalité :
$$\sum_{k=0}^9 n_k 10^{-p_k} a_k = S$$
où :
- les $p_k$ appartiennent à $\{0,1,2,..., P\}$ (en première approximation $P=4$),
- les $n_k$ sont des entiers naturels dont la somme est raisonnable (disons $\sum_k n_k\leq N$, avec $N$ qui vaut par exemple 5, 6 ou 7, je pense que ça devrait suffire).
Est-ce que ça peut s'écrire en général ?
Par exemple une fonction Python sommeFixe(A,S, P, N)
qui me renvoie la liste des [p_k, n_k] satisfaisants.
A défaut est-ce que ça peut s'écrire pour des cas particuliers (N=7, P=4 par exemple)....?
Je séche pour l'écriture, même pour le cas particulier...
Merci pour toute aide !
PS :
Je sais juste qu'on peut éviter les flottants, travailler partout avec des entiers pour éviter des problèmes !
On multilplie tout par $10^P$, et plus de problème d'arrondi.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je viens de m'apercevoir que mon énoncé est incomplet ! (td)
En effet les $a_k$ peuvent apparaître plusieurs fois, avec des coefficients $10^{-p_k}$ distincts !
-- Schnoebelen, Philippe
D'abord, évaluons le nombre de cas.
En attendant, on a, ici, $\Gamma_N^{10}=C_{N+9}^{10}$ répartitions. Par exemple, pour N=5, il y a $\Gamma_5^{10} = C_{14}^{10} = C_{14}^{4} = \frac{14*13*12*11}{4*3*2}=1001$ répartitions. Quantité abordable.
En attendant, on a, ici, $(P+1)^{10}$ équipes de valeurs. Par exemple, P=4, on a 5^10=9765625 cas possibles. Ça commence à chauffer.
En conclusion, on a $C_{N+9}^{10}(P+1)^{10}$ sommes possibles. Il suffit de les énumérer comme on les a dénombrées.
Dans l'exemple, 9775390625 itérations. Presque dix milliards de tours de boucle quand même.
Euh, non, faudrait construire ça !
Mon approche est algorithmique (et théorique). Y a-t-il un truc vraiment simplificateur que je rate ?
@PetitLutin
et par conséquent, ton approche de la complexité est très intéressante pour moi !
Ton premier point, avec le coef binomial, m'avait échappé ! Pourtant je connaissais ce dénombrement (avec 10 sortes de crottes en chocolats, combien de ballotins possibles, le ballotin contenant N crottes, c'est bien ça ?)
Tu proposes l'algoritme exhaustif, je vais essayer de l'écrire,
même s'il ne peut pas tourner sur de grosses valeurs...
Je voit mieux à quoi il pourrait ressembler... je crois.
Merci à tous les deux !
Non, je cherchais la grosse astuce qui .... lol !
Ps :
D'ailleurs, et compte tenu de ma remarque (mon second message)
je poserais la question différemment maintenant, en indexant sur N et non plus sur 10...
Je ne sais pas si je suis clair, là...
Si tu dois reconstiter le nombre 1,2345 à partir d'entiers, avec $p_k$ limité à 4 , il n'y a pas des tonnes de façons d'obtenir le 5 final ; Pour chacune de ces solutions, on va ensuite chercher à obtenir le 4 en avant dernière position etc
Donc même si l'arbre qu'il faut parcourir est énorme, dans les faits, il y a des tas de branches qui s'avèrent tout de suite inutiles.
Donc algorithmiquement parlant, ça ressemble plutôt à de la récursivité ?
J'ai un peu réfléchi à ça, mais je dois être rouillé sur le sujet (ou je ne l'ai jamais vraiment compris)...
Ensuite, clairement, la récursivité convient bien, et puisque on somme uniquement des entiers positifs, il y a moyen d'élaguer pas mal de branches.
On doit pouvoir aussi procéder par programmation dynamique, ou simplement par mémoïsation.
Euh c'est plutôt 10 boîtes et 5 crottes. 3 exemples de répartitions possibles :
(0 0 0 0 1 0 0 0 2 2)
(0 1 0 1 0 1 0 1 0 1)
(5 0 0 0 0 0 0 0 0 0)
À la relecture, je m'aperçois que ce n'est pas $\Gamma_{N}^{10}$, mais $\displaystyle \sum_{i=0}^{N} \Gamma_{i}^{10}$.
@Bisam
En commençant avec les grandes puissances :
Si la somme est trop grande, on élague. Ok
En partant avec les petites puissances :
Si la dernière décimale n'est pas la bonne, on élague. Ok.
Je suis incapable d'imaginer l'écriture récursive. Une bonne occasion de réviser le concept ?
Quant à la mémoïsation, première fois que je vois ce mot !
(quand j'ai le temps, je vais regarder sur le net, promis !)
@PetitLutin
J'ai dû mal m'exprimer.
Chez un artisan chocolatier, on va s'acheter un joli petit balotin de N crottes.
Il propose 10 sortes de chocolat.
On choisit librement (en dénombrement, répétitions possibles, ordre sans importance) la composition du balotin.
$\binom{9+N}{N}$ possibilités.
Exemple :
CCC I I I I CC | C | | | C I
modélise le choix de 7 chocolats parmi 10 sortes (numérotées ici de 1 à 10) :
3 de la sorte 1
2 de la sorte 5
1 de la sorte 6
1 de la sorte 9
Par exemple, renvoie
Je vais examiner ça dans le détail.
C'est tellement court que c'est inquiétant, :)olol !
Je manque un peu d'énergie et de temps maintenant,
mais je reviens sous quelques jours !
Bien sûr, j'ai modifié un peu la requête initiale en remplaçant la somme S à chercher par S * 10**P.
J'explique un tout petit peu mon algorithme :
Il y avait quelques petites erreurs à la fin que j'ai corrigées ci-dessus :
Cela devrait être mieux maintenant.
Pour y remédier, le moyen le plus simple est de changer la nature de la réponse en une liste de couples de tuples...
Voici donc la deuxième version :
Ainsi, cette fois-ci : renvoie
On voit en particulier que le tuple (1,1,1,1) de n_i est associé à deux couples de p_i : (0,1,2,3) et (0,3,2,1), ce qui est logique puisque les a_i correspondants sont égaux.
La première méthode a l'avantage d'éviter les multiplicités en les écrasant au fur et à mesure, mais elle peut rater des cas.
Avec une liste $a_i$ qui serait [3,1,4], est-ce que la solution 3+1/10+4/100+ 1/1000 est acceptée ou pas ?
Dans la 1ère formulation de l'exercice, on a envie de conclure que non. Chaque $a_i$ doit être utilisé une seule fois, avec un certain coefficient, et une puissance de 10.
Dans la 2ème piste (le PS de ce message), on a l'impression que finalement, on peut utiliser chaque nombre plusieurs fois , en respectant bien sur la contrainte sur N.
C'est un peu pour ça que je demandais des exemples.
Avec le jeu de données [3,1,4] , p=3, N=8, et S=3.141, est que que la solution 3+1/10+4/100+ 1/1000 est acceptée ou pas ?
2) somme_fixe2([111, 3], 111*101 + 3*10, 3, 4)
Bonjour et merci à tous les deux.
Et désolé pour la cafouillage initial, ma formulation en deux étapes jette le trouble.
la version rectifiée dans mon second post étant celle qui m'intéresse le plus.
Avec 1), je m'attends à obtenir des solutions avec ma première question.
Avec 2), je m'attends à obtenir des solutions avec ma seconde question.
(j'espère ne pas me tromper dans ces exemples).
Plus de détails sur ces deux exemples si besoin, mais je pense que vous avez bien compris ma recherche.
Désolé aussi, je manque d'énergie pour aller plus loin ce soir,
mais je me demande si ton algo, Bisam, ne part du principe que les éléments de la liste A sont < 10. Ce qui n'est pas comme le montre les exemples.
J'ai essayé de modifier le booléen S >= 10**(P+1) en S >= 10**(P+1) * max(A+[0]) * N, sans effet bénéfique.
J'y pense en écrivant : sans doute parce que dans un algo récursif, les valeurs de A, N P changent...
Il suffit d'enlever la condition pour obtenir ce que tu veux pour le premier cas.
En revanche, pour le second cas, il faut revoir entièrement l'algorithme. En effet, celui-ci prévoit que le nombre d'éléments de la liste A est fixé et la récursion le fait strictement diminuer.
Si on peut changer le nombre d'éléments de la liste, l'algorithme est caduc.
On peut peut-être y arriver quand même, mais cela devient plutôt un problème d'arithmétique.
Exemple : atteindre 22258 avec [111; 3; 14] demande l'étude de 3 sous-cas : 11158, 19258, et 8258. Et on recommence. Etc.
Notez que baisser de 14 descend plus vite que baisser de 111. :-)
(en particulier la manière dont on gère la récursivité, ce qui me posait le plus problème),
je crois que je vais essayer d'être autonome.
Effectivement, je vais réécrire les choses en essayant, comme le suggère PetitLutin,
non pas de diminuer la liste A, mais en diminuant N à chaque étape.
Ce que j'ignore complètement, c'est la capacité en termes de nombre de "branches de récursivité" de Python (ou d'un autre logiciel),
mais je testerai en diminuant longueur de liste et N.
Si déjà ça peut marcher comme ça, je serai assez content !!
Je vous envoie des nouvelles quand je me suis penché là-dessus.
Encore merci !
Je viens de faire le test avec un script tout bête et j'ai obtenu 989.
Tu lances le test avec "recur(0)" et le nombre renvoyé est la profondeur de récursion.
Puisque tu voulais te limiter à de petites valeurs de N, et si ton algorithme diminue strictement N à chaque étape, tu n'auras aucun problème... mais si je ne m'abuse, N ne diminue pas strictement...
N'as-tu pas plutôt obtenu $1000 - 2 = 998$, par hasard ? Because: et ce lien vers SO.
J'ai réussi à m'en sortir tout de même :
Cette fois, on renvoie directement un ensemble de solutions (pour éviter de répéter plusieurs fois la même), chacune des solutions étant sous la forme d'un tuple de couples. J'aurais préféré renvoyer un ensemble de dictionnaires, mais les dictionnaires ne sont pas hashables.
Ainsi, les trois essais renvoient respectivement les 3 résultats .
On doit pouvoir faire encore plus efficace avec des résolutions d'équations diophantiennes... mais je n'ai pas encore cherché dans cette voie, car si elle est sûrement plus efficace sur de grandes valeurs de N, elle est bien plus pénible à écrire !
J'ai essayé, une dizaine de jours après lecture du code proposé par Bisam,
de réécrire un code pour vérifier si j'avais compris.
Je signale que j'essaie de n'utiliser que des outils plus rudimentaire que Bisam (dans son code, les "set", les "tuple" m'échappent).
Donc je veux construire une liste affichée en cas de succès,
par exemple pour mon exemple ci-dessous, à savoir : sommeCoef([3, 111, 15], 4, 2, 11100+165)
j'attends quelque chose comme [ [2, 110], [1, 15], [0, 15] ] car 11100+165 = 111 * 10^2 + 15 * 10 + 15
Donc voilà ma tentative. Elle me semble "raisonnablement correcte" (j'espère),
mais ... je sais bien que ma liste n'est initialisée nulle part !
Donc ceci est un nouvel appel à l'aide :
- est-ce que je peux m'en sortir avec quelque chose comme ça ?
- si oui, où initialiser la liste ? Merci pour tout coup de main !
On ajoute un argument "liste" à la fonction qui sera modifié par effet de bord à l'exécution de la fonction.
Pour ne pas avoir besoin de le spécifier dans l'appel au départ., on donne une valeur par défaut à "liste"... mais une subtilité veut qu'on ne peut pas l'initialiser avec une liste vide car ce serait la même liste utilisée à tous les appels de la fonction puisque l'instanciation de la valeur par défaut se fait au moment de la création de la fonction et non à son exécution. L'astuce consiste à donner une valeur fixe (et impossible à obtenir autrement) par défaut et à tester à l'exécution si la valeur de la liste est cette valeur par défaut. Cela donne les deux premières lignes.
Ensuite, tu avait une erreur en renvoyant "test" à la fin de ta boucle : je l'ai supprimé. Une autre erreur était que tu mettais "A" au lieu de "elem" dans tes listes.
Pour finir, il suffit de faire l'appel récursif en adjoignant à la liste le couple [k, elem].
Le problème de cette méthode c'est que tu fais afficher les différentes solutions mais tu ne peux pas les réutiliser dans une autre fonction car elles ne sont pas renvoyées.
J'ai compris les boulettes,
le return, le A à remplacer par elem.
Et je suis heureux de connaître l'astuce ! Je voyais le problème d'initialisation, mais je ne savais pas le résoudre.
C'est j'imagine une astuce "classique" pour les algorithmes récursifs.
Pour le print, j'ai bien conscience du problème que tu soulèves.
Bon, je verrai si je trouve un moyen d'y remédier...
Pour en savoir plus, évidemment, suivre un cours basique de Python devrait aider...