Posted on 2010-08-07 13:09
MiYu 閱讀(781)
評論(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;
}