华为OD机试真题 - 抢7游戏 (D卷,200分)

题目描述

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

A先报一个起始数字 X（10 ≤ 起始数字 ≤ 10000），B报下一个数字 Y （X - Y < 3），A再报一个数字 Z（Y - Z < 3），以此类推，直到其中一个抢到7，抢到7即为胜者；

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

目录

题目描述

输入描述

输出描述

用例

题目解析

Java算法源码

JS算法源码

Python算法源码

C算法源码

华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作

https://ac.nowcoder.com/acm/contest/5652/K

点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。

输入描述

起始数字 M

• 10 ≤ M ≤ 10000

如：

100

输出描述

B能赢得比赛的组合次数

用例

解析

1. 首先，我们需要定义一个函数，用于计算B赢得比赛的组合次数。
2. 在这个函数中，我们需要遍历从起始数字M到7的所有数字，对于每个数字i，我们需要计算B能赢得比赛的组合次数。
3. 对于每个数字i，我们需要考虑A报的数字j，使得j-i<3。由于A先报数字，所以A可以选择报任意一个小于i+3的数字j，这样B就无法报出7。因此，我们需要计算在A报出j的情况下，B能赢得比赛的组合次数。
4. 为了计算这个组合次数，我们可以使用动态规划的方法。我们定义一个数组dp，其中dp[k]表示在A报出k的情况下，B能赢得比赛的组合次数。我们可以发现，dp[k] = dp[k-1] + dp[k-2] + dp[k-3]，因为B可以选择报出k-1、k-2或k-3这三个数字中的一个。
5. 最后，我们将所有dp[i]相加，得到B能赢得比赛的总组合次数。
6. 返回这个总组合次数作为结果。

重新回答

|

|

JS算法源码

 const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

async function main() {
  const m = parseInt(await new Promise((resolve) => rl.once('line', resolve)));

  const factor = initFactor(m - 7);

  let oneCount = m - 7;
  let twoCount = 0;

  let ans = BigInt(0);

  while (oneCount >= 0) {
    if ((oneCount + twoCount) % 2 !== 0) {
      ans += getPermutationCount(oneCount, twoCount, factor);
    }

    oneCount -= 2;
    twoCount += 1;
  }

  console.log(ans.toString());
}

function getPermutationCount(oneCount, twoCount, factor) {
  if (oneCount === 0 || twoCount === 0) {
    return BigInt(1);
  } else {
    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 <= n; i++) {
    factor[i] = BigInt(i) * factor[i - 1];
  }

  return factor;
}

main();

Java算法源码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static BigInteger[] factor;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);