华为OD机试 - 猜数字 - 暴力枚举（Python/JS/C/C++ 2024 E卷 100分）

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

专栏导读

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

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

一、题目描述

一个人设定一组四码的数字作为谜底，另一方猜。

每猜一个数，出题者就要根据这个数字给出提示，提示以XAYB形式呈现，直到猜中位置。

其中X表示位置正确的数的个数（数字正确且位置正确），而Y表示数字正确而位置不对的数的个数。

例如，当谜底为8123，而猜谜者猜1052时，出题者必须提示0A2B。

例如，当谜底为5637，而猜谜者猜4931时，出题者必须提示1A0B。

当前已知N组猜谜者猜的数字与提示，如果答案确定，请输出答案，不确定则输出NA。

二、输入描述

第一行输入一个正整数N，0 < N < 100。

接下来N行，每一行包含一个猜测的数字与提示结果。

三、输出描述

输出最后的答案，答案不确定则输出NA。

四、测试用例

测试用例1

1、输入

3
1234 1A2B
5678 0A1B
9012 0A0B

2、输出

NA

3、说明

没有唯一符合所有提示的谜底，因此输出"NA"。

测试用例2

1、输入

2
0000 4A0B
1111 0A0B

2、输出

0000

3、说明

唯一符合所有提示的谜底是0000。

五、解题思路

本题的核心算法是穷举所有可能的四位数字组合（从0000到9999），即遍历所有可能的谜底。

对于每一个可能的谜底，逐一检查它是否能满足所有给定的提示。

1、为什么采用穷举搜索？

题目要求我们找出一个四位数的谜底，这意味着谜底的取值范围是从0000到9999，总共只有10000种可能。

对于计算机来说，遍历10000种可能性是一个非常可控的操作，执行时间相对较短。因此，使用穷举搜索可以在合理的时间内完成。

2、具体步骤：

1. 枚举所有可能的谜底
   • 谜底是一个四位数，范围从0000到9999，总共有10000种可能性。
   • 我们需要遍历所有这些可能性，逐个验证它们是否符合所有提示。
2. 验证每一个可能的谜底
   • 对于每一个可能的谜底，我们需要根据所有的提示验证它是否符合条件。
   • 提示格式为 XAYB，其中：
   • X 表示猜测中有多少个数字在正确的位置上。
   • Y 表示猜测中有多少个数字是正确的，但位置不对。
3. 具体验证步骤如下：
   • 对于每个提示，计算当前可能谜底与猜测之间的 X 和 Y 值。
   • 将计算出的 X 和 Y 与输入的提示进行比较，如果不相等，则该可能的谜底无效。

3、复杂度分析

总共有10000个可能的四位数谜底。

对于每个可能的谜底，需要验证它是否符合N个提示。时间复杂度为 O(10000×N)，在最坏情况下，N为100。

由于数据范围相对较小，穷举法可以在合理的时间内解决问题。

六、Python算法源码

# 导入必要的模块
import sysdef main():# 读取所有输入并按空白字符分割input = sys.stdin.read().split()index = 0# 读取猜测次数Nn = int(input[index])index += 1# 初始化猜测和提示的列表guesses = []hints = []# 读取每一组猜测和提示for _ in range(n):guesses.append(input[index])hints.append(input[index + 1])index += 2# 查找可能的谜底result = findPossibleAnswer(n, guesses, hints)# 输出结果print(result)def findPossibleAnswer(n, guesses, hints):possibleAnswer = None# 遍历所有可能的四位数字for i in range(10000):# 将数字格式化为四位字符串currentGuess = f"{i:04d}"isValid = True# 验证当前数字是否符合所有提示for j in range(n):# 生成当前猜测与谜底的提示hint = generateHint(currentGuess, guesses[j])# 如果提示不匹配，则当前数字不符合if hint != hints[j]:isValid = Falsebreak# 如果当前数字符合所有提示if isValid:if possibleAnswer is None:possibleAnswer = currentGuesselse:# 如果已经有一个符合的谜底，则不唯一，返回"NA"return "NA"# 返回唯一的谜底或"NA"return possibleAnswer if possibleAnswer is not None else "NA"def generateHint(answer, guess):A = 0  # 数字正确且位置正确的个数B = 0  # 数字正确但位置不对的个数# 标记已经匹配的数字answerUsed = [False] * 4guessUsed = [False] * 4# 先计算A值for i in range(4):if answer[i] == guess[i]:A += 1answerUsed[i] = TrueguessUsed[i] = True# 再计算B值for i in range(4):if not guessUsed[i]:for j in range(4):if not answerUsed[j] and guess[i] == answer[j]:B += 1answerUsed[j] = Truebreak# 返回提示字符串return f"{A}A{B}B"# 调用主函数
if __name__ == "__main__":main()

七、JavaScript算法源码

// 使用标准输入输出
process.stdin.resume();
process.stdin.setEncoding('utf8');let input = '';// 读取输入数据
process.stdin.on('data', function(chunk) {input += chunk;
});// 输入结束后处理数据
process.stdin.on('end', function() {// 按空白字符分割输入const tokens = input.trim().split(/\s+/);let index = 0;// 读取猜测次数Nconst n = parseInt(tokens[index++], 10);// 初始化猜测和提示的数组const guesses = [];const hints = [];// 读取每一组猜测和提示for(let i = 0; i < n; i++) {guesses.push(tokens[index++]);hints.push(tokens[index++]);}// 查找可能的谜底const result = findPossibleAnswer(n, guesses, hints);// 输出结果console.log(result);
});// 定义查找可能谜底的函数
function findPossibleAnswer(n, guesses, hints) {let possibleAnswer = null;// 遍历所有可能的四位数字for(let i = 0; i <= 9999; i++) {// 将数字格式化为四位字符串const currentGuess = i.toString().padStart(4, '0');let isValid = true;// 验证当前数字是否符合所有提示for(let j = 0; j < n; j++) {// 生成当前猜测与谜底的提示const hint = generateHint(currentGuess, guesses[j]);// 如果提示不匹配，则当前数字不符合if(hint !== hints[j]) {isValid = false;break;}}// 如果当前数字符合所有提示if(isValid) {if(possibleAnswer === null) {possibleAnswer = currentGuess;} else {// 如果已经有一个符合的谜底，则不唯一，返回"NA"return "NA";}}}// 返回唯一的谜底或"NA"return possibleAnswer !== null ? possibleAnswer : "NA";
}// 定义生成提示的函数
function generateHint(answer, guess) {let A = 0; // 数字正确且位置正确的个数let B = 0; // 数字正确但位置不对的个数// 标记已经匹配的数字const answerUsed = [false, false, false, false];const guessUsed = [false, false, false, false];// 先计算A值for(let i = 0; i < 4; i++) {if(answer[i] === guess[i]) {A += 1;answerUsed[i] = true;guessUsed[i] = true;}}// 再计算B值for(let i = 0; i < 4; i++) {if(!guessUsed[i]) {for(let j = 0; j < 4; j++) {if(!answerUsed[j] && guess[i] === answer[j]) {B += 1;answerUsed[j] = true;break;}}}}// 返回提示字符串return `${A}A${B}B`;
}

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义最大可能的谜底数量
#define MAX_POSSIBLE 10000// 函数声明
char* findPossibleAnswer(int n, char guesses[][5], char hints[][5]);
char* generateHint(char* answer, char* guess);int main(){int n;// 读取猜测次数Nscanf("%d", &n);// 动态分配猜测和提示的数组char (*guesses)[5] = malloc(n * sizeof(*guesses));char (*hints)[5] = malloc(n * sizeof(*hints));// 读取每一组猜测和提示for(int i = 0; i < n; i++) {scanf("%s %s", guesses[i], hints[i]);}// 查找可能的谜底char* result = findPossibleAnswer(n, guesses, hints);// 输出结果printf("%s\n", result);// 释放动态分配的内存free(guesses);free(hints);free(result);return 0;
}// 定义查找可能谜底的函数
char* findPossibleAnswer(int n, char guesses[][5], char hints[][5]) {char* possibleAnswer = NULL;// 遍历所有可能的四位数字for(int i = 0; i <= 9999; i++) {// 将数字格式化为四位字符串char currentGuess[5];sprintf(currentGuess, "%04d", i);int isValid = 1;// 验证当前数字是否符合所有提示for(int j = 0; j < n; j++) {// 生成当前猜测与谜底的提示char* hint = generateHint(currentGuess, guesses[j]);// 如果提示不匹配，则当前数字不符合if(strcmp(hint, hints[j]) != 0) {isValid = 0;free(hint);break;}free(hint);}// 如果当前数字符合所有提示if(isValid) {if(possibleAnswer == NULL) {possibleAnswer = malloc(5 * sizeof(char));strcpy(possibleAnswer, currentGuess);}else {// 如果已经有一个符合的谜底，则不唯一，返回"NA"free(possibleAnswer);return "NA";}}}// 返回唯一的谜底或"NA"if(possibleAnswer != NULL) {return possibleAnswer;}else {// 分配内存存储"NA"char* na = malloc(3 * sizeof(char));strcpy(na, "NA");return na;}
}// 定义生成提示的函数
char* generateHint(char* answer, char* guess){int A = 0; // 数字正确且位置正确的个数int B = 0; // 数字正确但位置不对的个数// 标记已经匹配的数字int answerUsed[4] = {0, 0, 0, 0};int guessUsed[4] = {0, 0, 0, 0};// 先计算A值for(int i = 0; i < 4; i++) {if(answer[i] == guess[i]) {A += 1;answerUsed[i] = 1;guessUsed[i] = 1;}}// 再计算B值for(int i = 0; i < 4; i++) {if(!guessUsed[i]) {for(int j = 0; j < 4; j++) {if(!answerUsed[j] && guess[i] == answer[j]) {B += 1;answerUsed[j] = 1;break;}}}}// 分配内存存储提示字符串char* hintStr = malloc(5 * sizeof(char));sprintf(hintStr, "%dA%dB", A, B);return hintStr;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;// 函数声明
string findPossibleAnswer(int n, vector<string> guesses, vector<string> hints);
string generateHint(string answer, string guess);int main(){int n;// 读取猜测次数Ncin >> n;// 初始化猜测和提示的向量vector<string> guesses(n);vector<string> hints(n);// 读取每一组猜测和提示for(int i = 0; i < n; i++) {cin >> guesses[i] >> hints[i];}// 查找可能的谜底string result = findPossibleAnswer(n, guesses, hints);// 输出结果cout << result << "\n";return 0;
}// 定义查找可能谜底的函数
string findPossibleAnswer(int n, vector<string> guesses, vector<string> hints){string possibleAnswer = "";bool multiple = false;// 遍历所有可能的四位数字for(int i = 0; i <= 9999; i++) {// 将数字格式化为四位字符串string currentGuess = to_string(i);while(currentGuess.length() < 4) currentGuess = "0" + currentGuess;bool isValid = true;// 验证当前数字是否符合所有提示for(int j = 0; j < n; j++) {// 生成当前猜测与谜底的提示string hint = generateHint(currentGuess, guesses[j]);// 如果提示不匹配，则当前数字不符合if(hint != hints[j]) {isValid = false;break;}}// 如果当前数字符合所有提示if(isValid){if(possibleAnswer.empty()) {possibleAnswer = currentGuess;}else {// 如果已经有一个符合的谜底，则不唯一，返回"NA"return "NA";}}}// 返回唯一的谜底或"NA"return possibleAnswer.empty() ? "NA" : possibleAnswer;
}// 定义生成提示的函数
string generateHint(string answer, string guess){int A = 0; // 数字正确且位置正确的个数int B = 0; // 数字正确但位置不对的个数// 标记已经匹配的数字vector<bool> answerUsed(4, false);vector<bool> guessUsed(4, false);// 先计算A值for(int i = 0; i < 4; i++) {if(answer[i] == guess[i]) {A += 1;answerUsed[i] = true;guessUsed[i] = true;}}// 再计算B值for(int i = 0; i < 4; i++) {if(!guessUsed[i]) {for(int j = 0; j < 4; j++) {if(!answerUsed[j] && guess[i] == answer[j]) {B += 1;answerUsed[j] = true;break;}}}}// 返回提示字符串return to_string(A) + "A" + to_string(B) + "B";
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

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