Discussion :

[duvi]

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 :

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
 
#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;
	}
 
}

[HanLee]

J'avoue que c'est bizarre, normalement t'es en situation de récursivité terminale, le compilateur doit savoir supprimer dérécursifier ça...

T'es sûr que l'algorithme est exactement le même ?

[duvi]

oui mais il faut choisir une option dans le compilateur pour qu'il le fasse je suppose ?? mais je ne sais pas laquelle ?

[reggae]

Je viens de m'en rendre compte, mais pour que ton algo soit vraiment écrit en C++, la fonction principale: main() doit retourner un entier(int).

[Volune]

Pour les optimisations, il suffit de chercher dans les propriétés du projet sous Visual (du moins sous la version 2005 -_-).
J'ai essayé avec mingw/g++ : gain allant jusqu'à 50% de temps en moins avec l'optimisation (-O2).

En passant : il y a un delete[] qui va avec ceci ?

Code :

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

echequier=new int[Nombre_reines];

[Alp]

Je viens de m'en rendre compte, mais pour que ton algo soit vraiment écrit en C++, la fonction principale: main() doit retourner un entier(int).

main retourne 0 par défaut, il me semble...

[Volune]

Je viens de m'en rendre compte, mais pour que ton algo soit vraiment écrit en C++, la fonction principale: main() doit retourner un entier(int).

main retourne 0 par défaut, il me semble...

Je pense qu'il parlat de cette ligne là :

Code :

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

void main(){

[Alp]

Ah en effet, j'avais cru voir int main, je ne sais pourquoi
Et puis, pour l'auteur :
tu mets using namespace std mais après tu utilises std::abs au lieu de abs tout court etc ... Bizarre ^^