问题描述
假设我们有一个像{1,2,3}这样的集合，那么只有一种方法可以选择3个连续的数字...这就是集合{1,2,3} ...
Suppose we have a set like {1,2,3} then there is only one way to choose 3 consecutive numbers... it's the set {1,2,3}...
对于一组{1,2,3,4}，我们有3种方式:123 234 1234
For a set of {1,2,3,4} we have 3 ways: 123 234 1234
(从技术上讲，这是无序的数字集，但是连续写会有所帮助)
(technically these are unordered sets of numbers, but writing them consecutively helps)
- f(5); {1,2,3,4,5}-> 8种方式:
123123412351234523423453451345 - f(6); {1,2,3,4,5,6}-> 20种方式:...
- f(7); {1,2,3,4,5,6,7}-> 47种方式:...
- f(5) ; {1,2,3,4,5} -> 8 ways:
123123412351234523423453451345 - f(6) ; {1,2,3,4,5,6} -> 20 ways: ...
- f(7) ; {1,2,3,4,5,6,7} -> 47 ways: ...
因此，对于给定的N，我可以通过施加蛮力并计算所有具有3个或更多连续数字的子集来获得答案.
So for a given N, I can get the answer by applying brute force, and calculating all such subset having 3 or more consecutive number.
在这里，我只是想找出一种模式，一种获取给定N的所有此类子集的数量的技术.
Here I am just trying to find out a pattern, a technique to get the number of all such subset for a given N.
该问题进一步泛化为.....发现大小为N的集合中的m个连续数.
The problem is further generalized to .....discover m consecutive number within a set of size N.
推荐答案
此问题与某处连续至少有三个连续1的N位二进制数的数量"之间存在双射bijection是一个数字，如果不包含在子集中，则为0；如果包含在子集中，则为1).
There is a bijection between this problem and "the number of N-digit binary numbers with at least three consecutive 1s in a row somewhere" (the bijection being a number is 0 if excluded in the subset, and 1 if included in the subset).
这是一个已知问题，应该足以向Google提供信息以获取结果，如果您搜索number of n-digit binary strings with m consecutive 1s，则第二个匹配项是
This is a known problem, and should be enough information to google for a result, if you search for number of n-digit binary strings with m consecutive 1s, the second hit is Finding all n digit binary numbers with r adjacent digits as 1
或者，您也可以将其查找为 http ://oeis.org/search?q = 0 2^n - tribonacci(n+3)，请参阅此处，以获取有关Tribonacci数字的明确公式.它还给出了递归关系.给出的类比是在公平硬币的n次翻转中至少有3个正面朝上的1个冒牌的概率(在2 ^ n中)"
Alternatively you can just look it up as http://oeis.org/search?q=0%2C0%2C1%2C3%2C8%2C20%2C47 (based on the brute-forcing you did for the first few terms) - resulting in an explicit formula of 2^n - tribonacci(n+3), see here for an explicit formula for tribonacci numbers. It also gives a recurrence relation. The analogy given is "probability (out of 2^n) of getting at least 1 run of 3 heads within n flips of a fair coin"
我只能假设一般问题的答案是2 ^ n-F (n + m)，其中F 是m n步斐波那契数( 似乎是这种情况 )
I can only assume that the answer to the general problem is 2^n - F(n+m), where F is the m n-step Fibonacci number (edit: that does seem to be the case)
这篇关于{1,2,3，...，N}包含至少3个连续元素的子集数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！