ACM学习历程—Hihocoder 1164 随机斐波那契(数学递推)
2024-08-29 06:32:38
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
大家对斐波那契数列想必都很熟悉:
a0 = 1, a1 = 1, ai = ai-1 + ai-2,(i > 1)。
现在考虑如下生成的斐波那契数列:
a0 = 1, ai = aj + ak, i > 0, j, k从[0, i-1]的整数中随机选出(j和k独立)。
现在给定n,要求求出E(an),即各种可能的a数列中an的期望值。
输入
一行一个整数n,表示第n项。(1<=n<=500)
输出
一行一个实数,表示答案。你的输出和答案的绝对或者相对误差小于10-6时被视为正确答案。
样例解释
共存在3种可能的数列
1,2,2 1/4
1,2,3 1/2
1,2,4 1/4
所以期望为3。
- 样例输入
-
2
- 样例输出
-
3.000000
设f(n)表示an的期望值。
那么
设s(n)表示f(n)前n项的和,那么
当时Hihocoder挑战赛时没高兴推,直接暴力打表过的。
代码:
#include <iostream>
#include <cstdio>
#define LL long long using namespace std; double e[]; LL Sum(int n)
{
LL ans = ;
for (int i = ; i < n; ++i)
{
for (int j = ; j < n; ++j)
{
ans += e[i]+e[j];
}
}
return ans;
} void Init()
{
e[] = ;
double C2;
for (int i = ; i <= ; ++i)
{
C2 = i*i;
e[i] = Sum(i) / C2;
}
} int main()
{
Init();
int n;
while (scanf("%d", &n) != EOF)
{
printf("%.7lf\n", e[n]);
}
return ;
}
最新文章
- sqlite读取中文乱码(C#)
- C#程序
- javascript高级程序设计---Element对象
- qt-5.6.0 移植之tslib 配置及编译
- perl运行其他程序的5种方法
- Ubuntu 更新源
- GridVeiw 使用
- js字符串转化为方法调用
- MonoRail MVC应用(2)-构建多层结构的应用程序
- UVa 1593代码对齐
- 转: app端数据库(性能高) realm (ios, android 均支持)
- Android中FTP服务器搭建入门
- js中的对象封装
- Json.Net学习笔记(十) 保持对象引用
- openStack telemetry/ceilometry 云平台资源监控度量
- 常用颜色RGB、灰度值
- MongoDB之建立Windows和本地虚拟机的双向连接
- 第二章 python的介绍及变量
- SpringBoot之profile详解
- 一、Tableau基础
热门文章
- Android网络编程Socket【实例解析】
- caffe--anaconda2--makefile.config--compile --ubuntu16.04
- WinDbg调试分析 net站点 CPU100%问题
- Ubuntu64位安装Adobe Reader 9.5.5
- 【BZOJ4166】月宫的符卡序列 Manacher+hash
- android菜鸟学习笔记15----Android Junit测试
- HttpClient 访问 https 出现peer can&#39;t
- php异步任务处理: gearman
- python网络爬虫之使用scrapy自动登录网站
- JavaScript toFixed() 方法注意点