此博客链接:https://www.cnblogs.com/ping2yingshi/p/12337747.html
核反应堆(72min)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2085
Problem Description
某核反应堆有两类事件发生:
高能质点碰击核子时,质点被吸收,放出3个高能质点和1个低能质点;
低能质点碰击核子时,质点被吸收,放出2个高能质点和1个低能质点。
假定开始的时候(0微秒)只有一个高能质点射入核反应堆,每一微秒引起一个事件发生(对于一个事件,当前存在的所有质点都会撞击核子),试确定n微秒时高能质点和低能质点的数目。
高能质点碰击核子时,质点被吸收,放出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
题解:
方法:找递推公式。
思路:根据题目描述的质点撞击核子规律,得到以下递推公式:
高能质点 低能质点
0 G[0]=1 D[0]=0
1 G[1]=3 D[1]=1
2 3*G[1]+2*D[1]=11 G[1]+D[1]=4
3 3*G[2]+2*D[2]=41 G[2]+D[2]=15
1 G[1]=3 D[1]=1
2 3*G[1]+2*D[1]=11 G[1]+D[1]=4
3 3*G[2]+2*D[2]=41 G[2]+D[2]=15
............
n 3*G[n-1]+2*D[n-1] G[n-1]+D[n-1]
注意:1.此题一开始我用的递归,但是超时,改用循环。
2.注意结果的大小,开始使用整型,结果错误,后来使用题目给的_int64,但是输出时的类型是%I64u。
代码如下:
#include<stdio.h> #include<math.h> #include<stdlib.h> #include<string.h> void PrintGD(int n) { __int64 g=1; __int64 d=0; for (int i = 1; i <= n; i++) { __int64 temp = g + d; g = 3 * g + 2 * d; d = temp; } printf("%I64u, %I64u\n", g, d); } int main() { int n; scanf_s("%d", &n); while (n!=-1) { PrintGD(n); scanf_s("%d", &n); } return 0; }