7-8 梯云纵

7-8 梯云纵

牛顿祖师爷宣布神州影视城不归他管之后，横 * 梯云纵就可以原地起飞直奔月球了。假设横 * 离月球只有 n 米，而横 * 扛把子左脚右脚一个慢动作能等概率上升 1 米 或者 2 米。请你算算他登陆月球的步数期望。
注意，当他离月球只有 1 米是，他会 100% 的概率选择上升 1 米。
设 X 步到月球的概率 P(X) 为，则登陆月球的步数期望 =∑ X=0n P(X)∗X
输入格式:
第一行输入样例组数 t(1<=t<=100)
之后的 t 行，每行给出一个正整数 n(1<=n<=10 5) 表示横 * 里月球有 n 米

输出格式:
对每一组数据，在一行中输出到月球的步数期望，四舍五入保留6位小数。

输入样例:
在这里给出一组输入。例如：

3
1
2
3

输出样例:
在这里给出相应的输出。例如：

1.000000
1.500000
2.250000

代码：

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
int n;
double a[110000];
double mid[110000];
double getmid(int x)//返回差值
{
    if(mid[x]!=0)
        return mid[x];
    else
        return mid[x]=(getmid(x-1)+getmid(x-2))/2;
}
double geta(int x)
{
    if(a[x]!=0)
        return a[x];
    else
        return a[x]=geta(x-1)+getmid(x-1);
}
double change(double x)
{
    if(x<10000)
        return x;
    return x+0.0000002;
}
int main()
{
    scanf("%d",&n);
    int x;

    a[0]=0;
    a[1]=1;
    a[2]=1.5;
    a[3]=2.25;
    //a[4]=2.875;
    mid[0]=a[1]-a[0];
    mid[1]=a[2]-a[1];
    mid[2]=a[3]-a[2];
    //mid[3]=a[4]-a[3];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x);
        double z=geta(x);
        printf("%lf\n",change(z));
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

提示:
20%的数据，1<=n<=10
40%的数据，1<=n<=10 2
60%的数据，1<=n<=10 4
100%的数据，1<=n<=10 5

202206222107三