Re: [請益] 找出假幣

看板logic作者 (藍永倫)時間18年前 (2005/12/07 17:24), 編輯推噓6(607)
留言13則, 3人參與, 最新討論串9/14 (看更多)
※ 引述《A1Yoshi (我是按摩棒...)》之銘言: : 嗯,有道理。那就這樣定義吧: : 一、X為大於等於2的自然數,Y為大於等於1的自然數,Z為大於等於1的自然數。 : 二、X表示真球的數目,而真球每一顆重量都一樣。Y表示假球的數目,而假球 : 每一顆重量都一樣,但與真球重量不一樣(可能大也可能小於真球)。 : 三、目標是藉由天平,分出所有的假球。Z為所需稱量次數之最小值。 : 舉例來說:f(12, 1) = 3 你要這樣定的話,我可以告訴你,你這樣定的函數是不存在的,要不就是 第一點出問題(加上 X != Y),要不就是第三點出問題(最小值不存在的話, 隨便 assign 一個亂七八糟的數字,例如 -1)。 這大概不是你要的答案... 回到你第一篇的 "換句話說..." ,也是怪怪的 若只看換句話說後面的東西,我可以回答,這個函數是存在的 但這也不是你要的答案 其實我看得懂你的意思啦 只是你文字欠嚴謹, 做學問時容易在小地方造成混淆 這個問題不錯 目前還是 open problem ,有興趣可以解解看, 我解了一個下午都解不開。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.31.131

12/07 22:44, , 1F
我很想說AlYoshi其實說的很清楚了, 似乎你一直看不懂
12/07 22:44, 1F

12/07 22:52, , 2F
不過當x=y的確會有問題, 至於函數值z肯定會有最小吧
12/07 22:52, 2F

12/07 23:36, , 3F
^^; 你說有最小值存在 就是我第二段講的啊 存在
12/07 23:36, 3F

12/07 23:37, , 4F
但是他問的不只是存在,還可算,不只是可算,還 PTIME
12/07 23:37, 4F

12/07 23:39, , 5F
我看得懂他的問題是要問P解啦 但他敘述的方式, 像你就會回
12/07 23:39, 5F

12/07 23:40, , 6F
回答說,「存在」!但這又不是他要的答案 所以我才要他寫好
12/07 23:40, 6F

12/07 23:41, , 7F
點來
12/07 23:41, 7F

12/09 12:35, , 8F
看不太懂什麼叫可算
12/09 12:35, 8F

12/09 20:49, , 9F
可算就是 recursive(R), 邏輯裡頭也有討論 decidability 吧!
12/09 20:49, 9F

12/09 20:54, , 10F
這題 R 解存在, EXP 解存在, 不知道有沒有 P 解, 大概這樣吧
12/09 20:54, 10F

12/10 14:00, , 11F
嗯 以這題來說 我猜存在就是可算了吧
12/10 14:00, 11F

12/10 21:34, , 12F
Ya 的確可算 也在 EXP 內 但原作者想問的是 P 解 這個不知
12/10 21:34, 12F

12/12 12:41, , 13F
我語氣不好 真抱歉:)
12/12 12:41, 13F
文章代碼(AID): #13bgfXvt (logic)
討論串 (同標題文章)
文章代碼(AID): #13bgfXvt (logic)