查找假币并输出查找过程问题

Question

编写一个实验程序用于求解这样的假币问题，共有 n ( n >3）个硬币，编号为0~ n -1，其中有且仅有一个假币，假币与真币的外观相同但重量不同，不知道假币比真而轻还是重，现在用一架天平称重，天平称重的硬币数没有限制。最后找出这个假巾，使得称重的次数尽可能少。要求采用相关数据进行测试并且输出称重过程。采用三分查找思想，用 coins [0.. n -1］存放 n 个硬币，其中 coins [ i ］表示编号为 i 的硬币的重量（真币的重量为2，假币的重量为1或者3), light 指定假币比真币轻还是重， light =1表示假币较轻， light =-1表示假币较重。查找的假币编号用 no 表示。在以 i 开始的 n 个硬币 coins [ i .. i + n -1］中查找假币的过程如下：(1）如果 n =1，依题意它就是假币，置 no = i ，返回结果。 (2）如果 n =2，将两个硬币 coins [ i ］和 coins [ i +1］称重一次，若与 light 一致，说明硬币 i 是假币，置 no = i ，否则说明硬币 i +1是假币，置 no = i +1，返回结果。 (3）如果 n ≥3，若 n %3=0或 n %3=1，置 k =[ n /3」，若 n %3=2，置 k = Ln /3」+1.依次将 coins 中的 n 个硬币分为3份， A 和 B 中各有 k 个硬币（ A 为 coins [ ia .. ia + k -1]. B 为 coins [ ib .. ib + k -1]), C 中有 n -2k个硬币（ C 为 coins [ ic .. ic + n -2k-1])，这样划分保证 C 中硬币个数和 A 、 B 中硬币个数最多相差1。将 A 和 B 中的硬币称重一次，结果为 b ，分为如下3种情况： ①若两者重量相等（ b =0)，说明 A 和 B 中的所有硬币都是真币，假币一定在 C 中，递归在 C 中查找假币并返回结果。 ②若 A 和 B 的重量不相等（ b ≠0)，如果 b 与 light 一致，说明假币一定在 A 中，递归在 A 中查找假币并返回结果。 如果 b 与 light 不一致，说明假币一定在 B 中，递归在 B 中查找假币并返回结果。要求生成完整且可以直接运行的c＋＋代码并且输出查找假币的整个过程

Answer 1

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7616441

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^