Calcul des termes d'une somme

[Ang3x]

Bonjour,

Pour un projet personnel, je me dois de trouver une solution (si elle est possible) afin de retrouver les termes d'une somme quelconque selon certaines contraintes et/ou hypothèses.

Les contraintes:

- Tous les termes sont strictement différents
(Si le 1 est utilisé, alors tous les autres termes ne peuvent prendre qu'une autre valeur, 2 par exemple).

Les hypothèses:

- Le résultat de la somme est connu.
- Le nombre de termes est connu.
- On connait le dernier ou le premier terme utilisé.

----------------------------

Par exemple, on a:

n = le nombre de termes
S = le résultats de la somme

Pour n = 3 et S = 6, on a : X + Y + Z = 6
Donc, ce que l'on cherche: (X=1, Y=2, Z=3)..

J'ai tenté quelques petites choses mais rien de probant, peut-être existe-t-il un théorème, ou une formule..
Ladite formule recherchée serait proche de la somme des premiers entiers, sauf que certains termes peuvent sauter..
Par exemple, pour S = 7 et n = 3, alors (X=1, Y=2, Z=4 - Le 3 a sauté).

Si quelqu'un à une idée, merci d'avance, je planche toujours dessus!

[Skullkid]

Bonjour, y a un petit souci dans tes contraintes, tu dis que la somme doit faire n termes, tous non nuls, tous differents, et tous entiers compris entre 1 et n. Il n'y a qu'une seule somme satisfaisant ces conditions : la somme des entiers de 1 à n.

Dans ton deuxième exemple S = 7 et n = 3, si on s'en tient à tes contraintes, tu n'as pas le droit d'avoir 4 comme terme de la somme.

[Ang3x]

Bonjour, y a un petit souci dans tes contraintes, tu dis que la somme doit faire n termes, tous non nuls, tous differents, et tous entiers compris entre 1 et n. Il n'y a qu'une seule somme satisfaisant ces conditions : la somme des entiers de 1 à n.

Dans ton deuxième exemple S = 7 et n = 3, si on s'en tient à tes contraintes, tu n'as pas le droit d'avoir 4 comme terme de la somme.

En effet, je n'avais pas réfléchit désolé!
J'ai supprimé la première contrainte..

Pour S = 7 et n = 3, les termes peuvent prendre n'importe quelle valeur du moment qu'ils soient tous différents.. On peut éventuellement connaitre le dernier ou le premier terme. Possible tu penses?

NB: En gros, c'est une somme des premiers entiers où certains peuvent être nuls.

[chan79]

salut
Avec S=16 et n=4 et en commençant par 2, on aurait par exemple au moins ces deux possibilités:
2+3+4+7=16
2+3+5+6=16
C'est ça ?
On remarque déjà que si on augmente S d'une unité et en gardant le même n, il suffit d'augmenter le plus grand nombre de 1 pour obtenir une solution:
2+3+5+6=16
2+3+5+7=17

[Ang3x]

salut
Avec S=16 et n=4 et en commençant par 2, on aurait par exemple au moins ces deux possibilités:
2+3+4+7=16
2+3+5+6=16
C'est ça ?
On remarque déjà que si on augmente S d'une unité et en gardant le même n, il suffit d'augmenter le plus grand nombre de 1 pour obtenir une solution:
2+3+5+6=16
2+3+5+7=17

C'est ça! Néanmoins, le dernier terme est bien précis.

Si S = 1 + 2 + 4 = 7 et n = 3, alors, on doit retrouver chaque entier non nul, soit:
S = (n)*1 + (n+1)*1 + (n+2)*0 + (n+3)*1 = 7
Dans ce cas, il faut trouver les termes (les trois) n, n+2 et n+3 soit 1, 2 et 4...
Disons que l'on connait à la fois le premier et le dernier terme pour plus de précisions et moins de possibilités..

[chan79]

[quote="Ang3x"]C'est ça! Néanmoins, le dernier terme est bien précis.
[\QUOTE]
???
je pense que tu devrais essayer de bien reformuler ton énoncé :hein:

[Ben314]

Les hypothèses:

- Le résultat de la somme est connu.
- Le nombre de termes est connu.
- On connait le dernier ou le premier terme utilisé.

Sauf erreur, sur le plan théorique, la connaissance du premier terme ne sert pas à grand chose si on précise (ce qui est le cas sur tout les exemples que je vois dans ce fil) que les termes sont dans un ordre croissant :
Résoudre X1 + X2 + X3 +...+ Xk = S avec X1=3<X2<X3<...
ça revient à résoudre (X2-3) + (X3-3) + ... + (Xk-3) = S-3(k-1) avec 0<X1-3<X2-3<...

De même, en théorie, chercher les Xi tels que X1 + X2 + ... + Xk = S avec 0<X1<X2<X3<....
Revient à chercher les Yi=Xi-i tels que Y1 + Y2 + ... + Yk = S - k(k+1)/2 avec 0<=Y1<=Y2<=...
Donc rajouter la condition "les Xi sont distincts" ne change pas grand chose au problème (pourvu qu'on précise que les solutions sont à considérer sous la forme des Xi rangés dans l'ordre)

[Ang3x]

C'est ça! Néanmoins, le dernier terme est bien précis.
[\QUOTE]
je pense que tu devrais essayer de bien reformuler ton énoncé :hein:

Ok!

Alors le but: Trouver les termes d'une somme des premiers entiers à n termes pour T termes non nuls.

Hypothèses:
- Les termes sont compris entre 1 et n.
- Les termes sont tous strictement différents.
- Le nombre total de termes est n.
- Le nombre de termes non nuls est T.

Pour S = 7, n = 4 et T = 3, on a:
S = 1(*1) + 2(*1) + 3(*0) + 4(*1)
Il faut donc trouver {1,2,4}

[Ben314]

Vu ton truc, il y aura des solutions ssi la somme minimale 1+2+...+T des T premiers entiers de {1..n} est inférieur ou égal à la somme S désirée et si la somme maximale (n-T+1)+(n-T+2)+...+n des T derniers entiers de {1..n} est supérieure ou égal à la somme S désirée.
Dans ce cas, il y aura en général moulte solutions.
Tu as une préférence pour les solutions ou tu veut juste qu'on t'en donne une la plus simple à trouver ?

[Ang3x]

Vu ton truc, il y aura des solutions ssi la somme minimale 1+2+...+T des T premiers entiers de {1..n} est inférieur ou égal à la somme S désirée et si la somme maximale (n-T+1)+(n-T+2)+...+n des T derniers entiers de {1..n} est supérieure ou égal à la somme S désirée.
Dans ce cas, il y aura en général moulte solutions.
Tu as une préférence pour les solutions ou tu veut juste qu'on t'en donne une la plus simple à trouver ?

En image cela donne:



Nous avons S, Tp, Tn et N.
A partir de ces données, comment retrouver la liste des termes non nuls ?

[Ben314]

Si tu veut TOUTES les solutions, ça risque d'être assez long (pour de grandes valeurs, tu va en avoir des quantités assez faramineuses de solutions...)

Les données que j'ai pour une somme S sont :
- Le nombre total des termes (n).
- Le nombre de termes non nuls (T).
- Le premier et le dernier terme.
- Le résultat de la somme (S).
- (Petit bonus:) Le résultat de la somme des termes nuls S(termes nuls)
(Dans l'exemple précédent: S(termes nuls) = 3 pour S = 7, n = 4 et T = 3).
Soit S(termes nuls) = S - T

Ton truc est de nouveau pas trés clair (et à chaque fois un peu différent... :doh:)
Là, ton "- Le nombre total des termes (n)." ça serait plutôt "tout les termes sont entre 0 et n" par hasard (ce n'est pas du tout la même chose...) ?
Tes termes, ils doivent être calssés du plus petit au plus grand ou pas ?
Ca change tout en ce qui concerne la connaissance du "premier" et du "dernier" : s'il sont classés, ça veut dire que tu connait le plus petit et le plus grand et donc ton truc est redondant avec la première hypothèse, si effectivement elle dit "les termes sont entre 0 et n" ?

Enfin, ça "Le résultat de la somme des termes nuls S(termes nuls)", ça me laisse un peu perplexe : il me semble bien qu'une somme de termes nuls, ça ne peut faire que 0, non ?

[Ang3x]

Si tu veut TOUTES les solutions, ça risque d'être assez long (pour de grandes valeurs, tu va en avoir des quantités assez faramineuses de solutions...)
Ton truc est de nouveau pas trés clair (et à chaque fois un peu différent... :doh:)
Là, ton "- Le nombre total des termes (n)." ça serait plutôt "tout les termes sont entre 0 et n" par hasard (ce n'est pas du tout la même chose...) ?
Tes termes, ils doivent être calssés du plus petit au plus grand ou pas ?
Ca change tout en ce qui concerne la connaissance du "premier" et du "dernier" : s'il sont classés, ça veut dire que tu connait le plus petit et le plus grand et donc ton truc est redondant avec la première hypothèse, si effectivement elle dit "les termes sont entre 0 et n" ?

Enfin, ça "Le résultat de la somme des termes nuls S(termes nuls)", ça me laisse un peu perplexe : il me semble bien qu'une somme de termes nuls, ça ne peut faire que 0, non ?

Désolé de ne pas être assez clair, j'ai modifié mon message précédent avec une image pour être un peu plus compréhensible.. Ce qui donne:



On connait S, Tp, Tn et N.
On cherche à trouver tous les Tp :
- Dans l'exemple ci-dessus: {1,2,3,5,7}

[Ben314]

Sauf erreur, ça revient donc à ça :
On cherche un N-uplet d'entiers naturels non nuls avec , et connus tels que :
a)
b) ( connu)

[Ang3x]

A priori, moi, je veut bien partir là dessus :
On cherche un T-uplet d'entiers naturels non nuls avec , et connus tels que :
a)
b) ( connu)

Ça à l'air d'être ça je crois!
En effet, c'est bien du plus petit au plus grand..

[Ben314]

Ça à l'air d'être ça je crois!
En effet, c'est bien du plus petit au plus grand..

Le problème, c'est que dans ton dernier dessin, tu n'a plus l'air de considérer que tu connais et (Sur ton exemple, et ...)
Ils sont fixés ou pas le premier et le dernier ?

[Ang3x]

Le problème, c'est que dans ton dernier dessin, tu n'a plus l'air de considérer que tu connais et (Sur ton exemple, et ...)
Ils sont fixés ou pas le premier et le dernier ?

Disons que je peux faire en sorte de les connaître.
Si cela peut rendre le calcul plus simple (voir possible déjà), alors considère que oui!

X1 et XT connus.

[Ben314]

Si on ne les connais pas, ça revient à ça :
On connait N, T, S et n cherche un T-uplet d'entiers naturels tels que :
a)
b)

[Ben314]

Disons que je peux faire en sorte de les connaître.
Si cela peut rendre le calcul plus simple (voir possible déjà), alors considère que oui!
X1 et XT connus.

Au niveau du calcul, ça va pas chager grand chose, vu que, si on connait et , ça veut dire qu'on cherche uniquement ,..., avec des contraintes légèrement différentes.
Donc c'est pas à moi de te dire si on les connait ou pas...

[Ang3x]

Si on ne les connais pas, ça revient à ça :
On connait N, T, S et n cherche un T-uplet d'entiers naturels tels que :
a)
b)

As-tu une idée de formule magique?
(donc sans les connaître)

[Skullkid]

Je ne pense pas qu'il y ait de formule magique (comme l'a dit Ben314 il risque d'y avoir un grand nombre de solutions), mais si j'ai bien compris tu cherches à écrire un programme récursif qui te sort la liste des solutions, ça ne devrait pas être trop difficile.

À froid, je verrais bien un truc qui prendrait, en plus des arguments de base x1, xT, T et S, trois arguments auxiliaires : les premiers termes de la somme ('debut'), les derniers termes de la somme ('fin') et un accumulateur qui a vocation à contenir la liste complète des solutions à la sortie du programme ('acc'). Ça aurait pour conséquence qu'un appel à fonction(x1,xT,T,S,debut,fin,acc) soit sous-traité en beaucoup (!) d'appels à fonction(x1+i , xT-j , T-2 , S-x1-xT , [debut,x1] , [xT,fin] , acc), dans lesquels on remplit acc dans les cas où la solution (ou l'absence de solution) est immédiate (par exemple quand T = 2). Après yapluka s'assurer que la descente récursive se termine toujours...

Ce n'est sans doute pas très efficace comme algorithme vu le risque d'explosion du nombre d'appels (en même temps le nombre de solutions risque d'exploser aussi...), mais ça devrait donner une base.