网站开发 平均工资,wordpress更新缓存的插件,软件开发项目名称有哪些,海南百度首页广告华为OD机试 2024E卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试真题#xff08;Python/JS/C/C#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;私信哪吒#xff0c;备注华为OD#xff0c;加入华为OD刷题交流群#xff0c;… 华为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 数字 107。
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、说明
五、解题思路
为了求解这个问题我们需要生成输入的九个不同数字的所有排列组合并检查每个排列是否满足三阶积幻方的条件。具体步骤如下
读取输入使用 Scanner 读取九个不同的数字并存储在一个数组中。生成排列通过回溯算法生成所有可能的九个数字的排列组合。由于九个数字的全排列数量为 9! 362,880因此在时间允许的范围内这种方法是可行的。验证幻方条件 将排列的前九个数字放入 3×3 的格子中。计算每一行、每一列以及两条对角线的三个数字的乘积。检查这些乘积是否都相等。如果相等则该排列满足三阶积幻方的条件。 收集有效排列将所有满足条件的排列存储在一个列表中。排序根据题目要求对所有有效排列按升序进行排序。排序的规则是从第一个数字开始依次比较各个位置的数字大小。输出结果按排序后的顺序输出每个有效排列数字之间用空格分隔。
通过这种方法我们可以确保找到所有满足条件的排列并按照要求进行输出。
六、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 vectorint Permutation;// 全局变量用于存储所有有效的排列
vectorPermutation 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_setint 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在线答疑。
