读书人

递归回溯法生成1~N的排列

发布时间: 2012-04-26 14:01:31 作者: rapoo

求助:递归回溯法生成1~N的排列
从一篇讲义中获取的算法,可结果不对:
完整代码如下,请高手看一下错在什么地方:
-----------------

#include <iostream>
using namespace std;

#define N 3
int x[N+1];
void swap(int *a ,int *b)
{
int temp;
temp = *a;
*a = *b;
*b =temp;
}

void output(int x[])
{
for(int i=1;i <=N;i++)
cout < <x[i];
cout < <endl;
}

int Backtrack(int t)
{
if (t> N)
output(x);
else
for( int i = t; t <= N; t++) {
swap(&x[t], &x[i]);
Backtrack(t+1);
swap(&x[t], &x[i]);
}

return 0;
}

int main(int n)
{
for(int i=1;i <=N;i++)
x[i]=i;
Backtrack(1);


return 0;
}

[解决办法]
for( int i = t; i <= N; i++)
[解决办法]
//这样改就可以了:
#include <iostream>
using namespace std;

#define N 3
int x[N+1];
void swap(int *a ,int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}

void output(int x[])
{
for(int i=1;i <=N;i++)
cout < <x[i] < < " ";
cout < <endl;
}

int Backtrack(int t)
{
if (t > N )
output(x);
else
for( int i = t; i <= N; i++) {
swap(&x[t], &x[i]);
Backtrack(t + 1);
swap(&x[t], &x[i]);
}

return 0;
}

int main(int n)
{
for(int i = 1; i <= N; i++)
x[i] = i;
Backtrack(1);


return 0;
}

读书人网 >软件架构设计

热点推荐