华为OD机试 - 九宫格游戏（Python/JS/C/C++ 2024 E卷 100分）

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

专栏导读

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

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

一、题目描述

九宫格是一款广为流传的游戏，起源于河图洛书。

游戏规则 Q 是：1到9的九个数字放在3×3的格子中，要求每行、每列以及两个对角线上的三数之和都等于15。

在金庸名著《射雕英雄传》中黄蓉曾给 九宫格 Q 的一种解法，口诀：戴九履一，左三右七，二四肩背，八六为足，五居中央。解法如图所示。

现在有一种新的玩法，给九个 不同的 Q 数字，将这九个数字放在3×3的格子中，要求每行、每列以及两个对角线上的三数之积相等（三阶积幻方）。其中一个三阶幻方如图：

解释：每行、每列以及两个对角线上的三数之积相等，其为216，该示例的每个三数积均为216，满足三阶积幻方的要求。排列后的九个数字中：第1-3个数字为方格的第一行，第4-6个数字为方格的第二行，第7-9个数字为方格的第三行。

二、输入描述

九个不同的数字，每个数字之间用空格分开。

0 < 数字 < 10⁷。

0 排列后满足要求的每行，每列以及两个对角线上的三数之积 < 2^31-1。

三、输出描述

九个数字所有满足要求的排列，每个数字之间用空格分开。

每行输出一个满足要求的排列。

要求输出的排列升序排列，即：对于排列 A(A1,A2,A3…A9) 和排列 B(B1,B2,B3…B9)，从排列的第 1 个数字开始，遇到 Ai < Bi，则排列 A < 排列 B (1 <= i <= 9)。

说明：用例保证至少有一种排列组合满足条件。

四、测试用例

测试用例1：

1、输入

75 36 10 4 30 225 90 25 12

2、输出

10 36 75 225 30 4 12 25 90
10 225 12 36 30 25 75 4 90
12 25 90 225 30 4 10 36 75
12 225 10 25 30 36 90 4 75
75 4 90 36 30 25 10 225 12
75 36 10 4 30 225 90 25 12
90 4 75 25 30 36 12 225 10
90 25 12 4 30 225 75 36 10

3、说明

五、解题思路

为了求解这个问题，我们需要生成输入的九个不同数字的所有排列组合，并检查每个排列是否满足三阶积幻方的条件。具体步骤如下：

1. 读取输入：使用 Scanner 读取九个不同的数字，并存储在一个数组中。
2. 生成排列：通过回溯算法生成所有可能的九个数字的排列组合。由于九个数字的全排列数量为 9! = 362,880，因此在时间允许的范围内，这种方法是可行的。
3. 验证幻方条件：
   • 将排列的前九个数字放入 3×3 的格子中。
   • 计算每一行、每一列以及两条对角线的三个数字的乘积。
   • 检查这些乘积是否都相等。如果相等，则该排列满足三阶积幻方的条件。
4. 收集有效排列：将所有满足条件的排列存储在一个列表中。
5. 排序：根据题目要求，对所有有效排列按升序进行排序。排序的规则是从第一个数字开始，依次比较各个位置的数字大小。
6. 输出结果：按排序后的顺序输出每个有效排列，数字之间用空格分隔。

通过这种方法，我们可以确保找到所有满足条件的排列，并按照要求进行输出。

六、Python算法源码

import sys
from itertools import permutationsdef is_valid(grid):"""检查当前排列是否满足三阶积幻方的条件"""# 计算第一行的乘积作为基准target = grid[0] * grid[1] * grid[2]# 检查每一行的乘积for i in range(3):row_product = grid[3*i] * grid[3*i +1] * grid[3*i +2]if row_product != target:return False# 检查每一列的乘积for i in range(3):col_product = grid[i] * grid[i +3] * grid[i +6]if col_product != target:return False# 检查两条对角线的乘积diag1 = grid[0] * grid[4] * grid[8]diag2 = grid[2] * grid[4] * grid[6]if diag1 != target or diag2 != target:return Falsereturn Truedef main():# 读取输入并转换为整数列表input_numbers = list(map(int, sys.stdin.read().strip().split()))# 检查输入是否有且仅有9个数字if len(input_numbers) != 9:print("输入必须包含九个不同的数字。")return# 使用集合检查数字是否互不相同if len(set(input_numbers)) != 9:print("输入的数字必须互不相同。")returnvalid_perms = []  # 用于存储所有有效的排列# 生成所有排列并检查每个排列是否有效for perm in permutations(input_numbers):if is_valid(perm):valid_perms.append(perm)# 对所有有效排列进行排序valid_perms.sort()# 输出所有有效的排列for perm in valid_perms:print(' '.join(map(str, perm)))if __name__ == "__main__":main()

七、JavaScript算法源码

const readline = require('readline');// 创建接口以读取标准输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});// 读取输入
let input = '';rl.on('line', (line) => {input += line;
}).on('close', () => {// 将输入转换为数字数组const numbers = input.trim().split(/\s+/).map(Number);// 检查输入是否有且仅有9个数字if (numbers.length !== 9) {console.log("输入必须包含九个不同的数字。");process.exit(0);}// 检查数字是否互不相同const uniqueNumbers = new Set(numbers);if (uniqueNumbers.size !== 9) {console.log("输入的数字必须互不相同。");process.exit(0);}const validPerms = []; // 用于存储所有有效的排列// 生成所有排列的函数function permute(arr, l, r) {if (l === r) {if (isValid(arr)) {validPerms.push([...arr]);}return;}for (let i = l; i <= r; i++) {[arr[l], arr[i]] = [arr[i], arr[l]]; // 交换permute(arr, l + 1, r);[arr[l], arr[i]] = [arr[i], arr[l]]; // 交换回来}}// 检查当前排列是否满足三阶积幻方的条件function isValid(grid) {// 计算第一行的乘积作为基准const target = grid[0] * grid[1] * grid[2];// 检查每一行的乘积for (let i = 0; i < 3; i++) {const rowProduct = grid[3*i] * grid[3*i +1] * grid[3*i +2];if (rowProduct !== target) return false;}// 检查每一列的乘积for (let i = 0; i < 3; i++) {const colProduct = grid[i] * grid[i +3] * grid[i +6];if (colProduct !== target) return false;}// 检查两条对角线的乘积const diag1 = grid[0] * grid[4] * grid[8];const diag2 = grid[2] * grid[4] * grid[6];if (diag1 !== target || diag2 !== target) return false;return true;}// 生成所有排列permute(numbers, 0, numbers.length -1);// 对所有有效排列进行排序validPerms.sort((a, b) => {for (let i = 0; i < 9; i++) {if (a[i] !== b[i]) return a[i] - b[i];}return 0;});// 输出所有有效的排列validPerms.forEach(perm => {console.log(perm.join(' '));});
});

八、C算法源码

#include <stdio.h>
#include <stdlib.h>// 定义一个结构体用于存储排列
typedef struct {int arr[9];
} Permutation;// 全局变量用于存储所有有效的排列
Permutation validPerms[362880];
int count = 0;// 交换函数
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 检查当前排列是否满足三阶积幻方的条件
int isValid(int grid[]) {// 计算第一行的乘积作为基准long long target = (long long)grid[0] * grid[1] * grid[2];// 检查每一行的乘积for(int i = 0; i < 3; i++) {long long rowProduct = (long long)grid[3*i] * grid[3*i +1] * grid[3*i +2];if(rowProduct != target) return 0;}// 检查每一列的乘积for(int i = 0; i < 3; i++) {long long colProduct = (long long)grid[i] * grid[i +3] * grid[i +6];if(colProduct != target) return 0;}// 检查两条对角线的乘积long long diag1 = (long long)grid[0] * grid[4] * grid[8];long long diag2 = (long long)grid[2] * grid[4] * grid[6];if(diag1 != target || diag2 != target) return 0;return 1;
}// 生成所有排列并检查有效性
void permute(int *arr, int l, int r) {if(l == r) {if(isValid(arr)) {// 将当前有效的排列添加到validPerms中for(int i = 0; i < 9; i++) {validPerms[count].arr[i] = arr[i];}count++;}return;}for(int i = l; i <= r; i++) {swap(&arr[l], &arr[i]);          // 交换permute(arr, l +1, r);           // 递归swap(&arr[l], &arr[i]);          // 交换回来}
}// 比较两个排列，用于排序
int compare(const void *a, const void *b) {Permutation *pa = (Permutation *)a;Permutation *pb = (Permutation *)b;for(int i = 0; i < 9; i++) {if(pa->arr[i] != pb->arr[i]) {return pa->arr[i] - pb->arr[i];}}return 0;
}int main(){int numbers[9];// 读取九个不同的数字for(int i = 0; i < 9; i++) {if(scanf("%d", &numbers[i]) != 1){printf("输入必须包含九个不同的数字。\n");return 0;}}// 检查数字是否互不相同for(int i = 0; i < 9; i++) {for(int j = i +1; j < 9; j++) {if(numbers[i] == numbers[j]){printf("输入的数字必须互不相同。\n");return 0;}}}// 生成所有排列并检查有效性permute(numbers, 0, 8);// 使用快速排序对所有有效排列进行排序qsort(validPerms, count, sizeof(Permutation), compare);// 输出所有有效的排列for(int i = 0; i < count; i++) {for(int j = 0; j < 9; j++) {printf("%d", validPerms[i].arr[j]);if(j != 8) printf(" ");}printf("\n");}return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;// 定义一个类型用于存储排列
typedef vector<int> Permutation;// 全局变量用于存储所有有效的排列
vector<Permutation> validPerms;// 交换函数（C++内置swap已足够，无需自定义）// 检查当前排列是否满足三阶积幻方的条件
bool isValid(const Permutation &grid) {// 计算第一行的乘积作为基准long long target = (long long)grid[0] * grid[1] * grid[2];// 检查每一行的乘积for(int i = 0; i < 3; i++) {long long rowProduct = (long long)grid[3*i] * grid[3*i +1] * grid[3*i +2];if(rowProduct != target) return false;}// 检查每一列的乘积for(int i = 0; i < 3; i++) {long long colProduct = (long long)grid[i] * grid[i +3] * grid[i +6];if(colProduct != target) return false;}// 检查两条对角线的乘积long long diag1 = (long long)grid[0] * grid[4] * grid[8];long long diag2 = (long long)grid[2] * grid[4] * grid[6];if(diag1 != target || diag2 != target) return false;return true;
}int main(){ios::sync_with_stdio(false);cin.tie(0);Permutation numbers(9);// 读取九个不同的数字for(int i = 0; i < 9; i++) {cin >> numbers[i];}// 检查数字是否互不相同unordered_set<int> uniqueNumbers(numbers.begin(), numbers.end());if(uniqueNumbers.size() != 9){// 输入的数字不互不相同，退出return 0;}// 生成所有排列并检查有效性sort(numbers.begin(), numbers.end());do {if(isValid(numbers)) {validPerms.push_back(numbers);}} while(next_permutation(numbers.begin(), numbers.end()));// 对所有有效排列进行排序（已按字典序排列，无需再次排序）// 但为了确保，进行一次排序sort(validPerms.begin(), validPerms.end());// 输出所有有效的排列for(auto &perm : validPerms) {for(int i = 0; i < 9; i++) {cout << perm[i];if(i != 8) cout << ' ';}cout << '\n';}return 0;
}

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

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

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