首页 > 试题广场 >

小欧喝水

[编程题]小欧喝水

热度指数：306 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小欧拿了 $n$ 个杯子排成了一排，其中有 $k$ 个杯子装满了水，剩余的 $n-k$ 个杯子为空的。小欧每回合的操作如下：
1. 随机选择一个杯子。
2. 杯子是空的。回合直接结束。
3. 杯子是满的。如果小欧上一回合喝过了水，则回合结束；否则将喝完这杯水，回合结束。

小欧想知道，她喝完所有水的回合数期望是多少？

输入描述:

两个正整数，用空格隔开。

输出描述:

一个浮点数，代表期望的回合数。如果你的答案和正确答案的误差不超过，则认为答案正确。

示例1

输入

1 1

输出

1.000000000

说明

只有一杯水，第一回合就可以喝完。

示例2

输入

2 1

输出

2.000000000

说明

有50%的概率1回合喝完，有25%的概率需要2回合 ，有12.5%的概率需要3回合……
总期望为0.5*2+0.25*3+0.125*4+……=2

示例3

输入

2 2

输出

4.000000000

说明

第一回合有100%的概率喝一杯水。
第二回合无论是否选到有水的杯子都不会喝水。
0.5*3+0.25*4+0.125*5+...=4

算法知识视频讲解

0ffice

定义 $f_{n,k,t}$ )为n个杯子有k杯有水，上一轮喝了水( $t=1$ )),没喝水( $t=0$ ))的情况下的期望。
目标是求 $f_{n,k,0}$
状态转移

$\left \{ \begin{array}{} f_{n,k,0} & = & \frac{k}{n} (f_{n,k-1,1}+1)+\frac{n-k}{n}(f_{n,k,0}+1)\\ f_{n,k,1} & = & f_{n,k,0}+1 \end{array} \right. \Rightarrow f_{n,k,0}=\frac{n}{k}+f_{n,k-1,1}$

边界状态，没有杯子有水，k=0, $f_{n,0,0} = f_{n,0,1} = 0$

结果 $f_{n,k,0} = \frac{n+k}{k} + \frac{n+k-1}{k-1} + \cdots + \frac{n+2}{2} + f_{n,1,0}$

编辑于 2024-08-24 21:13:57 回复(0)

更多回答

牛客79348526号

#include <iostream>
using namespace std;
//大致的运行逻辑
double process(double k,double n,bool dr){
    if(k==0){
        return 0;
    }
    if(dr){
        return process(k,n,0)+1;
    }else {
        return double(n/k)+process(k-1,n,1);
    }
}

//改动态规划
int main() {
    int n;
    int k;
    cin>>n>>k;
    double dp[k][1];
    dp[0][0]=0;
    dp[0][1]=0;
    for(int i=1;i<=k;i++){
        dp[i][0]= double(n)/i+dp[i-1][1];
        dp[i][1]=dp[i][0]+1;
    }
    printf("%f",dp[k][0]);
}
// 64 位输出请用 printf("%lld")

发表于 2024-08-29 12:24:26 回复(0)

字节幺零二四

详细题解请移步至 A 或 B 或 C 或 D

发表于 2024-07-17 22:44:48 回复(0)

风清月明_不重复版昵称

import java.util.Scanner;
public class Main {
    static int nCup;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        nCup = scanner.nextInt();
        int kWater = scanner.nextInt();

        double expect = (double) nCup / kWater + computeExpectation(kWater - 1, true);
        System.out.println(expect);

        scanner.close();
    }

    private static double computeExpectation(int kWater, boolean drunk) {
        if (kWater == 0) {
            return 0;
        }
        return drunk ?
                1 + computeExpectation(kWater, false) :
                (double) nCup / kWater + computeExpectation(kWater - 1, true);
    }
}

发表于 2024-10-22 15:41:56 回复(1)

lukx

n个杯子，k杯有水，随机选取一杯直到选到有水的杯子，选取次数的期望为n/k；

根据题目要求，选到有水的杯子后喝水，之后冷却1回合，即总体期望+1；

之后问题转换为n个杯子，（k-1）杯有水；

不断递推直至k=1；

发表于 2024-08-09 02:48:20 回复(0)

三点一洲

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

double func(int n, int k) {
    if (k == 1) {
        double r = 0;
        int round = n < 100 ? 20 * n : 15 * n;
        for (int i = round; i >= 1; i--) {
            r += i * pow(1.0 * (n - 1) / n, i - 1) / n;
        }
        return r;
    }
    double r = func(n, 1) + k - 1;
    double tmp = 0;
    for (int i = 2; i <= k; i++) {
        tmp += 1.0 / i;
    }
    r += tmp * n;
    return r;
}


int main() {
    int n, k;
    while (cin >> n >> k) { // 注意 while 处理多个 case
        printf("%f", func(n, k));
    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-02-22 16:18:21 回复(0)

牛客764096563号

能过感觉不是正解，精度不好控制

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int n = in.nextInt(), k = in.nextInt();

double dp = find(1, n);

for (int i = 2; i <= k; i++) {

dp += find(i, n) + 1;

}

System.out.print(dp);

}

public static double find(int i, int n) { //n个杯子i杯水，喝到第一杯的期望轮次

if (i == n) {

return 1;

}

int round = 1;

double select = (double)i / n;

double noselect = (double)(n - i) / n;

double pre = 1;

double res = 0;

while (round * select * pre >= 0.000_000_1) { // 界限越小精度越高

res += round * pre * select;

pre *= noselect;

round++;

}

return res;

}

发表于 2024-07-24 18:11:15 回复(1)

Venn299


	
	
		int main() {
	

	
		    int n, k;
	

	
		    cin>>n>>k;
	

	
		    double ans = 0;
	

	
		    vector<double> dp(k+1,0);
	

	
		    dp[1] = double(n)/1;
	

	
		    for(int i=2;i<=k;i++){
	

	
		        dp[i] = double(n)/i + 1 + dp[i-1];
	

	
		    }
	

	
		    cout<<dp[k]<<endl;
	

	
		}

我这个为啥只能过11/20呀，错误的判例只差了0.03的误差，说明应该是double的处理有问题？

编辑于 2024-07-09 19:43:27 回复(2)

提交观点

问题信息

难度：

8条回答 37收藏 538浏览

小欧喝水

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题