Posted on 2010-08-07 13:09
MiYu 阅读(760)
评论(0) 编辑 收藏 引用 所属分类:
ACM ( 水题 ) 、
ACM ( 递推 & 递归 )
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2085
题目描述:
Problem Description
某核反应堆有两类事件发生：
高能质点碰击核子时，质点被吸收，放出3个高能质点和1个低能质点；
低能质点碰击核子时，质点被吸收，放出2个高能质点和1个低能质点。
假定开始的时候（0微秒）只有一个高能质点射入核反应堆，每一微秒引起一个事件发生(对于一个事件，当前存在的所有质点都会撞击核子)，试确定n微秒时高能质点和低能质点的数目。
Input
输入含有一些整数n(0≤n≤33)，以微秒为单位，若n为-1表示处理结束。
Output
分别输出n微秒时刻高能质点和低能质点的数量，高能质点与低能质点数量之间以逗号空格分隔。每个输出占一行。
Sample Input
5 2
-1
Sample Output
571, 209
11, 4
一个很简单的递推题 :
H[i] = 3 * H[i-1] + 2 * L[i-1]; //高能
L[i] = H[i-1] + L[i-1]; // 低能
有一点要注意 , 需要 64位整形保存结果, 否则会溢出.
代码如下:
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
#include <iostream>
using namespace std;
int main ()
{
long long H[34] = { 1 , 3 },L[34] = { 0 , 1 };
for ( int i = 2; i != 34; ++ i )
{
H[i] = 3 * H[i-1] + 2 * L[i-1];
L[i] = H[i-1] + L[i-1];
}
int N;
while ( cin >> N , N + 1 )
{
cout << H[N] << ", " << L[N] << endl;
}
return 0;
}