银币有关问题 动态规划算法
银币问题 动态规划算法
我们学校的oj上的一题
银币问题
问题描述
在n个银币中有一个是不合格的，不合格的银币比合格银币要轻。
现用天平秤银币，找出不合格的银币，且在最坏情况下秤银币的次数最少。
输入
输入有若干行。每行上有一个整数n，表示银币个数，n<=100000。
当n=0，表示输入结束。
输出
对输入大于0的整数n，输出2行。第1行输出n的值，第2行上先输出“Times:”，接着输出在最坏情况下秤n个银币的最少次数。
当n=0时，这种情况你不必处理和结果输出。
输入样例
4
7
50
0
输出样例
4
Times:2
7
Times:2
50
Times:4
------解决方案--------------------
这个搞过很多次了吧
直接求ceiling(log3(n))
4
Times:2=ceiling(log3(4))=ceiling(1.xxx)=2
7
Times:2=ceiling(log3(7))=ceiling(1.xxx)=2
50
Times:4=ceiling(log3(50))=ceiling(3.xxx)=4
我们学校的oj上的一题
银币问题
问题描述
在n个银币中有一个是不合格的，不合格的银币比合格银币要轻。
现用天平秤银币，找出不合格的银币，且在最坏情况下秤银币的次数最少。
输入
输入有若干行。每行上有一个整数n，表示银币个数，n<=100000。
当n=0，表示输入结束。
输出
对输入大于0的整数n，输出2行。第1行输出n的值，第2行上先输出“Times:”，接着输出在最坏情况下秤n个银币的最少次数。
当n=0时，这种情况你不必处理和结果输出。
输入样例
4
7
50
0
输出样例
4
Times:2
7
Times:2
50
Times:4
------解决方案--------------------
这个搞过很多次了吧
直接求ceiling(log3(n))
4
Times:2=ceiling(log3(4))=ceiling(1.xxx)=2
7
Times:2=ceiling(log3(7))=ceiling(1.xxx)=2
50
Times:4=ceiling(log3(50))=ceiling(3.xxx)=4