C语言排列搜索（共1篇）
C语言排列搜索 篇1
注：虽然没有通过测试，但学会了用递归实现全排序的方法(话说此题的通过率真低呀，哪位高手知道正确答案呢?)
但刚才用gcc测了下，当N=11时，运行时间为2.3s(我的机子是linux mint 16 64bit, 酷睿双核)，之前在windows上跑要7、8s呢
题目详情：
设数组a包含n个元素恰好是0..n - 1的一个排列，给定b[0],b[1],b[2],b[3]，
问：有多少个0..n-1的排列a，满足(a[a[b[0]]]*b[0]+a[a[b[1]]]*b[1]+a[a[b[2]]]*b[2]+a[a[b[3]]]*b[3])%n==k ?
输入包含5个参数：N,K,B0,B1,B2,B3，其中 4<= N<12, 0 <= K,B0,B1,B2,B3 < N，
解题代码：
#include
#define MAX_N 11
int a[MAX_N] = {0};
int g_count = 0;
int g_N;
int g_K;
int g_B0;
int g_B1;
int g_B2;
int g_B3;
// swap a[i] and a[offset]
void swap(int i, int offset)
{
int temp = a[i];
a[i] = a[offset];
a[offset] = temp;
}
// find permutation (全排列)
void perm(int offset)
{
if (g_N-1 == offset)
{
g_count += (a[a[g_B0]]*g_B0 + a[a[g_B1]]*g_B1 + a[a[g_B2]]*g_B2 + a[a[g_B3]]*g_B3)%g_N==g_K;
return;
}
else
{
int i;
for (i = offset; i < g_N; ++i)
{
swap(i, offset);
perm(offset + 1);
swap(i, offset);
}
}
}
int howmany (int N,int K,int B0,int B1,int B2,int B3)
{
g_N = N;
g_K = K;
g_B0 = B0;
g_B1 = B1;
g_B2 = B2;
g_B3 = B3;
// init array a
int i;
for (i = 0; i < N; ++i)
{
a[i] = i;
}
perm(0);
return g_count;
}
// 该段代码可能在庞果上编译不过(庞果你又调皮了)，把报错的那个局部变量改为全局变量即可，