17 个解决方案
#1
LZ的意思是18位的2进制编码中,包括4个连续的1的编码有多少种么?(连续5个的不算对么?)
#2
还是编程算吧。数学上太难 根据题意必定包含仅包含一个011110
可以用三个字节从0开始一直加1 每次进行判定.
要不用 bitset 不过还要考虑到环的问题 写起来真麻烦.
可以用三个字节从0开始一直加1 每次进行判定.
要不用 bitset 不过还要考虑到环的问题 写起来真麻烦.
#3
帮顶一下
#4
我试了一下,不知道对不对:
必定包含仅包含一个011110的组合 = 包含011110的组合 - 包含011110但至少还有另外一个1111的组合
包含011110的组合: = 18 * 2^12 - 重复数
重复数指的譬如01111001111000000,1-6的六位数和7-12的六位数是同一组合.
包含011110但至少还有另外一个1111的组合: = 18 * 8 * 2^8 - 重复数
因为重复数在必定包含仅包含一个011110的组合不存在,所以上面两个重复数必然相等.
===> 必定包含仅包含一个011110的组合 = 18 * 2^12 - 18 * 8 * 2^8 = 18 * 2^11
必定包含仅包含一个011110的组合 = 包含011110的组合 - 包含011110但至少还有另外一个1111的组合
包含011110的组合: = 18 * 2^12 - 重复数
重复数指的譬如01111001111000000,1-6的六位数和7-12的六位数是同一组合.
包含011110但至少还有另外一个1111的组合: = 18 * 8 * 2^8 - 重复数
因为重复数在必定包含仅包含一个011110的组合不存在,所以上面两个重复数必然相等.
===> 必定包含仅包含一个011110的组合 = 18 * 2^12 - 18 * 8 * 2^8 = 18 * 2^11
#5
用程序算了一个51016, 规则是最长连续4个1,并且只有1个4个1的串,剩下可以有连续3个的。
不知道是否满足LZ的要求。
不知道是否满足LZ的要求。
#6
donkey301的看来有道理
#7
能编程产生合乎要求的随机数吗？用程序实现产生要求的随机数才是最终目的
#8
如果我是必须要4个1开头呢？主要是要用4个1作为同步，做一个环形条码。
#9
除了4个1开头之外,有什么其他的要求么?LZ最好说清楚一些,否则大家都只能是猜!
#10
只能有4个连续的1作为开头（而且只能有一次4个连续的1），没有其他要求了
#11
既然是环，就假设011110在开始，然后算其他部分不包含1111的可能情况。每种情况又可以循环左移1,2,3,...,17位.
12位二进制数最大就是 2的12次方－1。
写个程序判断从0到 2的12－1次方的每个数，如果它的二进制表示里没有连续的四个1，那它就算一个。
找出所有数的个数然后乘以17就是总的符合条件的个数。
12位二进制数最大就是 2的12次方－1。
写个程序判断从0到 2的12－1次方的每个数，如果它的二进制表示里没有连续的四个1，那它就算一个。
找出所有数的个数然后乘以17就是总的符合条件的个数。
#12
因为有且只有一个连续的 1111,
而该 1111 两边都肯定是0,
从 011110 处拆开该环并作为开头,
余下 12 位不包含 4个连续1 的排列数目就是所求.
求有效的排列数方法如下:
用包含4个状态(顶点)的图,
0 1 2 3
--------
0| 1 1 1 1
1| 1 0 0 0
2| 0 1 0 0
3| 0 0 1 0
状态0-3表示目前已走过多少过连续的 1,
图中 (i,j)元素为 1 表示可从状态 j 转到状态 i(即有j->i的有向边).
比如 (0,2)为 1, 表示之前的排列为 011-, -为0时则可转到状态 0.
初始时在状态0, 则解答就是走了 12 步后所有可能的路径条数.
设列向量 ti=(ni0, ni1, ni2, ni3) 表示走了i步后,
落在各个状态的路径条数,
则解答就是 n12-0 + n12-2 + n12-2 + n12-3.
设上述图的矩阵为 M,
而 t(i+1) = M * ti
t0 = (1, 0, 0, 0)
所以 t12 = M^12 * t0
利用矩阵运算可轻松求出结果.
这道题目即使手算也很轻松,
t0=(1,0,0,0)
递推规则:
n(i+1)0 = ni0 + ni1 + ni2 + ni3
n(i+1)1 = ni0
n(i+1)2 = ni1
n(i+1)3 = ni2
最后我算出是 2200 种(不知有无错~~)
而该 1111 两边都肯定是0,
从 011110 处拆开该环并作为开头,
余下 12 位不包含 4个连续1 的排列数目就是所求.
求有效的排列数方法如下:
用包含4个状态(顶点)的图,
0 1 2 3
--------
0| 1 1 1 1
1| 1 0 0 0
2| 0 1 0 0
3| 0 0 1 0
状态0-3表示目前已走过多少过连续的 1,
图中 (i,j)元素为 1 表示可从状态 j 转到状态 i(即有j->i的有向边).
比如 (0,2)为 1, 表示之前的排列为 011-, -为0时则可转到状态 0.
初始时在状态0, 则解答就是走了 12 步后所有可能的路径条数.
设列向量 ti=(ni0, ni1, ni2, ni3) 表示走了i步后,
落在各个状态的路径条数,
则解答就是 n12-0 + n12-2 + n12-2 + n12-3.
设上述图的矩阵为 M,
而 t(i+1) = M * ti
t0 = (1, 0, 0, 0)
所以 t12 = M^12 * t0
利用矩阵运算可轻松求出结果.
这道题目即使手算也很轻松,
t0=(1,0,0,0)
递推规则:
n(i+1)0 = ni0 + ni1 + ni2 + ni3
n(i+1)1 = ni0
n(i+1)2 = ni1
n(i+1)3 = ni2
最后我算出是 2200 种(不知有无错~~)
#13
dengsf :
很感谢，感觉你的算法是对的，图论功底比较深厚。
还麻烦一下，如果是使用连续的3个1作为开头呢？这种组合会不会比连续的4个1少呢？
很感谢，感觉你的算法是对的，图论功底比较深厚。
还麻烦一下，如果是使用连续的3个1作为开头呢？这种组合会不会比连续的4个1少呢？
#14
我试着用Pari/Gp计算一下,应该是2872.
从另外一个方面,我们也可以先解出矩阵的特征多项式
结果为 x^4 - x^3 - x^2 - x - 1
从这里可以看出,这个数列的递推式为a(n+4)=a(n+3)+a(n+2)+a(n+1)+a(n),就是所谓的广义菲波那挈数列
而前四项为a(0)=1,a(1)=2,a(2)=4,a(3)=8,
于是我们根据 我的一个结论可以得到其通项公式为
round(s*r^(n+2)),
其中s=r^(-1)(r-1)/(10*r-8),
r为方程x^4-x^3-x^2-x-1=0的唯一的正实数根.
其中r~=1.927561975482925304261905862,s~=-1.328611428962112567203246619
比如对于这个题目,n=12,所以结果为
round(-1.328611428962112567203246619*1.927561975482925304261905862^14)=round(2872.023620480750834593275145)=2872.
从另外一个方面,我们也可以先解出矩阵的特征多项式
结果为 x^4 - x^3 - x^2 - x - 1
从这里可以看出,这个数列的递推式为a(n+4)=a(n+3)+a(n+2)+a(n+1)+a(n),就是所谓的广义菲波那挈数列
而前四项为a(0)=1,a(1)=2,a(2)=4,a(3)=8,
于是我们根据 我的一个结论可以得到其通项公式为
round(s*r^(n+2)),
其中s=r^(-1)(r-1)/(10*r-8),
r为方程x^4-x^3-x^2-x-1=0的唯一的正实数根.
其中r~=1.927561975482925304261905862,s~=-1.328611428962112567203246619
比如对于这个题目,n=12,所以结果为
round(-1.328611428962112567203246619*1.927561975482925304261905862^14)=round(2872.023620480750834593275145)=2872.
#15
同样,如果换成3个1作为开头,那么我们只需要将四阶广义菲波那挈数列换成三阶的就可以了
于是通项公式变成
round(s*r^(n+2)),其中s=r^(-1)(r-1)/(4*r-6)
其中r为x^3-x^2-x-1=0的正实数根,即1.839286755214161132551852565
而s~=0.3362281169949410942253629537,
所以通项为round(s*r^(n+2))
而这是n=13,所以结果为round(0.3362281169949410942253629537*1.839286755214161132551852565^15)=round(3135.997304035243766542589073)=3136.
也就是结果更加多.
于是通项公式变成
round(s*r^(n+2)),其中s=r^(-1)(r-1)/(4*r-6)
其中r为x^3-x^2-x-1=0的正实数根,即1.839286755214161132551852565
而s~=0.3362281169949410942253629537,
所以通项为round(s*r^(n+2))
而这是n=13,所以结果为round(0.3362281169949410942253629537*1.839286755214161132551852565^15)=round(3135.997304035243766542589073)=3136.
也就是结果更加多.
#16
14楼贴错了两处
一个是
s=r^(-1)(r-1)/(5*r-8),
另一个是
s~=0.2938130627736427370192323321
一个是
s=r^(-1)(r-1)/(5*r-8),
另一个是
s~=0.2938130627736427370192323321
#17
mathe :辛苦了，我先看看。
#1
LZ的意思是18位的2进制编码中,包括4个连续的1的编码有多少种么?(连续5个的不算对么?)
#2
还是编程算吧。数学上太难 根据题意必定包含仅包含一个011110
可以用三个字节从0开始一直加1 每次进行判定.
要不用 bitset 不过还要考虑到环的问题 写起来真麻烦.
可以用三个字节从0开始一直加1 每次进行判定.
要不用 bitset 不过还要考虑到环的问题 写起来真麻烦.
#3
帮顶一下
#4
我试了一下,不知道对不对:
必定包含仅包含一个011110的组合 = 包含011110的组合 - 包含011110但至少还有另外一个1111的组合
包含011110的组合: = 18 * 2^12 - 重复数
重复数指的譬如01111001111000000,1-6的六位数和7-12的六位数是同一组合.
包含011110但至少还有另外一个1111的组合: = 18 * 8 * 2^8 - 重复数
因为重复数在必定包含仅包含一个011110的组合不存在,所以上面两个重复数必然相等.
===> 必定包含仅包含一个011110的组合 = 18 * 2^12 - 18 * 8 * 2^8 = 18 * 2^11
必定包含仅包含一个011110的组合 = 包含011110的组合 - 包含011110但至少还有另外一个1111的组合
包含011110的组合: = 18 * 2^12 - 重复数
重复数指的譬如01111001111000000,1-6的六位数和7-12的六位数是同一组合.
包含011110但至少还有另外一个1111的组合: = 18 * 8 * 2^8 - 重复数
因为重复数在必定包含仅包含一个011110的组合不存在,所以上面两个重复数必然相等.
===> 必定包含仅包含一个011110的组合 = 18 * 2^12 - 18 * 8 * 2^8 = 18 * 2^11
#5
用程序算了一个51016, 规则是最长连续4个1,并且只有1个4个1的串,剩下可以有连续3个的。
不知道是否满足LZ的要求。
不知道是否满足LZ的要求。
#6
donkey301的看来有道理
#7
能编程产生合乎要求的随机数吗？用程序实现产生要求的随机数才是最终目的
#8
如果我是必须要4个1开头呢？主要是要用4个1作为同步，做一个环形条码。
#9
除了4个1开头之外,有什么其他的要求么?LZ最好说清楚一些,否则大家都只能是猜!
#10
只能有4个连续的1作为开头（而且只能有一次4个连续的1），没有其他要求了
#11
既然是环，就假设011110在开始，然后算其他部分不包含1111的可能情况。每种情况又可以循环左移1,2,3,...,17位.
12位二进制数最大就是 2的12次方－1。
写个程序判断从0到 2的12－1次方的每个数，如果它的二进制表示里没有连续的四个1，那它就算一个。
找出所有数的个数然后乘以17就是总的符合条件的个数。
12位二进制数最大就是 2的12次方－1。
写个程序判断从0到 2的12－1次方的每个数，如果它的二进制表示里没有连续的四个1，那它就算一个。
找出所有数的个数然后乘以17就是总的符合条件的个数。
#12
因为有且只有一个连续的 1111,
而该 1111 两边都肯定是0,
从 011110 处拆开该环并作为开头,
余下 12 位不包含 4个连续1 的排列数目就是所求.
求有效的排列数方法如下:
用包含4个状态(顶点)的图,
0 1 2 3
--------
0| 1 1 1 1
1| 1 0 0 0
2| 0 1 0 0
3| 0 0 1 0
状态0-3表示目前已走过多少过连续的 1,
图中 (i,j)元素为 1 表示可从状态 j 转到状态 i(即有j->i的有向边).
比如 (0,2)为 1, 表示之前的排列为 011-, -为0时则可转到状态 0.
初始时在状态0, 则解答就是走了 12 步后所有可能的路径条数.
设列向量 ti=(ni0, ni1, ni2, ni3) 表示走了i步后,
落在各个状态的路径条数,
则解答就是 n12-0 + n12-2 + n12-2 + n12-3.
设上述图的矩阵为 M,
而 t(i+1) = M * ti
t0 = (1, 0, 0, 0)
所以 t12 = M^12 * t0
利用矩阵运算可轻松求出结果.
这道题目即使手算也很轻松,
t0=(1,0,0,0)
递推规则:
n(i+1)0 = ni0 + ni1 + ni2 + ni3
n(i+1)1 = ni0
n(i+1)2 = ni1
n(i+1)3 = ni2
最后我算出是 2200 种(不知有无错~~)
而该 1111 两边都肯定是0,
从 011110 处拆开该环并作为开头,
余下 12 位不包含 4个连续1 的排列数目就是所求.
求有效的排列数方法如下:
用包含4个状态(顶点)的图,
0 1 2 3
--------
0| 1 1 1 1
1| 1 0 0 0
2| 0 1 0 0
3| 0 0 1 0
状态0-3表示目前已走过多少过连续的 1,
图中 (i,j)元素为 1 表示可从状态 j 转到状态 i(即有j->i的有向边).
比如 (0,2)为 1, 表示之前的排列为 011-, -为0时则可转到状态 0.
初始时在状态0, 则解答就是走了 12 步后所有可能的路径条数.
设列向量 ti=(ni0, ni1, ni2, ni3) 表示走了i步后,
落在各个状态的路径条数,
则解答就是 n12-0 + n12-2 + n12-2 + n12-3.
设上述图的矩阵为 M,
而 t(i+1) = M * ti
t0 = (1, 0, 0, 0)
所以 t12 = M^12 * t0
利用矩阵运算可轻松求出结果.
这道题目即使手算也很轻松,
t0=(1,0,0,0)
递推规则:
n(i+1)0 = ni0 + ni1 + ni2 + ni3
n(i+1)1 = ni0
n(i+1)2 = ni1
n(i+1)3 = ni2
最后我算出是 2200 种(不知有无错~~)
#13
dengsf :
很感谢，感觉你的算法是对的，图论功底比较深厚。
还麻烦一下，如果是使用连续的3个1作为开头呢？这种组合会不会比连续的4个1少呢？
很感谢，感觉你的算法是对的，图论功底比较深厚。
还麻烦一下，如果是使用连续的3个1作为开头呢？这种组合会不会比连续的4个1少呢？
#14
我试着用Pari/Gp计算一下,应该是2872.
从另外一个方面,我们也可以先解出矩阵的特征多项式
结果为 x^4 - x^3 - x^2 - x - 1
从这里可以看出,这个数列的递推式为a(n+4)=a(n+3)+a(n+2)+a(n+1)+a(n),就是所谓的广义菲波那挈数列
而前四项为a(0)=1,a(1)=2,a(2)=4,a(3)=8,
于是我们根据 我的一个结论可以得到其通项公式为
round(s*r^(n+2)),
其中s=r^(-1)(r-1)/(10*r-8),
r为方程x^4-x^3-x^2-x-1=0的唯一的正实数根.
其中r~=1.927561975482925304261905862,s~=-1.328611428962112567203246619
比如对于这个题目,n=12,所以结果为
round(-1.328611428962112567203246619*1.927561975482925304261905862^14)=round(2872.023620480750834593275145)=2872.
从另外一个方面,我们也可以先解出矩阵的特征多项式
结果为 x^4 - x^3 - x^2 - x - 1
从这里可以看出,这个数列的递推式为a(n+4)=a(n+3)+a(n+2)+a(n+1)+a(n),就是所谓的广义菲波那挈数列
而前四项为a(0)=1,a(1)=2,a(2)=4,a(3)=8,
于是我们根据 我的一个结论可以得到其通项公式为
round(s*r^(n+2)),
其中s=r^(-1)(r-1)/(10*r-8),
r为方程x^4-x^3-x^2-x-1=0的唯一的正实数根.
其中r~=1.927561975482925304261905862,s~=-1.328611428962112567203246619
比如对于这个题目,n=12,所以结果为
round(-1.328611428962112567203246619*1.927561975482925304261905862^14)=round(2872.023620480750834593275145)=2872.
#15
同样,如果换成3个1作为开头,那么我们只需要将四阶广义菲波那挈数列换成三阶的就可以了
于是通项公式变成
round(s*r^(n+2)),其中s=r^(-1)(r-1)/(4*r-6)
其中r为x^3-x^2-x-1=0的正实数根,即1.839286755214161132551852565
而s~=0.3362281169949410942253629537,
所以通项为round(s*r^(n+2))
而这是n=13,所以结果为round(0.3362281169949410942253629537*1.839286755214161132551852565^15)=round(3135.997304035243766542589073)=3136.
也就是结果更加多.
于是通项公式变成
round(s*r^(n+2)),其中s=r^(-1)(r-1)/(4*r-6)
其中r为x^3-x^2-x-1=0的正实数根,即1.839286755214161132551852565
而s~=0.3362281169949410942253629537,
所以通项为round(s*r^(n+2))
而这是n=13,所以结果为round(0.3362281169949410942253629537*1.839286755214161132551852565^15)=round(3135.997304035243766542589073)=3136.
也就是结果更加多.
#16
14楼贴错了两处
一个是
s=r^(-1)(r-1)/(5*r-8),
另一个是
s~=0.2938130627736427370192323321
一个是
s=r^(-1)(r-1)/(5*r-8),
另一个是
s~=0.2938130627736427370192323321
#17
mathe :辛苦了，我先看看。