华为OD机试 - 抢7游戏（Java & JS & Python & C）

题目描述

A、B两个人玩抢7游戏，游戏规则为：

A先报一个起始数字 X（10 ≤ 起始数字 ≤ 10000），B报下一个数字 Y （X - Y

在B赢得比赛的情况下，一共有多少种组合？

输入描述

起始数字 M

• 10 ≤ M ≤ 10000

  如：

  100

  输出描述

  B能赢得比赛的组合次数

  用例

  输入	10
  输出	1
  说明	无

  数学分析解法（可能会超时）

  下面模拟M为10~14时，B能够获胜的一些情况：

  

  看完上图，我们可以发现：

  抛开A首次叫的数字M，剩下的 M - 7 长度（上图中有颜色的），必须发生奇数次叫，才能保证B获胜。

  原因是：奇数次叫中，第一次必然是B，由于是奇数次，因此最后一次也必然是B，比如

  BAB

  BABAB

  都是奇数次。

  因此我们只需要将整数 M - 7 划分为奇数块即可，且每块取值只能是1或2。

  我们可以假设初始时，一共发生了M-7次叫（M-7可能不是奇数），即每块长度都是1，此时我们设

  • oneCount = M - 7
  • twoCount = 0

    然后检查 oneCount + twoCount 的和（一共叫几次）：

    • 若为奇数，则计算 oneCount 个 1 和 twoCount 个 2 形成的不重复的全排列的个数，统计进结果ans
    • 若为偶数，则B无法获胜

      之后，我们应该合并两个1为一个2，即：

      • oneCount -= 2
      • twoCount += 1

        此时就会产生一种新的叫声情况，将新的oneCount和twoCount带入前面逻辑，进行循环处理，知道oneCount

        本题的数量级很大，10 ≤ M ≤ 10000，因此满足要求的情况数量可能极端大，此时我们应该使用大数记录结果。

        JS算法源码

        const rl = require("readline").createInterface({ input: process.stdin });
        var iter = rl[Symbol.asyncIterator]();
        const readline = async () => (await iter.next()).value;
        void (async function () {
          const m = parseInt(await readline());
          const factor = initFactor(m - 7);
          let oneCount = m - 7;
          let twoCount = 0;
          // 记录B赢的情况数
          let ans = BigInt(0);
          while (oneCount >= 0) {
            // 叫的次数为奇数时，才能B赢
            if ((oneCount + twoCount) % 2 != 0) {
              ans += getPermutationCount(oneCount, twoCount);
            }
            // 合并两个1为一个2
            oneCount -= 2;
            twoCount += 1;
          }
          console.log(ans.toString());
          // 求解不重复的全排列数
          function getPermutationCount(oneCount, twoCount) {
            // 即 1 1 1 1 1 或 2 2 2 这种情况，此时只有一种排列
            if (oneCount == 0 || twoCount == 0) {
              return BigInt(1);
            } else {
              // 排列数去重，比如 1 1 1 2 2 的不重复排列数为 5! / 3! / 2! = 10
              return factor[oneCount + twoCount] / factor[oneCount] / factor[twoCount];
            }
          }
          // 阶乘
          function initFactor(n) {
            const factor = new Array(n + 1);
            factor[0] = BigInt(1);
            for (let i = 1; i = 0) {
              // 叫的次数为奇数时，才能B赢
              if ((oneCount + twoCount) % 2 != 0) {
                ans = ans.add(getPermutationCount(oneCount, twoCount));
              }
              // 合并两个1为一个2
              oneCount -= 2;
              twoCount += 1;
            }
            System.out.println(ans);
          }
          // 求解不重复的全排列数
          public static BigInteger getPermutationCount(int oneCount, int twoCount) {
            if (oneCount == 0 || twoCount == 0) { // 即 1 1 1 1 1 或 2 2 2 这种情况，此时只有一种排列
              return new BigInteger("1");
            } else {
              // 排列数去重，比如 1 1 1 2 2 的不重复排列数为 5! / 3! / 2! = 10
              return factor[oneCount + twoCount].divide(factor[oneCount].multiply(factor[twoCount]));
            }
          }
          // 阶乘
          public static void initFactor(int n) {
            factor = new BigInteger[n + 1];
            factor[0] = new BigInteger("1");
            for (int i = 1; i = 0:
                # 叫的次数为奇数时，才能B赢
                if (oneCount + twoCount) % 2 != 0:
                    ans += getPermutationCount(oneCount, twoCount)
                # 合并两个1为一个2
                oneCount -= 2
                twoCount += 1
            return ans
        print("{:.0f}".format(getResult()))
        

        C算法源码

        下面代码没有实现大数运算，关于大数运算可以参考：

        大数运算（加、减、乘、除）-CSDN博客

        #include 
        // 阶乘
        long long getFactor(int n) {
            long long ans = 1;
            for (int i = 2; i = 0) {
                // 叫的次数为奇数时，才能B赢
                if ((oneCount + twoCount) % 2 != 0) {
                    ans += getPermutationCount(oneCount, twoCount);
                }
                // 合并两个1为一个2
                oneCount -= 2;
                twoCount += 1;
            }
            printf("%lld", ans);
            return 0;
        }

        动态规划解法（不会超时） 

        本题最优解法为动态规划，动态规划的逻辑很简单，假设A从m开始叫，那么：

        B叫了数字 i 的方案数有多少种呢？

        如果B叫了数字 i，那么上一把A可能会叫数字i+1，也可能叫数字i+2

        dpB[i] 表示 B 能叫到数字 i 的方案数

        dpA[i] 表示 A 能叫到数字 j 的方案数

        那么 dpB[i] = dpA[i+1] + dpA[i+2]

        同理的是，如果A叫了数字 i，那么上一把B可能会叫数字i+1，也可能会叫数字 i+2

        那么 dpA[i] = dpB[i+1] + dpB[i+2]

        初始时，是A从m开始叫，因此 dpA[m] = 1，即A叫到数字m的方案数为1。而B肯定叫不到数字m，因此初始化dpB[m] = 0。

        之后我们可以递推出dpB[m-1]，即B叫出数字m-1的方案数，即dpB[m-1] = dpA[m] + dp[m+1]

        提示，根据dpB[m-1] = dpA[m] + dpA[m+1]的递推式，我们可以了解到dpA,dpB数组的长度应该初始化为m+2，这样上面递推式才不会越界。

        且dpA[m]  = 1，dpA[m+1] = 0

        而数字m-1，对于A而言是叫不到的，因此dpA[m-1]=0，但是也可以基于递推式得到：

        dpA[m-1] = dpB[m] + dpB[m+1]，而dpB[m]和dpB[m+1]都应该初始化为0。

        因此我们只需要按照上面递推式，一直递推到dpB[7]即可返回。

        Java算法源码

        import java.math.BigInteger;
        import java.util.Scanner;
        public class Main {
          public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int m = sc.nextInt();
            // dpA[i] 表示 A 叫 数字i 的方案数
            BigInteger[] dpA = new BigInteger[m + 2];
            // 初始化dpA[i]
            for (int i = 0; i = 7; i--) {
              // B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数
              dpB[i] = dpA[i + 1].add(dpA[i + 2]);
              // A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数
              dpA[i] = dpB[i + 1].add(dpB[i + 2]);
            }
            // 返回B叫7的方案数
            System.out.println(dpB[7]);
          }
        }
        

        JS算法源码

        const rl = require("readline").createInterface({ input: process.stdin });
        var iter = rl[Symbol.asyncIterator]();
        const readline = async () => (await iter.next()).value;
        void (async function () {
          const m = parseInt(await readline());
          // dpA[i] 表示 A 叫 数字i 的方案数
          const dpA = new Array(m + 2).fill(0).map(() => BigInt(0));
          // 由于是A从m开始叫，因此A叫m的方案数为1
          dpA[m] = BigInt(1);
          // dpB[i] 表示 B叫 数字i 的方案数
          const dpB = new Array(m + 2).fill(0).map(() => BigInt(0));
          for (let i = m - 1; i >= 7; i--) {
            // B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数
            dpB[i] = dpA[i + 1] + dpA[i + 2];
            // A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数
            dpA[i] = dpB[i + 1] + dpB[i + 2];
          }
          console.log(dpB[7].toString());
        })();
        

        Python算法源码

        # 输入获取
        m = int(input())
        # 算法入口
        def getResult():
            # dpA[i] 表示 A 叫 数字i 的方案数
            dpA = [0 for _ in range(m + 2)]
            # 由于是A从m开始叫，因此A叫m的方案数为1
            dpA[m] = 1
            # dpB[i] 表示 B叫 数字i 的方案数
            dpB = [0 for _ in range(m + 2)]
            for i in range(m - 1, 6, -1):
                # B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数
                dpB[i] = dpA[i + 1] + dpA[i + 2]
                # A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数
                dpA[i] = dpB[i + 1] + dpB[i + 2]
            # 返回B叫7的方案数
            return dpB[7]
        # 算法调用
        print(getResult())

        C算法源码

         下面代码没有实现大数运算，关于大数运算可以参考：

        大数运算（加、减、乘、除）-CSDN博客

        #include 
        int main() {
            int m;
            scanf("%d", &m);
            // dpA[i] 表示 A 叫 数字i 的方案数
            long long dpA[m + 2];
            // 初始化dpA[i]
            for (int i = 0; i = 7; i--) {
                // B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数
                dpB[i] = dpA[i + 1] + dpA[i + 2];
                // A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数
                dpA[i] = dpB[i + 1] + dpB[i + 2];
            }
            // 返回B叫7的方案数
            printf("%lld", dpB[7]);
            return 0;
        }