Re: [中學] 數論

[Sfly (topos)]

※ 引述《Eeon (Chaotic Good)》之銘言：
: ※ 引述《lilygarfield (愛情讓我變成詩人)》之銘言：
: : 標題: [中學] 數論
: : 時間: Fri Dec 16 11:18:47 2011
: : 從
: : 1/2, 1/3, 1/4, 1/5, ..., 1/99 中
: : 挑出10個數，使之加總為 1
: : 該挑那10個數？
: : --
: : ◆ From: 140.126.180.33
: 有版友已經給出一些特解了。
: 我用幾年前組的電腦，CPU：AMD Athlon 64 X2 Dual Core 5600+ 2.91 GHz 跑了
: CPU時間（註）八小時五十分後，得到下面這些一部份的解。
(恕刪)

根據經驗 不應該跑那麼久, 也許是因為你用Mathematica的緣故吧.

我用C++也寫了一個來試試

但我加了一個條件 : 這10個數皆不能被大於 25 的質數整除 (這很容易證明)

結果1分多鐘跑完

總共 63770解, 嗯應該也不用po出來@@

最大項最小的一組是 24 20 18 15 12 10 9 8 6 5

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 76.94.119.209
推 Eeon        :主因應該是你的演算法好很多，你加的那個條件好。
→ Eeon        :我只有加上下限，其他性質都沒用到，所以其實是很鳥
→ Eeon        :的演算法。
→ Sfly        :那個條件可以扣掉 23個數, 而C(75,10)/C(98,10) ~ 6%
→ Sfly        :剛試了一下, 拿掉這條件要8分鐘跑完, 接近理論值
→ Sfly        :你的code有跳出或空轉迴圈的機制嗎?
推 Eeon        :我的code裡，是直接用前面已決定的值來定出下一個迴
→ Eeon        :圈要跑的值的範圍。