Une solution en C++, dont je suis pas très fier du code (d'ailleurs, si quelqu'un pondait ça dans un de mes projets, je le dégage sec
J'y ajouterai quelques explications et j'essayerai de rendre le code plus potable.
Fonctionne parfaitement avec de grande valeur :
Il y a des optimisations très bourrine sur la génération des combinaisons.
Dernière version ici : http://www.developpez.net/forums/sho...0&postcount=55
Code C++ : 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83 #include <iostream> #include <vector> /*affiche un vecteur*/ void afficher(std::vector<int> & list) { std::cerr<<"["; for(int i =0; i <list.size()-1; i++) std::cerr<<list[i]<<", "; std::cerr<<list[list.size()-1]; std::cerr<<"], "<<std::endl; } /*calcul la somme d'un vecteur*/ int somme(std::vector<int> & list) { int total = 0; for(int i=0; i<list.size(); i++) total += list[i]; return total; } /*met tout le vecteur à 1 sauf le premier élément à n*/ void mettrePremierN(std::vector<int> & list, int n) { list[0] = n; for(int i = 1; i<list.size(); i++) list[i] = 1; } /*genère la combinaison suivante suivant un critère très particulier*/ void genererSuivant(std::vector<int> & list) { int currentMax = 0; int pos = 0; for(pos=0; pos<list.size()-1; pos++) if(list[pos+1]< list[pos]) currentMax = pos+1; if(pos == list.size()-1) list[currentMax]++; } /*génère l'ensemble des solutions dont la taille du vecteur vaut taille*/ void generationSolution(int n, int taille) { std::vector<int> list; for(int i=0; i<taille; i++) list.push_back(1); for(int i=1; i<=n; i++) { int total = 0; mettrePremierN(list, i); while(total<=n && list[0]==i) { total = somme(list); if(total == n) afficher(list); if(total >=n) break; genererSuivant(list); } } } /*génère l'ensemble des solutions*/ void generationSomme(int n) { for(int taille = n; taille>0; taille--) generationSolution(n, taille); } int main() { generationSomme(5); return 0; }
A partir, par exemple du vecteur : 4 1 1 1
genererSuivant génère successivement les combinaisons suivantes :
4 1 1 1
4 2 1 1
4 2 2 1
4 2 2 2
4 3 2 2
4 3 3 2
4 3 3 3
4 4 3 3
4 4 4 3
4 4 4 4
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
31
32
33
34
35
36
37 //Générer 10 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1, 1], [3, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 1, 1, 1, 1], [3, 2, 1, 1, 1, 1, 1], [4, 1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 1, 1], [3, 2, 2, 1, 1, 1], [4, 2, 1, 1, 1, 1], [5, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [3, 2, 2, 2, 1], [4, 2, 2, 1, 1], [5, 2, 1, 1, 1], [6, 1, 1, 1, 1], [3, 3, 2, 2], [4, 2, 2, 2], [5, 2, 2, 1], [6, 2, 1, 1], [7, 1, 1, 1], [4, 3, 3], [5, 3, 2], [6, 2, 2], [7, 2, 1], [8, 1, 1], [5, 5], [6, 4], [7, 3], [8, 2], [9, 1], [10], Press ENTER to continue.
Je pense que niveau rapidité et utilisation mémoire, je bats tout le monde pour l'instant. Par contre, niveau longueur de code, c'est pas ça
Partager