3

我只是发现这样的问题

“给你N个不同的整数，你知道有多少个不同的序列，每对相邻的数字之差大于1吗？”

当整数为“1 2 3”时，答案为零，当整数为“5 3 1”时，答案为6，对于“1 3 5”“1 5 3”“3 1 5”“ 3 5 1" "5 1 3" "5 3 1" 满足问题，我只是尝试了所有我能做的但我无法解决它，所以我的问题是，如何编写一个算法来解决它。

谢谢你。

这是我的程序

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;
}
4

3 回答 3

0

“有多少不同的序列......”这个问题的答案可以在不列举每个组合的情况下解决。这是一件好事，因为25!大约是 1.55 x 10^24，或者比任何现有计算机在一秒钟内枚举的多得多。或者一年之内。

这是一道数学题，特别是组合数学题。有关如何解决问题的信息，请参阅http://en.wikipedia.org/wiki/Combinatorics和可能的http://en.wikipedia.org/wiki/Combinations 。

于 2012-04-24T13:07:01.050 回答
0

似乎“中间相遇”原则可以提供合理的工作时间。

草图：

将数字列表分成相等的部分（奇数长度为 +-1）。有 C(N, N div 2) 变体。

计算所有固定的最后和第一个元素的前半部分和后半部分的有效排列数（递归）。为兼容的最后一个元素和第一个元素相乘。

编辑：发现更可靠的变体：

让我们 FullSet = (A, B, C, D) 计算有效排列，从 A 开始，我们应该计算没有 A 的集合 (B, C, D) 的有效排列，从值开始，与 A 兼容。同样如此对于有效的排列，从 B 开始等等......

我最初编写了递归函数来访问所有初始值并计算没有这些值的集合的有效排列。它仅适用于小型套装。

然后我使用记忆来记住组合 [InitialValue, Set] 的计数（以避免对同一集合重复计算）。这就是自上而下的动态规划。

最后，我将动态编程从自上而下转变为升序风格——这是可能的，因为我们可以按顺序填充记忆表。

复杂度为 O(N^2 * 2^N)，内存消耗为 O(N * 2^N)，因为我们应该（几乎）检查完整集的所有 2^N 个子集。所以我可以对 N <= 20 使用这种方法（如果 Int64 类型对 Count 来说足够了）。

德尔福代码：

var
  A: TArray<Byte>;
  Memo: array of array of Int64;
  N, Mask, msk, index, i: Integer;
  Count: Int64;
  OnlyOneOneBit: Boolean;

begin
  A := TArray<Byte>.Create(1, 2, 4, 5);

  N := Length(A);
  Mask := (1 shl N) - 1;//binary 000111111 with n ones

  SetLength(Memo, 1 shl N {2^N}, N);

  for msk := 1 to Mask do begin // all possible subsets, excluding empty one
    OnlyOneOneBit := 0 = (msk and (msk - 1));
    for index := 0 to N - 1 do
       if OnlyOneOneBit then
         Memo[msk, index] := (msk shr index) and 1 // 1 if indexth bit = 1 else 0
       else if 0 <> ((msk shr index) and 1) then begin
         Count := 0;
         for i := 0 to N - 1 do
           if Abs(A[i] - A[index]) > 1 then //compatible numbers
              Count := Count + Memo[msk xor (1 shl index), i];
     //use previous result for the set without index element, starting with ith
         Memo[msk, index] := Count;
       end;
  end;

  Count := 0;
  for index := 0 to N - 1 do
    Count := Count + Memo[Mask, index];

使用示例 (1, 2, 4, 5) 的结果是 8 手动检查：1425 1524 2415 2514 4152 4251 5142 5241

于 2012-04-24T13:29:48.560 回答
0

为了比枚举所有排列并检查它们的 O(n!) 方法更快地找到解决方案 - 我会注意到这个问题是计算图 (V, E) 上所有哈密顿路径的一个实例，其中 V 是原始列表的成员和 E 是连接可以相邻的成员的边。（所以你的第二个例子是 V={1,3,5} 和 E={(1,3),(3,5),(1,5)}。）

我不知道您将如何有效地计算哈密顿路径，但也许这是解决问题的方法。

于 2012-04-24T17:07:03.387 回答