当前位置：首页 > news >正文

华为OD机试真题 - 抢7游戏（Python/JS/C/C++ 2024 D卷 100分）

news 来源：原创 2024/9/20 11:44:43

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

A、B两个人玩抢7游戏，游戏规则为A先报一个起始数字X (10 <= X <= 10000），B报下一个数字Y，(0<X-Y<3)，A再报一个数字Z(0<Y-Z<3)，以此类推，直到其中一个抢到7，抢到7即为胜者，在B赢得比赛的情况下，一共有多少种组合？

二、输入描述

起始数字M，如100

10 <= M <= 10000

三、输出描述

B能赢得比赛的组合次数。

四、解题思路

问题分析：
- 这个游戏本质上是从起始数字 m 到 7 的一个递减过程。
- 每次可以选择减1或减2，对应了两种操作。
- B 想要赢，必须在轮到自己时拿到 7。
问题转化：
- 我们可以将问题转化为排列组合问题。
- 从 m 到 7 的过程可以看作是排列若干个"减1"和"减2"操作。
- "减1"操作的次数 = m - 7
- 总操作次数必须为奇数，这样最后一步（到7）才会是 B 操作。
计算策略：
- 初始时，所有操作都是"减1"，即 oneCount = m - 7, twoCount = 0。
- 然后我们逐步将两个"减1"合并为一个"减2"，遍历所有可能的组合。
- 对于每种有效组合（总步数为奇数），计算其不重复排列数。
排列数计算：
- 使用组合数学公式：(oneCount + twoCount)! / (oneCount! * twoCount!)
- 这个公式计算了在总操作序列中，"减1"和"减2"的所有不重复排列方式。
大数处理：
- 由于数字可能很大，我们使用 BigInteger 来处理计算，避免溢出。
- 预先计算阶乘，存储在数组中，以提高效率。
结果累加：
- 对每种有效组合的排列数进行累加，得到最终 B 获胜的总情况数。

五、测试用例

1、输入

2、输出

3、说明

只有一种赢的组合，A起始选择10，B接着选择9，A接着选择8，B接着选择7赢得胜利。

六、Python算法源码

from math import factorial
from functools import lru_cache@lru_cache(None)
def get_permutation_count(one_count, two_count):if one_count == 0 or two_count == 0:return 1else:total_steps = one_count + two_countreturn factorial(total_steps) // (factorial(one_count) * factorial(two_count))def main():m = int(input("请输入起始数字: "))  # 读取起始数字one_count = m - 7  # 初始的1的数量（每次减1的操作数）two_count = 0      # 初始的2的数量（每次减2的操作数）ans = 0  # 用于记录B赢的情况总数# 遍历所有可能的1和2的组合while one_count >= 0:# 当总步数为奇数时，B才能赢（因为A先手）if (one_count + two_count) % 2 != 0:# 计算当前组合的排列数，并加到总数中ans += get_permutation_count(one_count, two_count)# 将两个1合并为一个2（即减少两次"减1"，增加一次"减2"）one_count -= 2two_count += 1# 输出结果print(ans)if __name__ == "__main__":main()

七、JavaScript算法源码

function factorial(n) {if (n === 0) return 1;let result = 1;for (let i = 1; i <= n; i++) {result *= i;}return result;
}function getPermutationCount(oneCount, twoCount) {if (oneCount === 0 || twoCount === 0) {return 1;} else {let totalSteps = oneCount + twoCount;return factorial(totalSteps) / (factorial(oneCount) * factorial(twoCount));}
}function main() {const m = parseInt(prompt("请输入起始数字: "), 10);  // 读取起始数字let oneCount = m - 7;  // 初始的1的数量（每次减1的操作数）let twoCount = 0;      // 初始的2的数量（每次减2的操作数）let ans = 0;  // 用于记录B赢的情况总数// 遍历所有可能的1和2的组合while (oneCount >= 0) {// 当总步数为奇数时，B才能赢（因为A先手）if ((oneCount + twoCount) % 2 !== 0) {// 计算当前组合的排列数，并加到总数中ans += getPermutationCount(oneCount, twoCount);}// 将两个1合并为一个2（即减少两次"减1"，增加一次"减2"）oneCount -= 2;twoCount += 1;}// 输出结果console.log(ans);
}main();

八、C算法源码

#include <stdio.h>typedef unsigned long long ull;// 计算阶乘
ull factorial(int n) {if (n == 0) return 1;ull result = 1;for (int i = 1; i <= n; i++) {result *= i;}return result;
}// 计算不重复的全排列数
ull get_permutation_count(int one_count, int two_count) {if (one_count == 0 || two_count == 0) {return 1;} else {int total_steps = one_count + two_count;return factorial(total_steps) / (factorial(one_count) * factorial(two_count));}
}int main() {int m;printf("请输入起始数字: ");scanf("%d", &m);  // 读取起始数字int one_count = m - 7;  // 初始的1的数量（每次减1的操作数）int two_count = 0;      // 初始的2的数量（每次减2的操作数）ull ans = 0;  // 用于记录B赢的情况总数// 遍历所有可能的1和2的组合while (one_count >= 0) {// 当总步数为奇数时，B才能赢（因为A先手）if ((one_count + two_count) % 2 != 0) {// 计算当前组合的排列数，并加到总数中ans += get_permutation_count(one_count, two_count);}// 将两个1合并为一个2（即减少两次"减1"，增加一次"减2"）one_count -= 2;two_count += 1;}// 输出结果printf("%llu\n", ans);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>  // 使用Boost库中的大整数类型using namespace std;
using namespace boost::multiprecision;vector<cpp_int> factor;// 初始化阶乘数组
void initFactor(int n) {factor.resize(n + 1);factor[0] = 1;  // 0! = 1for (int i = 1; i <= n; i++) {factor[i] = factor[i - 1] * i;}
}// 计算不重复的全排列数
cpp_int getPermutationCount(int oneCount, int twoCount) {if (oneCount == 0 || twoCount == 0) {return 1;  // 只有1或只有2的情况，只有一种排列方式} else {// 使用组合数学公式计算不重复的排列数// 公式：(oneCount + twoCount)! / (oneCount! * twoCount!)return factor[oneCount + twoCount] / (factor[oneCount] * factor[twoCount]);}
}int main() {int m;cout << "请输入起始数字: ";cin >> m;  // 读取起始数字// 初始化阶乘数组，最大需要计算 (m-7)!initFactor(m - 7);int oneCount = m - 7;  // 初始的1的数量（每次减1的操作数）int twoCount = 0;      // 初始的2的数量（每次减2的操作数）cpp_int ans = 0;       // 用于记录B赢的情况总数// 遍历所有可能的1和2的组合while (oneCount >= 0) {// 当总步数为奇数时，B才能赢（因为A先手）if ((oneCount + twoCount) % 2 != 0) {// 计算当前组合的排列数，并加到总数中ans += getPermutationCount(oneCount, twoCount);}// 将两个1合并为一个2（即减少两次"减1"，增加一次"减2"）oneCount -= 2;twoCount += 1;}// 输出结果cout << ans << endl;return 0;
}