[組合] 題目釋義: run

看板Math作者 (僕は美味しいです)時間10年前 (2015/10/04 16:14), 編輯推噓5(5推 0噓 14→)
留言19則, 7人參與, 最新討論串1/2 (看更多)
Consider (m+n)-words with exactly m 1's and n 0's. Count the number of these words with exactly k runs, where a run is a maximal subsequence of consecutive 1's. Example: 1011100110 has 3 runs. 我只能說作者給的例子實在不好orz， 讓我看不懂 3 runs 指的是有(1)(111)(11)共3個runs 還是因為最大的(111)有3個1所以叫 3 runs?? 請問 1010101 是 4 runs 對嗎? 1101101111 是 3 runs 對嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.44.20.235 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1443946465.A.2E2.html
推
10/04 16:32, , 1F
是指各個相鄰1片段中最多相鄰的數目,舉例是1,4runs
10/04 16:32, 1F
→
10/04 16:33, , 2F
maximal
10/04 16:33, 2F
推
10/04 16:35, , 3F
"一個run是一個極大的連續都是1的子序列"
10/04 16:35, 3F
→
10/04 16:37, , 4F
我的語文能力太弱了，看不懂以上三位的解釋orz
10/04 16:37, 4F
→
10/04 16:38, , 5F
可以告訴我我舉的那兩個例子各是幾runs嗎，感恩
10/04 16:38, 5F
→
10/04 17:26, , 6F
連續出現最多1的次數 所以舉例分別是1 4
10/04 17:26, 6F
→
10/04 17:47, , 7F
我的理解跟原PO一樣,(1)(1)(1)(1) 4 個 runs
10/04 17:47, 7F
→
10/04 17:48, , 8F
(11)(11)(1111) 三個 runs
10/04 17:48, 8F
→
10/04 17:55, , 9F
照樓上的說法，題目不該用 maximal應該用number吧？
10/04 17:55, 9F
推
10/04 18:05, , 10F
maximum subsequence of consecutive 1
10/04 18:05, 10F
→
10/04 18:06, , 11F
直翻是三樓那樣, 那個"極大"的意思是找不到以它為
10/04 18:06, 11F
→
10/04 18:06, , 12F
一部份而更長的序列, 在此即是這一串兩邊都不是 1
10/04 18:06, 12F
→
10/04 18:07, , 13F
這樣的一個序列叫一個 run
10/04 18:07, 13F
推
10/04 18:07, , 14F
沒錯, 就是 LPH 大說的這樣
10/04 18:07, 14F
→
10/04 18:09, , 15F
如你的第二例, 取中間 1 個 1 不是極大, 因為能延伸
10/04 18:09, 15F
→
10/04 18:10, , 16F
若取中間兩個 0 之間的 11 則它不能延伸了
10/04 18:10, 16F
→
10/04 18:10, , 17F
這樣子就是一個 run
10/04 18:10, 17F
→
10/04 18:18, , 18F
感謝以上各位
10/04 18:18, 18F
推
10/04 22:42, , 19F
這不是組合學的題目嗎XD
10/04 22:42, 19F
‣ 更多 LeonYo 的文章
文章代碼(AID): #1M4D_XBY (Math)
‣ 更多 LeonYo 的文章
文章代碼(AID): #1M4D_XBY (Math)