problème des N reines récursif
Bonjour
Voici le code utilisé pour trouver de manière récursive les N reines. (backtrack simple)
Ce code est très compact mais seul petit hic c que à l'exécution il semble plus lent que certains programme tout fait que j'ai trouve itératif.
Alors je me demandais s'il était possible de doper le programme récursif si oui de quelles manières ?
Existe t il une option dans le compilateur (j'utilise visual studio dot net 2003) pour qu'il transforme a la compilation la partie récursive en itératif ou du moins améliorer la vitesse du récursif ?
merci d'avance
voici le code
Code:
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
|
#include <iostream>
#include <cmath>
using namespace std;
void affichage(int *echequier,int N){
for(int i=0;i<N;i++){
cout<<echequier[i];
}
cout<<endl;
}
inline bool solution(int *echequier, int &nombre_solution,int i_max,int N){ //inline accélère
for(int i=0;i<i_max-1;i++){
for(int j=i+1;j<i_max;j++){
if((std::abs(echequier[i]-echequier[j])==std::abs(i-j))||(echequier[i]==echequier[j])){
return false;
}
}
}
if(i_max==N){
nombre_solution++;
} // si va jusqu'au bout de la boucle c'est que les dames se prennent pas en diagonale)
return true;
}
void generer(int *echequier,int etat_avancement,int N,int &nombre_solution){
if(etat_avancement==N){
for(int i=1;i<=N;i++){
echequier[etat_avancement-1]=i;
solution(echequier,nombre_solution,N,N);
}
}
else{
for(int i=1;i<=N;i++){
echequier[etat_avancement-1]=i;
if(solution(echequier,nombre_solution,etat_avancement,N)==false){
continue;
}
generer(echequier,etat_avancement+1,N,nombre_solution);
}
}
}
void main(){
int *echequier;
while(1){
int Nombre_reines,compteur=0;
do{
cout<<"Entrez le nombre de reines voulues"<<endl;
cin>>Nombre_reines;
}while(Nombre_reines<1);
echequier=new int[Nombre_reines];
generer(echequier,1,Nombre_reines,compteur);
cout<<compteur<<endl;
}
} |
