大厂笔试题1——小强去买东西的概率

题目记不清楚了，大致题意为：

小强和小丽两人划拳决定谁去买东西。小强从1~N中随机取一个数，小丽从1~M中随机取一个数，如果两个数之和为奇数，则小强去买东西；否则小丽去买东西。问小强去买东西的概率是多少？请用最简分数的形式返回该概率。

示例：N=2, M=3，则小强可以选择的数字范围是1、2， 小丽可以选择的数字范围是1、2、3，所有可能的数字组合有(1,1)、(1,2)、(1,3)、(2,1)、(2,2)、(2,3)。其中和为奇数的组合是(1,2)、(2,1)、(2,3)；和为偶数的组合是(1,1)、(1,3)、(2,2)。所以概率是3/6，即1/2。返回结果1/2。

解答：

定义小强的号码牌为 $i$ ,则 $i=1,2…N$ ，定义小丽的号码牌为 $j$ ,则 $j=1,2…M$ 。首先，组合$(i,j)$的数量一共是$M*N$，我们记为$total$

不妨从小强的角度考虑，对每个 $i$ 值，组合$(i,j)$的和分布在区域$[i+1, M+i]$，则这个范围内包含的奇数的个数是$\lfloor \frac{M+i+1}{2} \rfloor - \lfloor \frac{i+1}{2} \rfloor$ 。（原因：数字范围$[1,X]$内奇数的个数为$\lfloor \frac{X+1}{2} \rfloor$。）

所以，和为奇数的组合个数是$\sum^{N}_{i=1} \lfloor \frac{M+i+1}{2} \rfloor - \lfloor \frac{i+1}{2} \rfloor$ ，我们记作$odd$

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

题目要返回最简分数，所以要求$odd$和$total$的最大公约数，然后分子分母都除以最大公约数，就是结果。

代码如下：

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);
        }
    }
    // 求最大公约数
    public static int gcd(int a, int b){
        if(b==0) return a;
        else return gcd(b,a % b);
    }
}