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
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <iterator>
//#define AFFICHER
int nbvalue(0);
typedef unsigned int DecompType;
inline void afficher(const std::vector<DecompType> & myVect,const DecompType & nb)
{
nbvalue++;
#ifdef AFFICHER
if (nb==0) return;
std::cout<<"[";
std::copy(myVect.begin(),myVect.begin()+nb-1,std::ostream_iterator<int>(std::cout,", "));
std::cout<<myVect[nb-1]<<"]\n";
#endif
}
//fonction récussive
inline void generate(std::vector<DecompType> & myVect,const DecompType & reste ,const DecompType & nb_precedent,const DecompType & level)
{
if (reste ==1)
{
myVect[level]=1;
afficher(myVect,level+1);
}
else
{
//on interdit que le chiffre que l'on va traiter puisse etre plus grand que le précédent
for (DecompType i=std::min(reste,nb_precedent);i>1 ;--i)
{
//on met le chii=ffre courant à i
myVect[level] = i;
//on traite le prochain chiffre avec le reste
//si reste ==i alors la somme des chiffres est bien ègale au chiffre de dépard
//sinon on passe au chiffre suivant
if (reste==i)
afficher(myVect,level+1);
else
generate(myVect,reste-i,i,level+1);
}
//cas ou le nombre courant est mis à 1
//td::vector<int>::iterator it = myVect.begin()+level;
myVect[level]=1;
myVect[level+reste-1]=1;
afficher(myVect,level+reste);
}
}
int main()
{
clock_t t1=std::clock();
DecompType n =100;
std::vector<DecompType> myVect(n);
DecompType level (0);
generate(myVect,n,n,level);
clock_t t2=std::clock();
std::cout<<nbvalue<<std::endl;
std::cout<<double(t2-t1)/CLOCKS_PER_SEC<<std::endl;
return 0;
} |
R�pondre avec citation
Envoy� par Steki-kun
-unsafe � la limite ca acc�lerera un chouia les acces tableaux...
Partager