我只是发现这样的问题
给你n个不同的整数,你知道有多少个不同的序列,每对相邻的数字之间的差大于1吗?
当整数是“123”时,答案是零,当整数是“531”时,答案是6,对于“135”“1535”“315”“315”“351”“513”“531”满足问题,我只是尽我所能,但我无法解决它,所以我的问题是,如何编写一个算法来解决它。
谢谢你。
这是我的程序
int n;bool vi[30];int a[30];int b[30];int counter = 0;
void dfs(int k)
{
if ( k == n)
{
for (int i = 2; i <= n; i ++)
if (fabs(b[i] - b[i - 1]) <= 1) return ;
counter ++;
return ;
}
for (int i = 0; i < n; i ++)
{
if (!vi[i])
{
b[k + 1] = a[i];
vi[i] = true;
dfs(k + 1);
vi[i] = false;
}
}
}
int main (void)
{
cin >> n;
for (int i = 0; i < n; i ++)
cin >> a[i];
memset(vi, 0, sizeof(vi));
for (int i = 0; i < n; i ++)
{
vi[i] = true;b[1] = a[i];dfs(1);vi[i] = false;
}
cout << counter << endl;
return 0;
}
最佳答案
“有多少个不同的序列…”这个问题的答案可以在不枚举每个组合的情况下解决。这是一件好事,因为25!
大约是1.55×10 ^ 24,或者比任何现有的计算机在一秒钟内要枚举的要多。或者一年后。
这是一道数学题,特别是组合数学有关如何解决问题的信息,请参见http://en.wikipedia.org/wiki/Combinatorics和可能的http://en.wikipedia.org/wiki/Combinations。