1

我需要划分一个S={1, 2, 3, … , n}由连续数字组成的集合，使得每个子集至少有 2 个元素（规则 1）并且它由连续数字组成（规则 2）。

规则是：

  1. 每个子集至少有两个元素。

  2. 所有子集的所有元素都是连续的。

  3. S 的所有元素都包含在分区中。

例子：

There is 1 subset for n = 2: 
1 2
There is 1 subset for n = 3:  
1 2 3   
There are 2 subset combinations for n = 4:
1 2 3 4
1 2 - 3 4
There are 3 subset combinations for n = 5:
1 2 3 4 5
1 2 - 3 4 5
1 2 3 - 4 5
There are 5 subset combinations for n = 6:
1 2 3 4 5 6
1 2 - 3 4 5 6
1 2 3 - 4 5 6
1 2 3 4 - 5 6
1 2 - 3 4 - 5 6
There are 8 subset combinations for n = 7:
1 2 3 4 5 6 7
1 2 - 3 4 5 6 7
1 2 3 - 4 5 6 7
1 2 3 4 - 5 6 7
1 2 3 4 5 - 6 7
1 2 - 3 4 - 5 6 7
1 2 - 3 4 5 - 6 7
1 2 3 - 4 5 - 6 7
There are 13 subset combinations for n = 8:
1 2 3 4 5 6 7 8
1 2 - 3 4 5 6 7 8
1 2 3 - 4 5 6 7 8
1 2 3 4 - 5 6 7 8
1 2 3 4 5 - 6 7 8
1 2 3 4 5 6 - 7 8
1 2 - 3 4 - 5 6 7 8
1 2 - 3 4 5 - 6 7 8
1 2 - 3 4 5 6 - 7 8
1 2 3 - 4 5 - 6 7 8 
1 2 3 - 4 5 6 - 7 8
1 2 3 4 - 5 6 - 7 8
1 2 - 3 4 - 5 6 - 7 8
There are 21 subset combinations for n = 9:
1 2 3 4 5 6 7 8 9
1 2 - 3 4 5 6 7 8 9
1 2 3 - 4 5 6 7 8 9
1 2 3 4 - 5 6 7 8 9
1 2 3 4 5 - 6 7 8 9
1 2 3 4 5 6 - 7 8 9
1 2 3 4 5 6 7 - 8 9
1 2 - 3 4 - 5 6 7 8 9
1 2 - 3 4 5 - 6 7 8 9
1 2 - 3 4 5 6 - 6 7 9
1 2 - 3 4 5 6 7 - 8 9
1 2 3 - 4 5 - 6 7 8 9 
1 2 3 - 4 5 6 - 7 8 9
1 2 3 - 4 5 6 7 - 8 9
1 2 3 4 - 5 6 - 7 8 9
1 2 3 4 - 5 6 7 - 8 9
1 2 3 4 5 - 6 7 - 8 9
1 2 - 3 4 - 5 6 - 7 8 9
1 2 - 3 4 - 5 6 7 - 8 9
1 2 - 3 4 5 - 6 7 - 8 9
1 2 3 - 4 5 - 6 7 - 8 9
There are 34 subset combinations for n = 10:
1 2 3 4 5 6 7 8 9 10
1 2 - 3 4 5 6 7 8 9 10
1 2 3 - 4 5 6 7 8 9 10
1 2 3 4 - 5 6 7 8 9 10
1 2 3 4 5 - 6 7 8 9 10
1 2 3 4 5 6 - 7 8 9 10
1 2 3 4 5 6 7 - 8 9 10
1 2 3 4 5 6 7 8 - 9 10
1 2 - 3 4 - 5 6 7 8 9 10
1 2 - 3 4 5 - 6 7 8 9 10
1 2 - 3 4 5 6 - 6 7 9 10
1 2 - 3 4 5 6 7 - 8 9 10
1 2 - 3 4 5 6 7 8 - 9 10
1 2 3 - 4 5 - 6 7 8 9 10
1 2 3 - 4 5 6 - 7 8 9 10
1 2 3 - 4 5 6 7 - 8 9 10
1 2 3 - 4 5 6 7 8 - 9 10
1 2 3 4 - 5 6 - 7 8 9 10
1 2 3 4 - 5 6 7 - 8 9 10
1 2 3 4 - 5 6 7 8 - 9 10
1 2 3 4 5 - 6 7 - 8 9 10
1 2 3 4 5 - 6 7 8 - 9 10
1 2 3 4 5 6 - 7 8 - 9 10
1 2 - 3 4 - 5 6 - 7 8 9 10
1 2 - 3 4 - 5 6 7 - 8 9 10
1 2 - 3 4 - 5 6 7 8 - 9 10
1 2 - 3 4 5 - 6 7 - 8 9 10
1 2 - 3 4 5 - 6 7 8 - 9 10
1 2 - 3 4 5 6 - 7 8 - 9 10
1 2 3 - 4 5 - 6 7 - 8 9 10
1 2 3 - 4 5 - 6 7 8 - 9 10
1 2 3 - 4 5 6 - 7 8 - 9 10
1 2 3 4 - 5 6 - 7 8 - 9 10
1 2 - 3 4 - 5 6 - 7 8 - 9 10

我没有在这里写下来，但是对于 n = 11 有 55 个子集组合，对于 n = 12 有 89 个子集组合。

我需要编写一个列出 n 的所有可能子集组的 Visual Basic 代码。几天来我一直在思考解决方案，但似乎问题的解决方案超出了我的能力范围。所需的嵌套循环的数量随着 n 的增加而增加，我无法弄清楚如何随着数量的增加对嵌套循环进行编程。任何帮助将不胜感激。

经过一番研究，我发现这是“所有部分 > 1 的 n 组合”的问题，并且可能组合的总数是斐波那契数（n 的 Fn-1）。

4

2 回答 2

1

我对您的回答是尝试提出给定模式的递归关系。递归思考。我怎样才能把这个问题分解成更小的子问题，直到达到最小的问题。解决那个最小的问题。在解决了那个最小的问题之后，想想归纳。假设第 n 步将是什么以及您将如何到达第 (n+1) 步。尝试解决第 (n+1) 步。一旦你对给定的模式提出了递归关系，就应该不难考虑如何递归地解决这个模式。这种方法可能更直观，而不是尝试使用嵌套循环。

于 2015-03-02T18:41:08.063 回答
1

我们已经知道这些情况的答案（正如您在示例中所写）：

  1. n=2
  2. n=3
  3. n=4

对于 n=5：

  • 您可以从 2 进行分区：1 2 - 3 4 5。这就像将 5 个成员集分成两组，第一个 n=2，第二个 n=3。我们现在可以继续划分每一半，但我们已经知道当 n=2 和 n=3 时的解！
  • 您可以从 3 进行分区：1 2 3 - 4 5。这就像将 5 个成员集分成两组，第一个 n=3，第二个 n=2。我们现在可以继续划分每一半，但我们已经知道当 n=2 和 n=3 时的解决方案！

对于 n=6：

  • 您可以从 2 分成两组：1 2 - 3 4 5 6。这就像将 6 个成员集分成两组，第一个 n=2，第二个 n=4。我们现在可以继续划分每一半，但我们已经知道 n=2 时的解。通过假设n = 4来解决下半部分！
  • 你可以从 3 分成两组：1 2 3 - 4 5 6。这就像把 6 个成员集分成两组，第一个 n=3，第二个 n=3，我们现在可以继续划分每一半，但是我们已经知道当 n=3 和 n=3 时的解决方案！
  • 您可以从 3 分成两组：1 2 3 4 - 5 6。这就像将 6 个成员集分成两组，第一个 n=4，第二个 n=2，我们现在可以继续划分每一半。通过设置 n=4 解决前半部分。对于后半部分，我们已经知道 n=2 时的解！

这是一个简单的递归关系。一般情况：

Partition (S): (where |S|>4)
- For i from 2 to |S|-2, partition the given set into two halves: s1 and s2 from i (s1={1,...,i}, s2={i+1,...,n}), and print the two subsets as a solution.
- Recursively continue for each half by calling Partition(s1) and Partition(s2)

---

另一个可能更难的解决方案是假设我们将数字划分为多个1 to n部分n，其中每个部分的长度可以是0、2或大于 的数字2。换句话说，让我们xi成为每个部分的长度：

x1 + x2 + ... xn = n, where the range of xi is: {0} + [2,n]

这是一个线性不等式系统，可以通过这里描述的方法来解决。

于 2015-03-02T21:49:27.947 回答