作者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