Posted on 2010-08-07 13:09
MiYu 閱讀(769)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 水題 ) 、
ACM ( 遞推 & 遞歸 )
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2085
題目描述:
Problem Description
某核反應(yīng)堆有兩類事件發(fā)生：
高能質(zhì)點(diǎn)碰擊核子時，質(zhì)點(diǎn)被吸收，放出3個高能質(zhì)點(diǎn)和1個低能質(zhì)點(diǎn)；
低能質(zhì)點(diǎn)碰擊核子時，質(zhì)點(diǎn)被吸收，放出2個高能質(zhì)點(diǎn)和1個低能質(zhì)點(diǎn)。
假定開始的時候（0微秒）只有一個高能質(zhì)點(diǎn)射入核反應(yīng)堆，每一微秒引起一個事件發(fā)生(對于一個事件，當(dāng)前存在的所有質(zhì)點(diǎn)都會撞擊核子)，試確定n微秒時高能質(zhì)點(diǎn)和低能質(zhì)點(diǎn)的數(shù)目。
Input
輸入含有一些整數(shù)n(0≤n≤33)，以微秒為單位，若n為-1表示處理結(jié)束。
Output
分別輸出n微秒時刻高能質(zhì)點(diǎn)和低能質(zhì)點(diǎn)的數(shù)量，高能質(zhì)點(diǎn)與低能質(zhì)點(diǎn)數(shù)量之間以逗號空格分隔。每個輸出占一行。
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]; // 低能
有一點(diǎn)要注意 , 需要 64位整形保存結(jié)果, 否則會溢出.
代碼如下:
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
#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;
}