华为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能赢得比赛的组合次数
用例
解析
- 首先,我们需要定义一个函数,用于计算B赢得比赛的组合次数。
- 在这个函数中,我们需要遍历从起始数字M到7的所有数字,对于每个数字i,我们需要计算B能赢得比赛的组合次数。
- 对于每个数字i,我们需要考虑A报的数字j,使得j-i<3。由于A先报数字,所以A可以选择报任意一个小于i+3的数字j,这样B就无法报出7。因此,我们需要计算在A报出j的情况下,B能赢得比赛的组合次数。
- 为了计算这个组合次数,我们可以使用动态规划的方法。我们定义一个数组dp,其中dp[k]表示在A报出k的情况下,B能赢得比赛的组合次数。我们可以发现,dp[k] = dp[k-1] + dp[k-2] + dp[k-3],因为B可以选择报出k-1、k-2或k-3这三个数字中的一个。
- 最后,我们将所有dp[i]相加,得到B能赢得比赛的总组合次数。
- 返回这个总组合次数作为结果。
重新回答
|
|
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);
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试题库D卷 文章被收录于专栏
2024年5-11月份考的D卷,不用再看AB卷,CD卷题目一样。多种语言解法,欢迎提供更好的解法。