猴子分桃(很有趣的规律题)

spoiler posted @ 2011年4月17日 00:20 in 未分类 , 2870 阅读

题目大意:老猴子辛苦了一辈子,给那群小猴子们留下了一笔巨大的财富——一大堆桃子。
老猴子决定把这些桃子分给小猴子。
第一个猴子来了,它把桃子分成五堆,五堆一样多,但还多出一个。它把剩下的一个留给老猴子,自己拿走其中的一堆。
第二个猴子来了,它把桃子分成五堆,五堆一样多,但又多出一个。它把多出的一个留给老猴子,自己拿走其中的一堆。
后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。
这里有n只小猴子,请你写个程序计算一下在开始时至少有多少个桃子,以及最后老猴子最少能得到几个桃子。

题目分析:其实题目不是很难,但是我很悲剧的是,因为学校服务器的问题,害我WA了20多次,后来都别的网站上提交,1Y就过了!

这里表示非常不淡定。。。

废话不说了让我们看题目吧:假设有X个桃子,第一次把X个桃子分成5份,恰好多了1,然后拿走一份!再这里,您应该想到借他4个不就正好5份了麽?然后每次都不是5份了麽?最后当前猴子拿走的也没多拿不是麽?举个例子说明一下吧,假设有5只猴子,第一次每份

(X-1)/5;如果我们借给他4个,每份不就是(X+4)/5吗?然后您会发现,(X+1)/5=(X-1)/5+1;每次都是如此,然后每次都能被5整除,这很显然,所以您应该懂了吧~{^_^}X=5^n-4  老猴子得到=n+(X+4)*(4/5)^n-4(您得还我的呀!对吧 嘿嘿)

代码+部分注释:

#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
int main(){
	long long total_num,old_num;
	int n;
	while(cin>>n,n){
		total_num=pow(5,n)-4;
		old_num = n + (total_num+4)*(pow(0.8,n))-4;
		cout<<total_num<<" "<<old_num<<endl;
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter