m4tonyadd

庫爾德語翻譯前陣子在python版看到有人接頭到這個昔時煞到萬國翻譯公司的遊戲， 一下子熱血舊夢又被重燃... 萬國翻譯公司還算有能利巴我手上的想法用C弄出來， 幾個程式設計相幹的板這裡也算是人氣較旺， 來這裡搞搞看有無人願意一路來玩玩瘋瘋 ------------------以上前情提綱，只是說明這絕對不是功課文----------------- 幾A幾B猜數字遊戲，略述如下: 兩小我玩，一方出數字，一方猜翻譯出數字的人要先想好一個沒有反複數字的4位數，不克不及 讓猜的人知道。猜的人就能夠開始猜。每猜一個數，出數者就要按照這個數字給出幾A幾 B，個中A前面的數字默示位置正確的數的個數，而B前的數字默示數字准確而位置舛錯的 數的個數。 如正確謎底為5234，而猜的人猜5346，則是1A2B，其中有一個5的位置對了，記為1A，而 3和4這兩個數字對了，而位置沒對，是以記為2B，合起來就是1A2B翻譯 如果不清晰劃定規矩的可以看wiki: http://goo.gl/FvfLq，或google 這個遊戲在網路上找到已有人對其解法的幾個最好化方向做過研究，一些事實: 1. worst case能包管幾次內猜到: 已證實為7次 (不可能6次) 2. 在所有正當的5040種可能性中worst case出現次數起碼: <=50次 (疑似open) 3. 最短能包管平均幾回猜到: 已證實為約5.2131次 4. 還沒有有人用暴力窮舉的體式格局跑完所有可能性過 (至少我沒查到) 5. 上述1、3有最少三種分歧(非對稱等價)的演算法能同時達到 6. "刪除不成能，從剩餘中隨機猜"這個算法平均約5.47次，worst case極可能是10 那麼，我還想從這個被研究爛了的問題中搞什麼? 固然是個很直覺、很該問，而又沒有在所有被找到的研究中看到過的問題 首先萬國翻譯公司們來察看上面第五點提到的這三種演算法 (詳見 http://goo.gl/rbXc4 第15頁) Strategy Name 1 2 3 4 5 6 7 8 Total ------------------------------------------------------------------------ Fast Strategy 1 7 62 718 2403 1757 92 26274 Slow Strategy 1 7 61 692 2445 1755 79 26274 Tanaka‘s Result 1 7 63 697 2424 1774 74 26274 ----------------------------------------------------------------------- 如上表，對於合法的5040種謎底，第一種演算法能把其中718種在第四次猜出來 而這三種演算法都能拿到平均26274 / 5040 = 5.2131的平均次數 並且從次數分派表可以看出他們是明顯是分歧的，不具有對稱等價關係 他們三者之間有什麼主要的分歧嗎? 有!!! 三個人拿著這三種"最好化"演算法相互對戰，誰會占優? 推行出去一概而論的話，這個問題夠直覺、夠該問吧 以下解釋若何比力兩種演算法對戰的好壞關係 (以下假定演算法非隨機) 假設一個演算法能包管N次內猜出，且恰好在第k次料中的機率為f(k)， (則: sum = 0.0; for (i=1;i<=N;i++) sum += f(i); 顯然有sum == 100%的關係) 對於兩種演算法各自的分派f1翻譯社 f2而言，在面臨面的對戰中， 第一種演算法勝出的機率是下面算出的sum sum = 0.0; for (i=1;i<=N1;i++) for (j=i+1;j<=N2;j++) sum += f1(i) * f2(j) 而兩種演算法平局的機率是 sum = 0.0; for (i=1;i<=min(N1, N2);i++) sum += f1(i) * f2(i) 由這樣的闡明，套入這三種演算法的次數分配表可知第二種是最互相對克服率最高的 (若是我目下當今腦殼中對之前的計算成效印象正確的話) 由此可知，一樣worst case步數、甚至同時有一樣的平均步數的兩個演算法 彼此對戰仍有高下，就更不要說平均步數分歧的演算法之間了。 甚至我還可以舉出一個假想中的極端例子， 平均步數較差的演算法可能在對戰勝率上贏過勝過平均較好的 設想演算法: 有一種worst case需要999999999999999步才算出來，其他都一步秒殺 這個精力就是"贏一步是贏一把，輸一百步也是輸一把" 所以一會兒很(ㄗˋ)顯(ㄧˇ)然(ㄨㄟˊ)前面提到的直覺又主要的問題 "什麼演算法實戰勝率最高?" 仿佛變得有玩弄的空間了不是嗎? -------------------------以上是念頭、背景說明-------------------------------- 所以我想幹嗎? 我想在這裡糾各人有閒的時辰來實做本身的玩法 看看誰能提出實克服率比力厲害的算法來 現實對照由於有上面所述的評斷方式，所以不需要把人人的code放在同個平台上跑 只要各自提出自己算法的次數分配表(極可能是7個數字而已) 並附上演算法說明或程式碼給其他有樂趣的人檢討不是豪笅就可以了 斟酌到上面提到的闡發方法實務上只適用於"有肯定流程"的演算法間的比較 對於具有隨機性的算法可能會很難測出真實的機率分派表 我建議人人盡量的設計有肯定流程的算法以便交流， 若是真的非隨機不成，建議附上最少跑1000圈(每圈5040種各一次)的累計次數分派後果 為了拋磚引玉， (我這兩天會弄出最少一個C code放在這個版以契合版旨，但新手需要點時間...) 今後有空的時辰會陸續更新更好的算法 今朝手上有三個用python實作的簡單隨機算法 平均是5.36~5.48次，此中最好的誰人有worst case很可能是7次， 他的10圈成就是6, 15翻譯社 433, 4909, 22617翻譯社 20591, 1829 最爛的那個是天真的"每次從剩下可能中隨機選"， 100圈成績是94, 1301, 10871, 61687, 177337, 185799, 61590, 5253翻譯社 67翻譯社 1 視大師對搞這個流動反映若何啦， 如果反映強烈熱鬧的話萬國翻譯公司願意提供p幣(等下看萬國翻譯公司有多少XD)給最優者 總之鼓動勉勵各人一路來動腦PK殺時候，陪我瘋一瘋 再附上一個不錯的參考資料: http://bulls-cows.sourceforge.net/index.html -- 我不是學生，不是要交作業弄陳述，也不是教員或帶人做科展 我甚至不是資訊科學相關本科系身世，只是對數學、益智遊戲有點愛好 而且有點根本的寫程式能力，所以本身玩玩 想要調查我動機的不消太麻煩，台北附近可以約出來打棒球順便聊聊

文章來自: https://www.ptt.cc/bbs/C_and_CPP/M.1348247639.A.C78.html有關各國語文翻譯公證的問題歡迎諮詢萬國翻譯公司02-23690931