Who's Studio.

hihoCoder#1164 - 随机斐波那契

Word count: 204Reading time: 1 min
2016/05/17

题目

考虑如下生成的斐波那契数列:
a[0] = 1, a[i] = a[j] + a[k], i > 0, j, k从[0, i-1]的整数中随机选出（j和k独立）
现在给定n，要求求出E(an)，即各种可能的a数列中an的期望值。
具体描述请见hihoCoder。

解题思路

本题其实很简单。考虑期望的定义，可以得到递推式：
f[i] = 1/i * sum(f[0], f[1], ..., f[i-1] + 1/i * sum(f[0], f[1], ..., f[i-1]

时间复杂度

时间复杂度为N，空间复杂度为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

float randomFib(int n) {
	float sum = 1;
	float fib = 0;
	for (int i = 1; i <= n; i++) {
		fib = 2 * sum / i;
		sum += fib;
	}

	return fib;
}

int main() {
	int n = 0;
	cin >> n;

	cout << randomFib(n) << endl;

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/17/2016-05-17-hihocoder-random-fibonacci/

Publish date：May 17th 2016, 6:35:29 pm

Update date：December 4th 2022, 5:10:59 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目