阿里筆試題1——小強去買東西的概率

題目記不清楚了懂扼，大致題意為：

小強和小麗兩人劃拳決定誰去買東西。小強從1~N中隨機取一個數(shù)嘹锁，小麗從1~M中隨機取一個數(shù)葫录，如果兩個數(shù)之和為奇數(shù)，則小強去買東西领猾；否則小麗去買東西米同。問小強去買東西的概率是多少？請用最簡分數(shù)的形式返回該概率摔竿。

示例：N=2, M=3面粮，則小強可以選擇的數(shù)字范圍是1、2继低，小麗可以選擇的數(shù)字范圍是1熬苍、2、3袁翁，所有可能的數(shù)字組合有(1,1)柴底、(1,2)婿脸、(1,3)、(2,1)似枕、(2,2)盖淡、(2,3)。其中和為奇數(shù)的組合是(1,2)凿歼、(2,1)褪迟、(2,3)；和為偶數(shù)的組合是(1,1)答憔、(1,3)味赃、(2,2)。所以概率是3/6虐拓，即1/2心俗。返回結(jié)果1/2。

解答：

定義小強的號碼牌為 $i$ ,則 $i=1,2...N$ 蓉驹，定義小麗的號碼牌為 $j$ ,則 $j=1,2...M$ 城榛。首先，組合 $(i,j)$ 的數(shù)量一共是 $M*N$ 态兴，我們記為 $total$

不妨從小強的角度考慮狠持，對每個 $i$ 值，組合 $(i,j)$ 的和分布在區(qū)域 $[i+1, M+i]$ 瞻润，則這個范圍內(nèi)包含的奇數(shù)的個數(shù)是 $\lfloor \frac{M+i+1}{2} \rfloor - \lfloor \frac{i+1}{2} \rfloor$ 喘垂。（原因：數(shù)字范圍 $[1,X]$ 內(nèi)奇數(shù)的個數(shù)為 $\lfloor \frac{X+1}{2} \rfloor$ 。）

所以绍撞，和為奇數(shù)的組合個數(shù)是 $\sum^{N}_{i=1} \lfloor \frac{M+i+1}{2} \rfloor - \lfloor \frac{i+1}{2} \rfloor$ 正勒，我們記作 $odd$

所求概率 $p=\frac{odd}{total}$

題目要返回最簡分數(shù)，所以要求 $odd$ 和 $total$ 的最大公約數(shù)傻铣，然后分子分母都除以最大公約數(shù)章贞，就是結(jié)果。

代碼如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int N = sc.nextInt();
            int M = sc.nextInt();
            int odd = 0;
            for(int i = 1;i<=N;i++){
                // java的除會自動向下去整
                odd += (M+i+1)/2 - (i+1)/2;
            }
            int total=M*N;
            int factor = gcd(odd, total);
            System.err.printf("%d/%d\n", odd/factor,total/factor);
        }
    }
    // 求最大公約數(shù)
    public static int gcd(int a, int b){
        if(b==0) return a;
        else return gcd(b,a % b);
    }
}

最后編輯于：2020.09.22 21:26:06

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者