概率問題 NO.2
|
|
| 香港三國志 · 版規 |
 說明
 搜尋
 會員
 聲望
 日曆
 統計
|
| 歡迎訪客 ( 登入 | 註冊 ) | 重寄認證電子郵件 |
   |
概率問題 NO.2| 阿暪 |
發表於： Jul 27 2006, 14:09
|
 一品官  發表數： 5,279 所屬群組： 一般 註冊日期： 8-17-2004 活躍：16 聲望：1208  |
這次的問題應該比上次哪個容易, 只要想得清楚的話, 應該讀過F.3 F.5 數學是有可能答到的.
只是....可能需要一點電腦知識, (或許我一會兒寫一個較易理解的題目吧...) 假如現在有一個 40kB 的檔案. (讓問題更清晰, 就假設它是準準確確不多不少 40kB吧) 我現在 HEXEDIT 它 (16進制編輯??), 我用replace all 把這檔案裏的 "01 02 03 04 05" 的五Byte 串 replace 為 "06 07 08 09 0A" (其實replace 做甚麼是沒有影響的), 如果我實際想replace的 "01 02 03 04 05" 串 在該檔案裏只出現 3 次, 而這三個 "01 02 03 04 05" 串 在檔案裏相隔足夠遠. (解釋一下: 我想取代的 "01 02 03 04 05" 在該檔案裏表達某資料, 所以我要把所有代表該資料的"01 02 03 04 05 " 取代為另一個串, 但一個檔案裏也有可能因巧合而出現並不是代表該資料的 "01 02 03 04 05" 組合) 那麼, 有其他"01 02 03 04 05"因純粹巧合而被 replace 的機會是多少? ......好像問得很不清楚........  _____________________________________________________ 試試形象化一點來說, 如果我要把孖寶遊戲裏的所有「MARIO」字眼改為「PEACH」, 那我便會用replace all 把所有 "16 0A 1B 12 18" 取代為 "19 0E 0A 0C 11", 但那遊戲檔裏可能有其他不代表「MARIO」 字眼的地方因巧合而出現"16 0A 1B 12 18" 組合, (例如圖像資料, 或關卡資料), 那replace all 便會把那些不代表「MARIO」 字眼的地方都一併改了. 本篇文章已被 阿暪 於 Jul 27 2006, 14:17 編輯過 附帶圖片 ) -------------------- 暗淡了刀光劍影，遠去了鼓角錚鳴
眼前飛揚著一個個鮮活的面容 湮沒了黃塵古道，荒蕪了烽火邊城 歲月啊！你帶不走那一串串熟悉的姓名 興亡誰人定啊！盛衰豈無憑啊！ 一頁風雲散啊...變幻了時空 聚散皆是緣啊！離合總關情啊！ 擔當生前事啊...何計身後評？ 長江有意化作淚，長江有情起歌聲 歷史的天空，閃爍幾顆星 人間一股英雄氣... 在馳騁縱橫... |
 
|
| 阿暪 |
發表於： Jul 27 2006, 14:36
|
|
一品官 發表數： 5,279 所屬群組： 一般 註冊日期： 8-17-2004 活躍：16 聲望：1208 |
試試把題目比喻為:
如果在一個 40kB 的文字檔(每個字母用 1 Byte), 我想把所有"found" 字改為"abcde", 於是用replace all , 但這樣可能會把一些原本不是指"found" 字的字串都一起改掉, 例如: "I found thte foundation of the building." 那麼用 replace all, 就會把 "foundation" 也改為 "abcdeation". 那麼, 當我用replace all , 我會誤把1個或以上 不是 "found" 單字的"found" 字串取代的機會是多少? 為了配合原本問題, 和把問題簡化, 有以下兩個極不合理的假設: 1. 假設該文字檔中的字目是完全隨機排列. 每個字母出現的機率一樣. (甚麼"e字母出得特別多", "英文文法" 就不用想了) 2. 該文字檔裏有256種字母. (那是ASCII 的所有符號都會出現了......) -------------------- 暗淡了刀光劍影，遠去了鼓角錚鳴
眼前飛揚著一個個鮮活的面容 湮沒了黃塵古道，荒蕪了烽火邊城 歲月啊！你帶不走那一串串熟悉的姓名 興亡誰人定啊！盛衰豈無憑啊！ 一頁風雲散啊...變幻了時空 聚散皆是緣啊！離合總關情啊！ 擔當生前事啊...何計身後評？ 長江有意化作淚，長江有情起歌聲 歷史的天空，閃爍幾顆星 人間一股英雄氣... 在馳騁縱橫... |
|
|
| Superdog |
發表於： Jul 27 2006, 15:44
|
 八品官 發表數： 256 所屬群組： 一般 註冊日期： 4-01-2005 活躍：3 聲望：40 |
只要逐一找出16、0A、1B、12、18這五個值的出現概率(出現頻率/總字節數)，就不必假設各值的出現概率完全隨機，而只需它們假設出現後是隨機分布就好了。
挑戰性問題：這樣做(在計算中考慮到各值的出現概率)，相比起既不考慮出現概率也不考慮分布概率的計算方式，能否保證計算出來的答案更接近實際的概率值？  p.s. 阿瞞你可能要補充些定義...... 1024 bytes (2^10): This definition is always used to express memory capacity, and other quantities which are based on powers of two. Most software also uses it to express storage capacity. This definition has been expressly forbidden by the SI standard (section 3.1, marginal note), and most standards organizations instead recommend the term kibibyte (KiB). Although the word "kibibyte" is seldom seen in practice, it is starting to be adopted by software in which precision is important, such as BitTorrent or the Linux kernel. 1000 bytes (10^3): This definition is consistent with the SI prefix, and is recommended for all uses by international standards organizations such as IEC, IEEE, and ISO, with the abbreviation "kB". The overwhelming popularity of the 1024 definition means that anyone using "kilobyte" to mean 1000 in these situations is likely to cause confusion. However, it is common to use 1000 when deriving kilobyte measures from quantities which are not based on powers of two, such as clock speeds or bitrates.  本篇文章已被 徐元直 於 Jul 28 2006, 17:34 編輯過 --------------------  |
|
|
| 阿暪 |
發表於： Jul 28 2006, 15:25
|
||
|
一品官 發表數： 5,279 所屬群組： 一般 註冊日期： 8-17-2004 活躍：16 聲望：1208 |
這是指, 先找出檔案裏實際上 這5個值出現了的次數, 然後才計算他們連在一起的機會? 馬聚 眼看來應該會較接近實際概率值, 但現在未想清楚不感肯定, 可能那五個值的出現概率會影響準確度? 現在我傾向於認為這能夠保證計算出來的答案更接近實際的概率值. __________________________________________________________ 如果用找出的5個值各自概率, 取代5 個 1/256 來計算巧合出現"16 0A 1B 12 18"串的機會, 那我還懂得計, 但如果要用那5個值的出現總數來分析他們的分佈, 計算出現"16 0A 1B 12 18"串的概率 (這概率可以視為「實際的概率值」吧.), 那就真的考起我了. ___________________________________________________________ 其實我沒有說kB用1024還是1000是因為我想看看大家會用哪個 既然說了, kB 就用1024 吧. 本篇文章已被 阿暪 於 Jul 28 2006, 15:45 編輯過 -------------------- 暗淡了刀光劍影，遠去了鼓角錚鳴
眼前飛揚著一個個鮮活的面容 湮沒了黃塵古道，荒蕪了烽火邊城 歲月啊！你帶不走那一串串熟悉的姓名 興亡誰人定啊！盛衰豈無憑啊！ 一頁風雲散啊...變幻了時空 聚散皆是緣啊！離合總關情啊！ 擔當生前事啊...何計身後評？ 長江有意化作淚，長江有情起歌聲 歷史的天空，閃爍幾顆星 人間一股英雄氣... 在馳騁縱橫... |
||
|
|
| 阿暪 |
發表於： Aug 5 2006, 03:34
|
|
一品官 發表數： 5,279 所屬群組： 一般 註冊日期： 8-17-2004 活躍：16 聲望：1208 |
(我的)答案:
(先說沒有元直談到的數值出現頻率) 該檔案裏的 5 Byte 字串 總數 = 40 x 1024 - 4 = 40956 (知不知道 - 4 是甚麼?) 可以被誤換的字串 = 40956 - 9 x 3 = 40929 (知不知道 9 x 3 是甚麼?) 一個字串因巧合而被誤換的機會 = (1/256) ^ 5 有字串被誤換的機會 = 1 - { [1 - (1/256) ^ 5] ^ 40929 } = 3.72247 x 10^ -8 (根據小算盤) 或者 binomial expansion approx. = 1 - (1 - 40929 / 256^5) = 3.72247 x 10^ -8 所以, 基於之前假設, 機會是非常小, 大概不會被誤換. (如果有該5個數值出現頻率, 那麼 (1/256)^5 則應該換為 該5個概率乘起來) 本篇文章已被 阿暪 於 Aug 5 2006, 03:38 編輯過 -------------------- 暗淡了刀光劍影，遠去了鼓角錚鳴
眼前飛揚著一個個鮮活的面容 湮沒了黃塵古道，荒蕪了烽火邊城 歲月啊！你帶不走那一串串熟悉的姓名 興亡誰人定啊！盛衰豈無憑啊！ 一頁風雲散啊...變幻了時空 聚散皆是緣啊！離合總關情啊！ 擔當生前事啊...何計身後評？ 長江有意化作淚，長江有情起歌聲 歷史的天空，閃爍幾顆星 人間一股英雄氣... 在馳騁縱橫... |
|
|
| 徐元直 |
發表於： Aug 5 2006, 03:58
|
 攤抖首領 發表數： 7,913 所屬群組： 君主 註冊日期： 9-18-2003 活躍：59 聲望：4176 |
自問自答其樂無窮 XD
-------------------- ......
|
|
|
| 阿暪 |
發表於： Aug 6 2006, 02:56
|
|
一品官 發表數： 5,279 所屬群組： 一般 註冊日期： 8-17-2004 活躍：16 聲望：1208 |
從前問這類問題還有不少人來答, 但近來似乎沒有多少人有興趣, 難道因為暑假大家都不想理這些問題?
-------------------- 暗淡了刀光劍影，遠去了鼓角錚鳴
眼前飛揚著一個個鮮活的面容 湮沒了黃塵古道，荒蕪了烽火邊城 歲月啊！你帶不走那一串串熟悉的姓名 興亡誰人定啊！盛衰豈無憑啊！ 一頁風雲散啊...變幻了時空 聚散皆是緣啊！離合總關情啊！ 擔當生前事啊...何計身後評？ 長江有意化作淚，長江有情起歌聲 歷史的天空，閃爍幾顆星 人間一股英雄氣... 在馳騁縱橫... |
|
|
| 黃巾小賊 |
發表於： Aug 6 2006, 06:34
|
||
 芻狗 發表數： 4,555 所屬群組： 軍團長 註冊日期： 3-02-2005 活躍：12 聲望：557 |
這個你最好問問長恭。  不過這題目不吸引之處似乎是問題難懂，和醫院生仔或更早的班次到站相比，不夠日常生活，所以就毫無趣味兼且看似很專業的範疇。雖然你說所需知識不高，但一般人可能沒有去了解問題的興趣。 本篇文章已被 黃巾小賊 於 Aug 6 2006, 06:36 編輯過 -------------------- 板友Leaf：「黃巾賊本來都和你我一樣是小市民一個，對一個小賊來說，當黃巾賊可能是餓死之外的惟一選擇......」
魯迅：「人民處於官兵與強盜之間，不論被裹從或自願參加，都是拿兩面旗；賊來了從賊，官來了從官。」 板友呂遜：「不論是出於孝心還是貪心，偷就是不對，偷就是賊。」 孔子：「老而不死，是為賊。」 |
||
|
1 位使用者正在閱讀本主題 (1 位訪客及 0 位匿名使用者)
0 位會員：
 |
|
[ Script Execution time: 0.0381 ] [ 12 queries used ] [ GZIP 啟用 ]