我只是发现这样的问题
给你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

09-25 19:56