Generator

NC237335. Generator

描述

Mr.L has a uniform random generator.
In the beginning, Mr. L will input an integer $N$ , and then pushes the generate button. The generator will output a random integer $x\in [1,N]$ . Then he will push the button again, and the generator will output a random integer $y\in [1,x]$ and so on and so forth.
It is clear that the output is non-increasing, and after a number of pushes, the output will at last be $1$ . Now he wants to know the expected number of pushes to obtain $1$ as output.

输入描述

A positive integer  .

输出描述

A real number --- the expected number of pushes.
Your answer will be accepted if the relative or absolute error does not exceed .

示例1

输入:

输出:

1.0000000000

示例2

输入:

输出:

2.5000000000

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 6ms, 内存消耗: 468K, 提交时间: 2022-05-22 20:31:24

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;cin>>n;
	const int N=2e6;
	double ans=1;
	for(int i=1;i<=min(N,n)-1;i++)ans+=1.0/i;
	if(n>N)ans+=log(n-1)-log(N);
	cout<<fixed<<setprecision(6)<<ans;
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 500K, 提交时间: 2022-10-12 12:41:22

#include<bits/stdc++.h>
using namespace std;
double ans=0;
int main()
{
	int n=1e8;
	scanf("%d",&n);
	if(n<=1000000)
	for(int i=1;i<n;++i)
	{
		ans+=1.0/i;
	}
	else
	{
		ans=log(n)+0.577215659900;
	}
	printf("%.12lf",ans+1);
}