Re: [問題] 隨機2進位和k不連續1

[bleed1979 (十三)]

這是相關程式碼，計算下面的範例會是對的。

但仍有待驗證。

http://codepad.org/98A4dBOV
http://pastie.org/2667047

==============================================================
修改如下，文章有點長

下面的作法是一個比較不好的方法，很消耗記憶體。

n = 4, k = 2, 0.9 0.8 0.7 0.6

0000  0.1 0.2 0.3 0.4 = 0.0024
0001  0.1 0.2 0.3 0.6 = 0.0036
0010  0.1 0.2 0.7 0.4 = 0.0056
0011  -
0100  0.1 0.8 0.3 0.4 = 0.0096
0101  0.1 0.8 0.3 0.6 = 0.0144
0110  -
0111  -
1000  0.9 0.2 0.3 0.4 = 0.0216
1001  0.9 0.2 0.3 0.6 = 0.0324
1010  0.9 0.2 0.7 0.4 = 0.0504
1011  -
1100  -
1101  -
1110  -
1111  -

total 0.1400

如果從1去減的角度來看，我們算有1的可能，然後用1.00去減。

用*代表不重複的。

for 11??
1100  *
1101  *
1110  *
1111  *

for ?11?
0110  *
0111  *
1110
1111

for ??11
0011  *
0111
1011  *
1111

又n = 4, k = 1, 用*代表不重複的

for 1???
1000  *
1001  *
1010  *
1011  *
1100  *
1101  *
1110  *
1111  *

for ?1??
0100  *
0101  *
0110  *
0111  *
1100
1101
1110
1111

for ??1?
0010  *
0011  *
0110
0111
1010
1011
1110
1111

for ???1
0001  *
0011
0101  *
0111
1001
1011
1101
1111


n = 4, k = 3

for 111?
1110  *
1111  *

for ?111
0111  *
1111


n = 5, k = 2, 僅列出需要計算的。

for 11???
11000
11001
11010
11011
11100
11101
11110
11111

for ?11??
01100
01101
01110
01111

for ??11?
00110
00111
10110
10111

for ???11
00011
01011
10011

我們把
11000 鏡射 00011
11001      10011
...
...
只要跑一半就可以了，但要小心對稱而重複。

另外尚有一點是要做到什麼時候為止。

如果是n = 5, k = 1，那就做到 00100 為止。

但如果是n = 5, k = 2就很麻煩，要做到01110為止。

不曉得有沒可以驗證的測資，程式碼容後補上。



========================================
以下修正如上面所述。
========================================

f大一開始的推文應該是對的。

1.00 - (all k連續 的可能)

n = 5, k = 3

1 - [ 111??, ?111?, ??111 ] + [ 1111?, ?1111 ] - [ 11111 ]

不曉得這樣是否有洞，還請指教。




※ 引述《pigcat1315 (還是朋友?)》之銘言：
: 標題: [問題] 隨機2進位和n不連續1
: 2<=k<=n<=200
:
: n代表幾個bit k代表最多幾個連續1  且每個bit有1時機率
:
: ex:n=2 k=2   p1=0.9 p2=0.5 (機率由使用者給)
:
: 00=> 0.1*0.5       1
:
: 01=> 0.1*0.5       2
:
: 10=> 0.9*0.5       3
:
: 11=> 0.9*0.5       4
: ============================
: 取無兩個連續1  1+2+3 等於答案
:
: → firejox:那不就算連續的就好？                                    10/09 02:44

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.116.47
※ 編輯: bleed1979       來自: 114.43.116.47        (10/09 14:14)
推 ericinttu:k個不連續1 跟 k個連續1, 是有差別的.
→ bleed1979:我懂你的意思了。我想一下。
→ ericinttu:你文章內容沒錯, 但可能跟原原PO要的不一樣.
※ 編輯: bleed1979       來自: 114.43.116.47        (10/09 14:34)
推 pigcat1315:F大的想法是對的阿...問題跟你找出0 是一樣的道理阿~"~
推 pigcat1315:重點在於這樣找~要讓電腦比較2兩百次方~@@
※ 編輯: bleed1979       來自: 114.43.116.47        (10/09 20:54)
推 tropical72:bleed1979 思緒好清晰.對稱性若可,旋轉性是否也可 ??
→ tropical72:sori,旋轉性是比較麻煩的 XD
※ 編輯: bleed1979       來自: 114.43.116.47        (10/10 03:14)
推 pigcat1315:><" 要睡了再給你個分析推