[問題] 演算法問題

看板Prob_Solve作者 (可愛小孩子)時間8年前 (2016/06/13 13:46), 7年前編輯推噓5(5推 0噓 5→)
留言10則, 4人參與, 最新討論串7/8 (看更多)
n 個相異正整數: n1,n2,n3 ... 一正整數 r: n1,n2,n3 ... 除以 r 的餘數都不相等 試求 r 最小是多少 請問這題除了令 r = 2,3,4 ... 一直遞增試除下去以外 有什麼好的算法嗎 謝謝 ^_^ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.221.80.36 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1465796763.A.3A7.html
推
06/13 13:58, , 1F
r 應該可以從 n 開始試吧！
06/13 13:58, 1F
對喔，可以從 n 開始試
推
06/13 14:03, , 2F
r 最大是不是這 n 個數字的最大值 - 最小值 + 1 呢？
06/13 14:03, 2F
※ 編輯: cutekid (61.221.80.36), 06/13/2016 15:28:34
推
06/13 16:07, , 3F
r 顯然不能與任兩個數字的差相等，只是好像沒用。
06/13 16:07, 3F
推
06/13 21:52, , 4F
也不能是這些差的因數; 把這些數全部搜集起來之後
06/13 21:52, 4F
→
06/13 21:52, , 5F
求最小不在其中的數應該就是答案了
06/13 21:52, 5F
→
06/13 21:54, , 6F
另外 r 有可能會是全部的最大值; 例如輸入是前 n 個自然數
06/13 21:54, 6F
→
06/13 21:55, , 7F
噢, 仔細想了一下, Max-Min+1 好像是對的
06/13 21:55, 7F
→
06/14 12:21, , 8F
謝謝 s 跟 L 大，提供 2 個減少搜尋的 heuristic
06/14 12:21, 8F
→
06/28 00:14, , 9F
Google「中國剩餘定理」「大衍求一術」
06/28 00:14, 9F
※ 編輯: cutekid (210.61.233.210), 06/28/2016 13:09:12
推
06/28 17:34, , 10F
樓上推文好像搞錯問題了, 這題不是給定餘數...
06/28 17:34, 10F
‣ 更多 cutekid 的文章
文章代碼(AID): #1NNaYREd (Prob_Solve)
‣ 更多 cutekid 的文章
文章代碼(AID): #1NNaYREd (Prob_Solve)