几种求排列数的方法例如:给出n=3求得所有的排列数为 1 2 3 ,1 3 2,2 1 3,2 3 1,3 1 2 ,3 2 1一共有几种算法可以求出这个结果呀?
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/16 09:18:26
几种求排列数的方法例如:给出n=3求得所有的排列数为 1 2 3 ,1 3 2,2 1 3,2 3 1,3 1 2 ,3 2 1一共有几种算法可以求出这个结果呀?
几种求排列数的方法
例如:给出n=3
求得所有的排列数为 1 2 3 ,1 3 2,2 1 3,2 3 1,3 1 2 ,3 2 1
一共有几种算法可以求出这个结果呀?
几种求排列数的方法例如:给出n=3求得所有的排列数为 1 2 3 ,1 3 2,2 1 3,2 3 1,3 1 2 ,3 2 1一共有几种算法可以求出这个结果呀?
前面的热心网友回答的那种穷举法可以,但比较耗时且不易扩展.
全排列问题其实就是一个深度搜索的问题,一般采取回溯法来解决.
当然就具体问题还要考虑剪枝等细节问题,不过你这里只是全排列就不用考虑那么多了.
比较有名的题目是八皇后问题.
下面给一个全排列问题的递归解法,改变N的值可以对不同数进行全排列.
如果要求输入n来全排列的话把数组a改成动态分配,并作为参数送入各个函数就行了.
#include <iostream>
using namespace std;
#define N 3
int a[N];
void printSeq()
{
for(int i=0; i<N; i++) cout << a[i] << " ";
cout << endl;
}
bool isok(int i, int k)
{
for(int j=0; j<i; j++)
{
if(a[j] == k) return false;
}
return true;
}
void calcSeq(int i)
{
if(i==N) printSeq();
else
{
for(int k=1; k<=N; k++)
{
if(isok(i, k))
{
a[i] = k;
calcSeq(i+1);
}
}
}
}
int main()
{
calcSeq(0);
return 0;
}
另外也有非递归解法,模拟一个栈来做