Discussion :

[GoustiFruit]

Bonjour,

J'ai un petit problème à vous soumettre...

J'ai écrit une petit boucle qui me liste toutes les combinaisons de 3 valeurs (entiers positifs) telles que la somme de ces 3 valeurs est toujours égale à une autre valeur donnée:

Soit i1 + i2 + i3 = iMax dans tous les cas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
procedure ListerCombinaisons;
var
  s: string;
  i1, i2, i3, iMax: integer;
begin
  iMax := 4; // Par exemple
 
  for i1 := 0 to iMax do begin
    for i2 := 0 to (iMax - i1) do begin
      i3 := iMax - i1 - i2;
      s := Format('%2d-%2d-%2d', [i1, i2, i3]);
      slCombinaisons.Add(s);
    end;
  end;
end;

(slCombinaisons est un TStringList global)
Cet exemple va me donner la liste suivante:

i1 | i2 | i3 | (Index)
0 0 4 | 0
0 1 3 | 1
0 2 2 | 2
0 3 1 | 3
0 4 0 | 4
1 0 3 | 5
1 1 2 | 6
1 2 1 | 7
1 3 0 | 8
2 0 2 | 9
2 1 1 | 10
2 2 0 | 11
3 0 1 | 12
3 1 0 | 13
4 0 0 | 14

La suite est logique, l'ordre est toujours le même.

Maintenant je voudrais, *par le calcul* (et pas en consultant la liste !):
1- déterminer le nombre total de combinaisons (en fonction de iMax). Dans cet exemple, le résultat est 15.
2- connaissant i1, i2, i3 (et iMax), déterminer la position de leur combinaison dans la liste (Index). Par ex. avec les valeurs 1 1 2 le résultat doit être 6.
3- connaissant la position dans la liste (Index) et iMax, calculer i1, i2, i3. Par ex. avec un Index de 9 le calcul doit me donner i1=2, i2=0 et i3=2.
Encore une fois, ceci sans boucler sur la liste elle-même, mais seulement à partir des valeurs connues.

Mais je n'y arrive pas, ça fait des heures que je me prends la tête dessus ! Donc si quelqu'un y voit plus clair que moi...

PS: si une façon de lister différente permet de faciliter les calculs, ça ne me dérange pas de modifier ma façon de faire.

[mick605]

Hahaha, enfin un probleme de maths, j'adore ca ! ^^

Bon, Question 1 :

Pour 4 on a 15
Pour 2 on a :
002
011
020
101
110
200
Donc pour 2 on a 6
Pour 3 on a :
003
012
021
030
102
111
120
201
210
300
Donc pour 3 on a 10

On remarque (avec un peu d'entrainement) que pour n on a 1+2+3+...+(n-1)+n+(n+1) (Somme des entiers de 1 a n+1), soit NbreLignes=((n+1)*(n+2))/2

Deuxieme question (niveau 2 ) :

Alors, la c'est plus dur :
Voila comment j'ai procédé : J'ai cherché une fonction qui a i1 (pour n=4) associe successivement les valeurs 0-5-9-12-14 (valeurs pour i1 donné et i2=0)
J'ai ainsi trouvé : S = NbreLignes (correspond a la question 1) - (1+2+...+(n+1-i1)) (Somme des entiers de 1 a (N+1-i1))

En arrangeant un peu, et grace a la formule :
1+2+3+4+........+(x-1)+x = (x*(x+1))/2, on trouve finalement :

S = 1/2* i1 * (2n+3-i1)

Ensuite, pour trouver l'index, on a :
Index = S+i2 (indépendant de i3 )

La je suis chaud, 3eme question :

A ouais, elle est dure aussi.

Tu calcules D=NbreLignes-Index
Ensuite, tu dois trouver un x (entier, compris entre 0 et n) le plus grand possible tel que
1+2+...+x < D (Strictement inferieur)
ou
x*(x+1)/2 < D

Tu auras ainsi i1 = n-D
Pour i2, tu te sert simplement de la formule de la deuxieme question, et pour i3, facile

Voila !
J'attends d'autres questions, j'adore ce genre de probleme.

Pour info, je suis parti la plupart du temps de la constatation que pour n=4, les i1 sont :
0
0
0
0
0
1
1
1
1
2
2
2
3
3
4

soit 5 (0) + 4 (1) + 3 (2) + 2 (3) + 1 (4) et le reste est venu avec des tests !
On remarque ainsi que nbre de lignes = 5 + 4 + 3 + 2 + 1 !



Si tu as la moindre question, ou si tu veux plus d'explications sur ma maniere de proceder, fais le moi savoir !

Bonne chance pour la suite !

[GoustiFruit]

C'est vrai que la nuit porte conseil: je me couche avec un problème insoluble en tête, et au petit matin, paf , la solution !

Merci beaucoup, beaucoup, beaucoup ! (en plus tu as posté à 1h51, faire des maths à cette heure là, faut en vouloir ! Dis-moi que tu habites aux antipodes, ça me rassurerait...)

Bon maintenant je vais mettre tout ça en pratique... j'ai compris ton raisonnement pour la 1, j'ai encore un peu de mal avec la 2 mais en y regardant de plus près et en programmant ça devrait venir... pour la 3, je ne comprends pas comment tu poses d'entrée de jeu "D=NbreLignes-Index" ni le raisonnement qui s'en suit, je veux bien un peu d'explications supplémentaires si tu as le temps (et si c'est pas trop compliqué ;-) ). Mais bon, le principal c'est que je puisse avancer maintenant que j'ai les réponses...

Encore merci.

[mick605]

Merci beaucoup, beaucoup, beaucoup ! (en plus tu as posté à 1h51, faire des maths à cette heure là, faut en vouloir ! Dis-moi que tu habites aux antipodes, ça me rassurerait...)

Ben ca dépends si tu pense que toulouse c'est aux antipodes


Pour la deuxieme question,

J'ai cherché une fonction qui a i1 (pour n=4) associe successivement les valeurs 0-5-9-12-14

On remarque que si on fait 15 (NbreLignes) - ces valeurs, on trouve 15-10-6-3-1 , qui est la suite 1 - 1+2 - 1+2+3 - 1+2+3+4 - 1+2+3+4+5.
Donc, par exemple, pour le 10, on devrait trouver i1 = 1 et on trouve un x egal a 4, soit 5-1 (il faut souvent se referer a n+1 dans ton probleme) ... On voit que la deuxieme suite est la somme de 1 à x pour x variant de 1 à 5. En arrangeant un peu, on remarque que ce x est facilement lié a i1. on trouve enfin que x = n+1-i1. Ensuite, c'est des maths ...

POur la troisieme question, je me doutais qu'il fallait travailler avec 15 - Index, pour les memes raisons que dans la question 2. Ensuite, je savais que cela ne serait pas une égalité, car pour des différentes valeurs de Index, on peut avoir des valeurs de i1 identiques.

Ensuite, on doit associer :
D -> i1
15 - 0
14 - 0
13 - 0
12 - 0
11 - 0
10 - 1
9 - 1
8 - 1
7 - 1
6 - 2
5 - 2
4 - 2
3 - 3
2 - 3
1 - 4

On remarque que les valeurs de i1 changent quand D passe "le cap" 1 - 3 - 6 - 10 - 15 .......... Toujours cette suite !
Ensuite, avec des petits tests, j'ai reussi a voir le lien avec i1 ...
Mais sur la derniere, je fais avec une technique que j'arrive pas a expliquer, au feeling ! Je n'ai aucun raisonnement mathématique ! Si j'ai une idée de comment t'expliquer, je reviendrai !

En attendant, bonne continuation !

PS : C'est pour quoi faire ce probleme ? C'est un exo de maths ?

[GoustiFruit]

Bah oui Toulouse c'est l'autre bout du monde pour moi :-)

Et non il ne s'agit pas d'un devoir, je programme un petit truc en ce moment qui demande que j'associe des données à ce genre de liste de combinaisons: la liste est facile à créer mais ensuite pour y associer les données, j'ai besoin de retrouver "facilement" et rapidement leur position dans la liste. J'aurais pu boucler sur la liste mais ça me semble plus efficace si je peux retrouver l'index par le calcul.

[mick605]

Bah oui Toulouse c'est l'autre bout du monde pour moi :-)

Ah ouais, t'habite ou ? Tokyo ?

Et non il ne s'agit pas d'un devoir, je programme un petit truc en ce moment qui demande que j'associe des données à ce genre de liste de combinaisons: la liste est facile à créer mais ensuite pour y associer les données, j'ai besoin de retrouver "facilement" et rapidement leur position dans la liste. J'aurais pu boucler sur la liste mais ça me semble plus efficace si je peux retrouver l'index par le calcul.

A c'est sur, c'est plus rapide et mieux par le calcul, et moins risqué, parce que ta liste, tu peux la modifier !

[mick605]

Tu calcules D=NbreLignes-Index
Ensuite, tu dois trouver un x (entier, compris entre 0 et n) le plus grand possible tel que
1+2+...+x < D (Strictement inferieur)
ou
x*(x+1)/2 < D

Tu auras ainsi i1 = n-D

Oula, grosse erreur de ma part ... je voulais dire i1 = n-x !

[GoustiFruit]

Ah ok. Mais c'est pas grave, je n'ai pas encore eu besoin de cette partie (et je ne sais pas si j'en aurais besoin). Par contre les 1 et 2 fonctionnent très bien dans mon code :-)