题意简述

有一张 \(n\) 个节点的无边图,图在连通之前每次随机抽取一个点然后建边,求期望操作次数(即最大多少次)。

思路

这道题似乎和图论没什么关系,首先我们看 \(n\) 个球抽出一个的概率是 \(\frac{1}{n}\) ,那么抽第二个时概率是 \(\frac{1}{n-1}\) 以此类推。所以最坏情况下就是抽第 \(n-1\) 个球是都没有抽到,所以我们就只需要把 \(1\)\(n-1\) 每个球抽中的概率加起来就行了。

code

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	double ans=0.0;
	for(double i=1;i<n;i++) ans+=(double)n/(n-i);
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。