[回到版面]
回應模式
名 稱
E-mail
標 題
內 文
附加圖檔[] []
類別標籤(請以 , 逗號分隔多個標籤)
刪除用密碼(刪除文章用。英數字8字元以內)
附加選項[動態GIF]
  • 可附加圖檔類型:GIF, JPG, JPEG, PNG,禁止發佈色情及獵奇圖片
  • 附加圖檔最大上傳資料量為 750 KB。當回文時E-mail填入sage為不推文功能
  • 各類學術相關話題均可在此發表, 但是自己的功課要自己做
  • 新討論串必須輸入相對應之標題, 推文字數限制為五十字
  • 本版內容不能視為專業醫療建議, 醫療相關問題請諮詢專業醫護人員
  • 違規事項及管理意見請向此管理室回報

檔名:1512102054610.jpg-(156 KB, 1080x1080) [以預覽圖顯示]
156 KBLego 數學題 名稱: 無名氏 [17/12/01(五)12:20 ID:Ys.q8NFA] No.187753 2推 +   
有數學家或工程師計得出嗎?
無名氏: 9億的話寫程式硬爆應該有機會 (4mgLNnEs 17/12/01 18:10)
無名氏: 如果要儲存全部的組合要20G記憶體...也不算不可能。不過還是想個更好的方法來檢查重複似乎比較好 (4mgLNnEs 17/12/01 18:19)
給後人一點參考 名稱: 無名氏 [17/12/02(六)00:58 ID:CiU7uQPo] No.187754 11推 +    
這個題目有點模糊
我們先定義幾個基本假設

1.全部的樂高都是凸面向上來進行討論,不橫放、不考慮有些樂高的Z軸方向與別人不同的情況
2.所有的樂高都必須位在整數個點的位置,不考慮放半格的情況
3.Z軸角度(XY平面上的角度)只有縱橫兩種可能,不考慮斜擺
4.兩塊樂高能結合的條件是:長或寬有一邊以上被凸點填滿。不符合此條件的都視為組合不穩而不算、符合條件的都假設他接合力足夠不會倒塌
簡單來說,只考慮邏輯簡單、能用XYZ座標空間描述的組合方式,不考慮任何創意手法


兩塊樂高組合時,在X或Y軸最多差三格凸點
六塊如果用最極限的方式組成一條斜線,頭尾的X或Y軸最多差15格

所以我定義一個XY軸16*16格、Z軸6格的空間來隨意擺入六個樂高
可以把所有符合基本假設的組合通通包含在內
再乘上每個樂高可以有縱或橫兩種角度
在這個空間中,不分組合是否成立的擺法,一共有(16*16*6*2)^6種
這個數字等於2^60*3^6=840479776858391445504≒ 8.4*10^20


接著我們使用資工領域常用的蒙地卡羅法
隨機從上面8.4*10^20個組合裡挑幾個組合出來,看他是不是合乎條件的組法
當採樣數量夠大時,上述採樣的成功機率會接近整個母體裡的合法組法的比例
再用這個比例乘上總數就可以估計總共有幾個合法組法

在採樣前,要先估算一下我們需要採多少樣品數字才夠可信
總共有20次方,原PO說答案在8次方
所以平均要跑10^12個樣本才會有一個成功案例...


幹你娘,這什麼爛數字
不算了不算了
無名氏: (〃∀〃)你這傲嬌 (PdxgJXZk 17/12/02 04:10)
無名氏: 感覺有點像圍棋 說好必勝計算量是10^600以上 但逼死人類只要下效率棋就夠了 (Oy7AEjwY 17/12/02 12:23)
無名氏: 若用遞歸法,逐方塊放置上去,可以排除掉很多佔了同一空間和上下沒有併合的情況 (XzETTe0Q 17/12/02 17:30)
無名氏: 數一數,放第二塊時不扣除對稱有46種放法,再放其餘就當有2, 3, 4, 5倍的放法好了,這樣一共 (XzETTe0Q 17/12/02 17:37)
無名氏: 啊上面不是46是92 // 這樣一共92^5*5!約八千億種。放第二塊時扣掉對稱就能砍一小半 (XzETTe0Q 17/12/02 17:44)
無名氏: 四千億之數較於4GHz的CPU,約一秒週期數的百倍。如每回遞歸能花一千週期以內,還是有望一天內算完 (XzETTe0Q 17/12/02 17:59)
無名氏: 稍微估個低一點的上限,pi{i=1~6}(64*i),等於4.9*10^13 (OGBaAo1o 17/12/15 21:47)
無名氏: 用branching factor估的 (OGBaAo1o 17/12/15 21:47)
無名氏: 後來又想想應該只要1~5,但又想到忘記上下都可以組所以每層都要乘以二 (1Iz6YWm6 17/12/16 19:05)
無名氏: 所以應該是pi{i=1~5}(64*i*2)=4.12*10^12,稍微少了點 (1Iz6YWm6 17/12/16 19:06)
無名氏: 靠北,現在才看到樓上已經有估一個更短的了(死 (T2VlKLH2 17/12/17 03:35)

【刪除文章】[]
刪除用密碼: