期中考最后一题,应该是有关排列组合的
给定n个不同的数,问这n个数可以组成多少个不同的序列且序列中相邻的元素之差大于一。一开始我用递归进行全排列,然后逐个比较。后来看到最多有25个数,就知道肯定超时了(时间复杂度已经达到O(n!)了)。不知各位大牛有何建议?这肯定是有简便方法的,不过我就是没想出来。。。
附上我超时的代码:
#include<iostream>
using namespace std;
int fabs(int n)
{
if(n<0)
return -n;
else
return n;
}
int counter=0;
void Swap(int& a,int& b)
{
int temp=a;
a=b;
b=temp;
}
void pai(int a[],int n,int k,int end)
{
int flag=1;
if(k==end)
{
//cout<<"yes.\n";
/*for(int i=0;i<n-1;i++)
{
if((a[i]-a[i+1]==1)||(a[i]-a[i+1]==-1))
return;
}*/
counter++;
return;
/*for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;*/
}
for(int i=k;i<n;i++)
{
Swap(a[k],a[i]);
if(fabs(a[k]-a[k+1])>1)
{
if(k>=1)
{
if(fabs(a[k]-a[k-1])>1)
pai(a,n,k+1,end);
}
else
pai(a,n,k+1,end);
}
//pai(a,n,k+1,end);
Swap(a[k],a[i]);
}
}
int main()
{
int T,num;
int a[26];
cin>>T;
while(T--)
{
counter=0;
cin>>num;
for(int i=0;i<num;i++)
cin>>a[i];
pai(a,num,0,num-1);
cout<<counter<<endl;
}
return 0;
}