Re: [請益] 找出假幣

[yllan (藍永倫)]

※ 引述《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
推 thalesf:我很想說AlYoshi其實說的很清楚了, 似乎你一直看不懂
推 thalesf:不過當x＝y的確會有問題, 至於函數值z肯定會有最小吧
→ yllan:^^; 你說有最小值存在  就是我第二段講的啊  存在
→ yllan:但是他問的不只是存在，還可算，不只是可算，還 PTIME
→ yllan:我看得懂他的問題是要問P解啦  但他敘述的方式, 像你就會回
→ yllan:回答說，「存在」！但這又不是他要的答案 所以我才要他寫好
→ yllan:點來
→ aletheia:看不太懂什麼叫可算
推 yllan:可算就是 recursive(R), 邏輯裡頭也有討論 decidability 吧!
推 yllan:這題 R 解存在, EXP 解存在, 不知道有沒有 P 解, 大概這樣吧
→ aletheia:嗯 以這題來說 我猜存在就是可算了吧
推 yllan:Ya 的確可算 也在 EXP 內 但原作者想問的是 P 解 這個不知
推 thalesf:我語氣不好 真抱歉:)