1、猴子分桃
题目连接
题目描述：
老猴子辛苦了一辈子，给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。
第一个猴子来了，它把桃子分成五堆，五堆一样多，但还多出一个。它把剩下的一个留给老猴子，自己拿走其中的一堆。
第二个猴子来了，它把桃子分成五堆，五堆一样多，但又多出一个。它把多出的一个留给老猴子，自己拿走其中的一堆。
后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。
这里有n只小猴子，请你写个程序计算一下在开始时至少有多少个桃子，以及最后老猴子最少能得到几个桃子。
输入描述：
输入包括多组测试数据。
每组测试数据包括一个整数n(1≤n≤20)。
输入以0结束，该行不做处理。
输出描述：
每组测试数据对应一行输出。
包括两个整数a，b。
分别代表开始时最小需要的桃子数，和结束后老猴子最少能得到的桃子数。
示例：
输入：
5
1
0
输出：
3121 1025
1 1
解题思路：
我们改变一下原题规则：假设一开始桃子个数为x，我们人为添加4个桃子之后总桃子数变为x+4。这样每次刚好可以分成5堆，不考虑每次拿完后给老猴子一个，最终剩下的桃子-4依然等于原
题场景的结果。
完整代码：
#include <iostream> #include <math.h> using namespace std; using namespace std; int main() { int n = 0; while(cin>>n && n!=0) { // 题目要求输出整数，而pow返回值类型为double // 5的20次方数值超过int的大小，所以强转为long cout<<(long)pow(5, n)-4<<' '<<(long)pow(4, n)+n-4<<endl; } return 0; }
性能分析：
时间复杂度：O(1)。
空间复杂度：O(1)
2、有假币
题目连接
题目描述：
居然有假币！ 现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。nowcoder这就去买猪肉，结果找来的零钱中有假币！！！可惜nowcoder 一不小心把它混进了一堆真币里面去了。只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），请用最快的时间把那个可恶的假币找出来。
输入描述：
1≤n≤2^30,输入0结束程序。
输出描述：
最多要称几次一定能把那个假币找出来？
示例：
输入：
3
12
0
输出：
1
3
解题思路：
对于要称量的硬币，每次称量前分成3份，要求前两份的个数不小于第三份，这样每次称完都可以排除2/3的硬币。
如果有一个硬币：最多称量0次，这个硬币就是假币。
如果有二个硬币：最多称量1次，轻的那个就是假币。
如果有三个硬币：最多称量1次，分成三份（1,1,1），先称量前两份轻的那个就是假币，如果前两份重量相等那么第三份的那个硬币就是假币。
如果有四个硬币：最多称量2次，分成三份（2,2,0），首先称量前两份，假币在轻的那两颗硬币里，在对轻的那份称一次得到假币。
如果有五个硬币：最多称2次，分成三份（2,2,1），考虑最差情况，首先称前两份，其中一份重量更轻，再单独对那份称量一次得到假币。
通过上面的例子我们可以发现规律：一次称量最多能找到2~3枚硬币中的假币、二次称量最多能找到4 ~ 9枚硬币中的假币，以此类推…
完整代码：
#include <iostream> using namespace std; int main() { int n = 0; while(cin>>n && n!=0) { int ret = 0; // 输入的n确定是在int范围内的 // sum每次要乘等3最终会大于n，那么可能会大于int最大范围所以sum类型我们定义为long long sum = 1; while(sum < n) { ++ret; sum *= 3; } cout<<ret<<endl; } return 0; }
性能分析：
时间复杂度：O(1)。
空间复杂度：O(1)。
