※ 引述《ddavid (星舞弦独角兽神话忆)》之铭言： : ※ 引述《weiluner (游戏人间^^y)》之铭言： : : 店员有25元、10元、5元、1元的币值 : : 我想问的是 : : 如果要找出一种铜板总数目最小的方法 : : 这种把要找钱的数目先从大的币值除 : : 所得余数再由第二小的币值一直除下来的方法能够通用在所有的钱数吗 : : 如果可以 要如何证明呢？ 对不起 可能我写的不够清楚 第一个问题的前提是只有第一种币值情形下 要如何证明用上述方式就可以找到最小硬币数(其实等同第二个问题拉~) : : 如果今天我们的币值是25元、20元、10元、5元、1元 : : 利用以上方法 40元就不适用了 : : 最小的硬币数是2个20元 而不是1个25元、1个10元以及1个5元 : : 我想知道这两种币值有什麽差异 : : 为什麽第一种币值就可以用这种方式 而第二种不行 : 原因是，第一种币值的情况，每一个币值都大於等於两倍的比它小币值。这确保 : 了「当可以用某币值表现的值，其中一个硬币／钞票换成更小的来表现时一定得用两 : 个或以上。」 : 比如25 > 2 * 10，所以25可用1 * 25，换成用比它小的就要2 * 10 + 1 * 5共 : 三个。 : 而第二种币值中，25 < 20 * 2，这表示至少在20 * 2 = 40这个值上以25来表现 : 无法确保比用20来表现用更少的币数，因为20只要2个就能表现，但25用了1个之後还 : 剩余15，等於是至少要用2个才能表示，并可能更差。 我有想过这个方法 但是如果币值是5元、4元、3元、2元、1元我却找不到反例 5 < 4*2 所以只能证明哪种币值用此方法可以找到最小值 不一定每种能用此法找到最小值的币值都是符合这个条件吗? --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 163.25.93.75