3

假设我们有一个这样的集合，{1,2,3}那么只有一种方法可以选择 3 个连续的数字......它是集合 {1,2,3}......

对于一组 {1,2,3,4}，我们有 3 种方式：123 234 1234

（从技术上讲，这些是无序的数字集，但连续编写它们会有所帮助）

  • f(5) ; {1,2,3,4,5} -> 8 种方式：123 1234 1235 12345 234 2345 345 1345
  • f(6) ; {1,2,3,4,5,6} -> 20 种方式：...
  • f(7) ; {1,2,3,4,5,6,7} -> 47 种方式：...

因此，对于给定的 N，我可以通过应用蛮力得到答案，并计算所有具有 3 个或更多连续数字的子集。

在这里，我只是想找出一种模式，一种获得给定 N 的所有此类子集数量的技术。

问题被进一步推广到......在一组大小为 N 中发现 m 个连续数。

4

5 回答 5

5

此问题与“在某处某处连续至少三个连续1s 的 N 位二进制数的数量”之间存在双射（如果排除在子集中，则作为数字的双射为 0，如果包含在子集中，则为 1） .

这是一个已知问题，应该是足够的信息来谷歌搜索结果，如果你搜索number of n-digit binary strings with m consecutive 1s，第二次点击是查找所有 n 位二进制数，其中 r 个相邻数字为 1

或者，您可以将其查找为http://oeis.org/search?q=0%2C0%2C1%2C3%2C8%2C20%2C47（基于您对前几个术语所做的暴力破解） - 结果在 的显式公式中2^n - tribonacci(n+3)，请参阅此处以获取 tribonacci 数的显式公式。它还给出了递归关系。给出的类比是“在公平硬币的 n 次翻转中获得至少 1 次 3 正面的概率（在 2^n 中）”

我只能假设一般问题的答案是 2^n - F m (n+m)，其中 F m是第 m个 n 步斐波那契数（编辑：似乎确实如此）

于 2012-09-07T06:39:29.457 回答
0

这对我来说听起来像是家庭作业，所以我会让你开始。FoOne 的方法是考虑运行的最低和最高成员 L 和 H。如果设置大小为 N，并且您的最小运行长度为 M，那么对于 L 的每个可能位置 P，您可以计算出有多少个位置H 有....

于 2012-09-07T05:00:55.933 回答
0

不知道你的意思是不是连续的。如果不是，那么对于 {1, 2, 3, 4} 有 4 种可能性： {1, 2, 3} {2, 3, 4} {1, 3, 4} {1, 2, 3, 4}

我认为你可以用 N!/3! 计算解决方案！其中N！= N*(N-1) (N-2) ...*1。

于 2012-09-07T05:03:37.517 回答
0

使用一些 python 代码，我们可以调查这个：

y = set()

def cons(li, num):
    if len(li) < num:
        return
    if len(li) == num:
        y.add(tuple([i for i in li]))
    else:
        y.add(tuple([i for i in li]))
        cons(li[1:], num)
        cons(li[:-1], num)

这个解决方案会很慢（实际上它的复杂性是指数级的），但是尝试一些小的列表大小，我认为你应该能够掌握这种模式。

于 2012-09-07T05:09:07.333 回答
0

快速回答：

Sequences(n) = (n-1)*(n-2) / 2

长答案：

你可以通过归纳来做到这一点。首先，我要重新陈述问题，因为您的问题陈述不够清楚。

  • 规则 1：对于所有连续数字 1..n 的集合，其中 n 为 2 或更大

  • 规则 2：计算连续数 m..m+q 的子集 S(n)，其中 q 为 2 或更多

S(n=3)

通过检查，我们发现只有一个 - 123

S(n=4)

通过检查，我们发现 3！- 123 234 和 1234

请注意，S(4) 包含 S(3)，加上两个新的……都包括新的数字 4……嗯。

S(n=5)

通过检查，我们发现 ... S(n=4) 以及 345 2345 和 12345。总共 3+3=6。

我认为这里形成了一种模式。让我们定义一个新的函数 T。

  • 规则 3：S(n) = S(n-1) + T(n) ... 对于某个 T。

我们知道 S(n) 包含数字 n，并且现在应该已经发现 S(n) 还包含（作为子组件）所有长度为 3 到 n 的序列，其中包括数字 n。我们知道它们不能在 S(n-1) 中，所以它们必须在 T(n) 中。

  • 规则 4：T(n) 包含所有以 n 结尾且长度为 3 到 n 的序列。

S(n)中有多少个序列？

让我们回顾一下 S(3) S(4) 和 S(5)，并合并 T(n)：

  • S(3) = S(3)
  • S(4) = S(3) + T(4)
  • S(5) = S(4) + T(5) = S(3) + T(4) + T(5)

让我们概括一下：

  • 对于从 4 到 n 的所有 f，S(n) = S(3) + T(f)。

那么给定的 T 中有多少个呢？

回顾规则 5 - 它描述了多少个序列？

对于 T(4)，它描述了所有以 4 结尾的序列 3 和更长的序列。（即 234）

对于 T(5)，它描述了所有以 5 结尾的序列 3 和更长的序列。（即 345 2345 = 2）

T count Examples
4 2     1234 234
5 3     12345 2345 345
6 4     123456 23456 3456 456

看起来非常像 T(n) 只是 n-2 ！

所以

S(6) = T(6) + T(5) + T(4) + S(3)
  10 = 4    + 3    + 2    + 1

S(7) = 15 = 5 + 4 + 3 + 2 + 1 S(8) = 21 = 6 + 5 + 4 + 3 + 2 + 1

把它变成一个公式

2 * S(8) 是多少？

42 = 6 + 5 + 4 + 3 + 2 + 1 + 1 + 2 + 3 + 4 + 5 + 6

将每对最大和最小数字相加：

42 = 7 + 7 + 7 + 7 + 7 + 7

42 = 7 * 6

但这是 2 * S(8)，所以

S(8) = 42/2 = 21 = 7 * 6 / 2

这概括了：

S(n) = (n-1)*(n-2) / 2

让我们检查一下这是否有效：

S(3) = 2*1/2 = 1
S(4) = 3*2/2 = 3
S(5) = 4*3/2 = 6
S(6) = 5*4/2 = 10

我很满意。

于 2012-09-07T06:47:39.713 回答