Discussion :

[CondensationdeCauchy]

Bonjour!
Je suis en train de développer un programme qui trouve les n-uplets tel que la somme des éléments compris entre 1 et m soit égale à un nombre s et tel que chaque élément du n-uplet est différent des autres. Par exemple, si l'utilisateur spécifie s=15, m=9 et n=3, le programme retournera les triplets (1,5,9), (1,6,8), (2,4,9), (2,5,8), (2,6,7), (3,4,8),(3,5,7) et (4,5,6). J'ai commencé à écrire un code pour trouver des triplets (pour n = 3) qui satisfont la consigne.

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#include <stdio.h> 
 
void TrouverTuplets(int m, int s) {
    printf("Entrer le nombre d'entiers à utiliser et la somme du triplet : ");
    scanf("%d%d", &m, &s);
    int i;
    int j;
    int k;
    for (i = 1; i <= m; i++){
        for (j = i+1; j <= m; j++){
            for (k = j+1; k <= m; k++){
                int numero=1;
                if (i + j + k == s) {
                      printf("Triplet no. %d: ( %d, %d, %d) \n", numero, i, j, k);
                numero ++;
                      }
                }
            }
        }
    }
 
 
int main() {
    int m;
    int s;
    TrouverTuplets(m, s);
    getchar();
    return 0;
}

Celui-ci fonctionne. Maintenant, je dois généraliser pour un nombre n de variables i1, i2, ... , in mais je sais plus ou moins comment m'y prendre. Il y aura n boucles imbriquées. Y a-t-il une façon simple, élégante de le faire?

[picodev]

Bonjour,

plusieurs remarques :

• tu ferais mieux de demander les valeurs de m et s hors de ta fonction de calcul
  
  
• une petite optimisation d'algorithme :
  au lieu de parcourir les n-uples, parcours uniquement les (n-1)-uples, si s moins la somme des composants de ton (n-1)-uple est inférieur à m et supérieur la dernière composante alors tu as une solution. Dans ton exemple on aurait :
  
  (1,2) : 15 - (1+2) = 12 > 9 donc pas de 3-uple commençant par 1,2
  ...
  (1,5) : 15 - (1+5) = 9 ≤ 9 une solution (1,5,9)
  ...
  (1,7) : 15 - (1+7) = 7 ≤ 7 pas de tuple commençant par 1,7 ni 1,8 ni 1,9 on peut commencer la recherche avec ceux commençant par 2
  Tu peux «économiser» une boucle
  
  
• autre optimisation d'algorithme :
  le premier tuple visité sera toujours (1,2, ..., n) et le dernier (m-n+1, m-n+2, ..., m).
  Dans ton exemple tu parcours lexicographiquement les triplets de (1,2,3) à (7,8,9). Tout comme tu as déjà réduit l'espace de recherche ne commençant pas toutes tes boucles à 1, tu peux ne pas toutes les terminer à m.

Pour en revenir à ta question, pour simuler dynamiquement n boucles, il te faut un tableau de n cases. La i^ème case contiendra la valeur de l'indice de la i^ème boucle. Passer «au tour suivant» consistera donc à incrémenter ces valeurs en commençant par la fin. Le principe de base est celui d'un odomètre en fait.
Il va bien sûr falloir vérifier au préalable que m,n et s satisfont les contraintes pour que de tels tuples existent.

En gros il te faudra un type qui contiendra les valeurs de m,n,s et un tuple courant. En ce qui concerne les primitives il te faudra au minimum une de création, une qui initialise le tuple courant au premier, une qui détermine s'il s'agit du dernier et une qui va incrémenter le tuple courant (sans doute la plus délicate).