作者yllan (藍永倫)
看板logic
標題Re: [請益] 找出假幣
時間Wed Dec 7 17:39:58 2005
※ 引述《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
1F：推 thalesf:我很想說AlYoshi其實說的很清楚了, 似乎你一直看不懂 12/07 22:44
2F：推 thalesf:不過當x＝y的確會有問題, 至於函數值z肯定會有最小吧 12/07 22:52
3F：→ yllan:^^; 你說有最小值存在 就是我第二段講的啊 存在 12/07 23:36
4F：→ yllan:但是他問的不只是存在，還可算，不只是可算，還 PTIME 12/07 23:37
5F：→ yllan:我看得懂他的問題是要問P解啦 但他敘述的方式, 像你就會回 12/07 23:39
6F：→ yllan:回答說，「存在」！但這又不是他要的答案 所以我才要他寫好 12/07 23:40
7F：→ yllan:點來 12/07 23:41
8F：→ aletheia:看不太懂什麼叫可算 12/09 12:35
9F：推 yllan:可算就是 recursive(R), 邏輯裡頭也有討論 decidability 吧! 12/09 20:49
10F：推 yllan:這題 R 解存在, EXP 解存在, 不知道有沒有 P 解, 大概這樣吧 12/09 20:54
11F：→ aletheia:嗯 以這題來說 我猜存在就是可算了吧 12/10 14:00
12F：推 yllan:Ya 的確可算 也在 EXP 內 但原作者想問的是 P 解 這個不知 12/10 21:34
13F：推 thalesf:我語氣不好 真抱歉:) 12/12 12:41