一、问题描述
幻方修复问题
题目描述
幻方（Magic Square）是一个由 1~N²，共 N² 个整数构成的 N×N 矩阵，满足每行、列和对角线上的数字和相等。
上回你已经帮助小明将写错一个数字的幻方进行了修复，小明在感谢之余也想进一步试试你的水平，于是他准备了有两个数字发生了位置交换的幻方。
你可以把这两个交换的数字找出来并且改正吗？
输入描述
- 第一行输入一个整数 N，代表带校验幻方的阶数（3 ≤ N ＜ 50）。
- 接下来的 N 行，每行 N 个整数，空格隔开（1 ≤ 每个整数 ≤ N²）。
输出描述
- 输出两行，代表两条纠正信息。
- 每行包含三个整数，分别是：出错行号、出错列号、应填入的数字（末尾无空格）。
- 注意：先输出行号小的，若行号相同则先输出列号小的。
用例
示例输入
3
8 1 9
3 5 7
4 6 2
示例输出
1 3 6
3 2 9
题目解析
解决该问题需要结合幻方的特性以及一些数学规律，以下详细介绍解题思路。
幻方特性
幻方中每一条直线上的数的和叫作 幻和。公式如下：
幻和 = 所有数的和 ÷ 阶数
- 每行、列以及两条对角线上的数字和均为幻和。
- 如果将幻方中两个数字交换，其行、列和对角线的和将不再符合幻和。
解题思路
1. 计算幻和
通过公式计算幻和：
幻和 = (N² × (N² + 1) / 2) ÷ N
- N² × (N² + 1) / 2 是 1~N² 的总和。
- 将总和除以阶数 N，得到幻和。
2. 找出行和与列和不符合幻和的行和列
遍历每行和每列，计算其和，记录所有不满足幻和的行和列。
- 如果某一行的和 ≠ 幻和，则该行可能存在错误。
- 如果某一列的和 ≠ 幻和，则该列可能存在错误。
3. 区分错误类型
幻方可能出现以下三种错误情况：
-
两个交换的数字在不同的行和列中
- 即两行和两列的和都与幻和不符。
- 错误的两行和两列的交点是可能的错误位置。
-
两个交换的数字在同一行中
- 即所有行的和均符合幻和，但有两个列的和不符。
- 错误的两列中的所有行交点是可能的错误位置。
-
两个交换的数字在同一列中
- 即所有列的和均符合幻和，但有两行的和不符。
- 错误的两行中的所有列交点是可能的错误位置。
4. 尝试复原幻方
对于每种错误类型，在可能的错误位置中进行两点组合，尝试交换两点的数值。
- 如果交换后满足幻方的所有行、列和对角线的和均为幻和，则找到了正确的两点。
5. 特殊情况
-
两个交换的数字同时出现在对角线上
- 特别是主对角线或副对角线。
- 需要验证对角线和是否符合幻和。
-
边界问题
- 确保行号和列号均从 1 开始，而非从 0 开始。
示例分析
示例输入
- N = 3
- 输入矩阵：
8 1 9
3 5 7
4 6 2
解题步骤
-
计算幻和
( 幻和 = \frac{(3^2 \times (3^2 + 1) / 2)}{3} = 15 ) -
找出不符合幻和的行和列
- 第 1 行和 = (8 + 1 + 9 = 18)（错误）。
- 第 3 行和 = (4 + 6 + 2 = 12)（错误）。
- 第 2 列和 = (1 + 5 + 6 = 12)（错误）。
- 第 3 列和 = (9 + 7 + 2 = 18)（错误）。
-
确定可能的错误点
- 错误点可能在：
- 第 1 行第 3 列（数值为 9）
- 第 3 行第 2 列（数值为 6）
- 错误点可能在：
-
交换验证
- 交换 (9) 和 (6) 后：
-
新矩阵为：
8 1 6 3 5 7 4 9 2 -
每行和、每列和以及对角线和均为 15，满足幻方要求。
-
- 交换 (9) 和 (6) 后：
-
输出结果
- 错误点 1：第 1 行第 3 列，改为 6。
- 错误点 2：第 3 行第 2 列，改为 9。
示例输出
1 3 6
3 2 9
不同阶数幻方示例
四阶幻方
输入矩阵：
4
1 8 11 14
12 13 2 7
6 3 16 9
15 10 5 4
五阶幻方
输入矩阵：
5
2 23 16 10 14
20 9 12 3 21
13 1 25 19 7
24 17 8 11 5
6 15 4 22 18
六阶幻方
输入矩阵：
6
21 23 4 1 32 30
22 24 2 3 31 29
28 27 17 18 9 12
25 26 19 20 11 10
8 6 34 36 13 14
7 5 35 33 15 16
七阶幻方
输入矩阵：
7
46 15 40 9 34 3 28
21 39 8 33 2 27 45
38 14 32 1 26 44 20
13 31 7 25 43 19 37
30 6 24 49 18 36 12
5 23 48 17 42 11 29
22 47 16 41 10 35 4
八阶幻方
输入矩阵：
8
64 2 62 4 5 59 7 57
9 55 11 53 52 14 50 16
48 18 46 20 21 43 23 41
25 39 27 37 36 30 34 32
33 31 35 29 28 38 26 40
24 42 22 44 45 19 47 17
49 15 51 13 12 54 10 56
8 58 6 60 61 3 63 1
九阶幻方
输入矩阵：
9
47 58 69 80 1 12 23 34 45
57 68 79 9 11 22 33 44 46
67 78 8 10 21 32 43 54 56
77 7 18 20 31 42 53 55 66
6 17 19 30 41 52 63 65 76
16 27 29 40 51 62 64 75 5
26 28 39 50 61 72 74 4 15
36 38 49 60 71 73 3 14 25
37 48 59 70 81 2 13 24 35
十阶幻方
输入矩阵：
10
92 99 1 8 15 67 74 51 58 40
98 80 7 14 16 73 55 57 64 41
4 81 88 20 22 54 56 63 70 47
85 87 19 21 3 60 62 69 71 28
86 93 25 2 9 61 68 75 52 34
17 24 76 83 90 42 49 26 33 65
23 5 82 89 91 48 30 32 39 66
79 6 13 95 97 29 31 38 45 72
10 12 94 96 78 35 37 44 46 53
11 18 100 77 84 36 43 50 27 59
二、JavaScript算法源码
以下是对代码的详细注释和讲解，力求让每一步逻辑都清晰且容易理解。
代码分解与详细讲解
1. 基础输入与初始化
javascript>javascript">const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
let n, matrix, magic_sum;
- 使用
readline模块来读取控制台输入。 - 定义
lines数组存储每一行输入。 - 定义
n表示幻方的阶数，matrix表示整个幻方矩阵，magic_sum表示幻和。
2. 输入数据处理
javascript>javascript">rl.on("line", (line) => {lines.push(line);if (lines.length == 1) {n = lines[0] - 0; // 第一个输入是幻方的阶数}if (n && lines.length == n + 1) {lines.shift(); // 去掉第一行阶数matrix = lines.map((line) => line.split(" ").map(Number)); // 将剩下的每一行转为数字矩阵getResult(); // 调用主函数进行幻方修复lines.length = 0; // 处理完成后清空输入}
});
- 监听每一行输入，将其存储到
lines中。 - 当
lines的长度等于n + 1（阶数行 + 矩阵行数），触发处理逻辑：- 移除第一行阶数信息。
- 将输入的矩阵转换为二维数字数组。
- 调用
getResult()函数开始解题逻辑。
3. 主逻辑函数：getResult
3.1 计算幻和
javascript>javascript">function getResult() {magic_sum = 0; // 初始化幻和for (let i = 0; i < n; i++) {for (let j = 0; j < n; j++) magic_sum += matrix[i][j]; // 累加整个矩阵的所有数字}magic_sum /= n; // 幻和 = 总和 ÷ 阶数
}
- 遍历整个矩阵，计算所有数字的总和。
- 将总和除以阶数
n，得到幻和magic_sum。
3.2 记录不正确的行和列
javascript>javascript"> const rows = [];const cols = [];for (let row = 0; row < n; row++) {if (getRowSum(row) != magic_sum) rows.push(row); // 如果行和不等于幻和，记录该行号}for (let col = 0; col < n; col++) {if (getColSum(col) != magic_sum) cols.push(col); // 如果列和不等于幻和，记录该列号}
- 遍历每一行和每一列：
- 如果某一行的和不等于幻和，记录其行号到
rows数组。 - 如果某一列的和不等于幻和，记录其列号到
cols数组。
- 如果某一行的和不等于幻和，记录其行号到
3.3 特殊情况处理
javascript>javascript"> if (rows.length == 0) {for (let i = 0; i < n; i++) rows.push(i); // 如果所有行都正确，则可能是在同一行中交换，记录所有行号}if (cols.length == 0) {for (let i = 0; i < n; i++) cols.push(i); // 如果所有列都正确，则可能是在同一列中交换，记录所有列号}
- 如果没有发现错误的行，说明交换的两个数字位于同一行，可能出现在任何行中。
- 如果没有发现错误的列，说明交换的两个数字位于同一列，可能出现在任何列中。
3.4 生成可能的错误点坐标
javascript>javascript"> const positions = [];for (let row of rows) {for (let col of cols) positions.push([row, col]); // 行和列的笛卡尔积，生成所有可能的错误点}
- 将所有可能出错的行和列进行笛卡尔积，生成可能的错误点坐标。
3.5 遍历可能的错误点组合，尝试修复
javascript>javascript"> for (let i = 0; i < positions.length; i++) {for (let j = i + 1; j < positions.length; j++) {if (isValid(positions[i], positions[j])) return; // 如果找到正确的交换位置，直接返回}}
}
- 组合错误点的所有可能两点组合。
- 对每一对点调用
isValid函数，尝试交换并验证幻方是否正确。
4. 验证函数：isValid
4.1 获取交换点并交换值
javascript>javascript">function isValid(pos1, pos2) {const [x1, y1] = pos1;const [x2, y2] = pos2;let tmp = matrix[x1][y1];matrix[x1][y1] = matrix[x2][y2];matrix[x2][y2] = tmp;
- 获取两个可能出错点的坐标。
- 交换这两个点的值。
4.2 验证幻方是否正确
javascript>javascript"> let ans = getDiagonalSum1() == magic_sum && getDiagonalSum2() == magic_sum;if (ans) {for (let r = 0; r < n; r++) {if (getRowSum(r) != magic_sum) {ans = false;break;}}}if (ans) {for (let c = 0; c < n; c++) {if (getColSum(c) != magic_sum) {ans = false;break;}}}
- 验证主对角线和副对角线是否等于幻和。
- 验证所有行和是否等于幻和。
- 验证所有列和是否等于幻和。
4.3 输出结果或复原
javascript>javascript"> if (ans) {if (x1 * n + y1 < x2 * n + y2) {console.log(`${x1 + 1} ${y1 + 1} ${matrix[x1][y1]}`);console.log(`${x2 + 1} ${y2 + 1} ${matrix[x2][y2]}`);} else {console.log(`${x2 + 1} ${y2 + 1} ${matrix[x2][y2]}`);console.log(`${x1 + 1} ${y1 + 1} ${matrix[x1][y1]}`);}} else {tmp = matrix[x1][y1];matrix[x1][y1] = matrix[x2][y2];matrix[x2][y2] = tmp;}return ans;
}
- 如果验证通过，输出修复后的坐标和对应值。
- 如果验证失败，复原两点的值，继续尝试其他组合。
5. 辅助函数
5.1 行和计算
javascript>javascript">function getRowSum(r) {let sum = 0;for (let c = 0; c < n; c++) {sum += matrix[r][c];}return sum;
}
- 累加某一行的所有元素，返回行和。
5.2 列和计算
javascript>javascript">function getColSum(c) {let sum = 0;for (let r = 0; r < n; r++) {sum += matrix[r][c];}return sum;
}
- 累加某一列的所有元素，返回列和。
5.3 对角线和计算
javascript>javascript">function getDiagonalSum1() {let sum = 0;for (let i = 0; i < n; i++) {sum += matrix[i][i];}return sum;
}function getDiagonalSum2() {let sum = 0;for (let i = 0; i < n; i++) {sum += matrix[i][n - 1 - i];}return sum;
}
- 分别计算主对角线（左上到右下）和副对角线（右上到左下）的和。
总结
-
核心逻辑：
- 找到错误的行和列。
- 生成错误点的坐标。
- 尝试交换并验证幻方的正确性。
-
特点：
- 代码逻辑清晰，逐步推进。
- 通过幻方特性减少搜索空间。
-
注意事项：
- 坐标从 1 开始输出（而非从 0）。
- 确保复原交换值，避免影响后续验证。
三、Java算法源码
代码讲解
1. 主函数结构
java">public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt(); // 读取幻方的阶数matrix = new int[n][n]; // 初始化幻方矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = sc.nextInt(); // 读取矩阵中的数字magic_sum += matrix[i][j]; // 累加所有数字，计算总和}}magic_sum /= n; // 幻和 = 矩阵总和 ÷ 阶数getResult(); // 开始进行错误修复
}
-
输入处理：
- 使用
Scanner读取控制台输入。 n表示幻方的阶数，matrix是存储幻方的二维数组。
- 使用
-
幻和计算：
- 幻和（
magic_sum）是矩阵所有数字的总和除以阶数 ( n )。 - 这是幻方的核心特性，即每行、每列和每条对角线的和都等于幻和。
- 幻和（
-
调用修复逻辑：
- 输入处理完成后，调用
getResult()函数，开始检查并修复幻方。
- 输入处理完成后，调用
2. 获取修复结果
2.1 寻找不正确的行和列
java">public static void getResult() {// 记录 和不正确的行ArrayList<Integer> rows = new ArrayList<>();// 记录 和不正确的列ArrayList<Integer> cols = new ArrayList<>();// 检查每行的和是否等于幻和for (int row = 0; row < n; row++) {if (getRowSum(row) != magic_sum) {rows.add(row); // 记录不正确的行号}}// 检查每列的和是否等于幻和for (int col = 0; col < n; col++) {if (getColSum(col) != magic_sum) {cols.add(col); // 记录不正确的列号}}
- 记录错误行和列：
- 遍历每一行和每一列，检查其总和是否等于幻和。
- 如果某行的和不等于幻和，将该行号存入
rows。 - 如果某列的和不等于幻和，将该列号存入
cols。
2.2 特殊情况处理
java"> // 两点处于同一行，不同列if (rows.size() == 0) {// 如果所有行都正确，则两点的行坐标可能是任意一行for (int i = 0; i < n; i++) rows.add(i);}// 两点处于同一列，不同行if (cols.size() == 0) {// 如果所有列都正确，则两点的列坐标可能是任意一列for (int i = 0; i < n; i++) cols.add(i);}
- 行或列完全正确的特殊情况：
- 如果
rows为空，则说明所有行的和均正确，交换的两个数字可能在同一行。 - 如果
cols为空，则说明所有列的和均正确，交换的两个数字可能在同一列。 - 在这两种情况下，所有行或列都需要加入可能的错误位置。
- 如果
2.3 生成可能的错误坐标
java"> // 行号 x 列号，就可以组合出坐标ArrayList<int[]> positions = new ArrayList<>();for (Integer row : rows) {for (Integer col : cols) {positions.add(new int[] {row, col});}}
- 生成坐标：
- 将所有错误行和列的组合生成坐标点。
- 这些坐标点是可能发生错误的数字位置。
2.4 遍历尝试交换
java"> // 组合两点，尝试交换for (int i = 0; i < positions.size(); i++) {for (int j = i + 1; j < positions.size(); j++) {if (isValid(positions.get(i), positions.get(j))) return;}}
}
- 两点组合：
- 遍历所有可能的坐标点组合。
- 对每一对点调用
isValid()，尝试交换并验证幻方是否符合要求。
3. 验证是否符合幻方
3.1 获取并交换值
java">public static boolean isValid(int[] pos1, int[] pos2) {int x1 = pos1[0], y1 = pos1[1];int x2 = pos2[0], y2 = pos2[1];// 交换两个点的值int tmp = matrix[x1][y1];matrix[x1][y1] = matrix[x2][y2];matrix[x2][y2] = tmp;
- 交换两点的值：
- 交换两个可能出错点的值，进行验证。
3.2 验证行、列和对角线
java"> boolean ans = magic_sum == getDiagonalSum1() && magic_sum == getDiagonalSum2();if (ans)for (int r = 0; r < n; r++) {if (getRowSum(r) != magic_sum) {ans = false;break;}}if (ans)for (int c = 0; c < n; c++) {if (getColSum(c) != magic_sum) {ans = false;break;}}
-
验证对角线：
- 检查主对角线和副对角线是否等于幻和。
-
验证行和列：
- 遍历所有行和列，检查其和是否等于幻和。
3.3 输出或复原
java"> if (ans) {if (x1 * n + y1 < x2 * n + y2) {System.out.println((x1 + 1) + " " + (y1 + 1) + " " + matrix[x1][y1]);System.out.println((x2 + 1) + " " + (y2 + 1) + " " + matrix[x2][y2]);} else {System.out.println((x2 + 1) + " " + (y2 + 1) + " " + matrix[x2][y2]);System.out.println((x1 + 1) + " " + (y1 + 1) + " " + matrix[x1][y1]);}} else {// 否则复原交换位置tmp = matrix[x1][y1];matrix[x1][y1] = matrix[x2][y2];matrix[x2][y2] = tmp;}return ans;
}
-
成功验证：
- 如果交换后验证通过，输出两个点的坐标和修复后的值。
- 按照坐标的字典序（行号优先，其次列号）输出。
-
验证失败：
- 如果验证失败，复原交换的值。
4. 辅助函数
行和计算
java">public static int getRowSum(int r) {int sum = 0;for (int c = 0; c < n; c++) sum += matrix[r][c];return sum;
}
- 计算第
r行的所有数字之和。
列和计算
java">public static int getColSum(int c) {int sum = 0;for (int r = 0; r < n; r++) sum += matrix[r][c];return sum;
}
- 计算第
c列的所有数字之和。
对角线和计算
java">public static int getDiagonalSum1() {int sum = 0;for (int i = 0; i < n; i++) {sum += matrix[i][i];}return sum;
}
- 计算主对角线（左上到右下）的和。
java">public static int getDiagonalSum2() {int sum = 0;for (int i = 0; i < n; i++) {sum += matrix[i][n - 1 - i];}return sum;
}
- 计算副对角线（右上到左下）的和。
总结
-
整体逻辑：
- 通过幻方特性（每行、列、对角线的和相等），逐步定位并修复问题。
-
关键优化：
- 利用错误行列生成可能的错误点，大幅减少搜索空间。
-
注意事项：
- 输出时行号和列号从 1 开始（人类习惯），而非从 0 开始（编程习惯）。
- 确保在验证失败时复原交换值，避免影响后续尝试。
四、Python算法源码
代码讲解
1. 输入处理与初始化
python">n = int(input()) # 读取幻方的阶数
matrix = [list(map(int, input().split())) for _ in range(n)] # 构建幻方矩阵
- 输入处理：
- 使用
input()读取阶数n。 - 使用列表解析读取
n行的矩阵数据，并将每一行转换为整数列表。
- 使用
2. 辅助函数
2.1 对角线和计算
python">def getDiagonalSum1():total = 0for i in range(n):total += matrix[i][i] # 左上到右下return totaldef getDiagonalSum2():total = 0for i in range(n):total += matrix[i][n - 1 - i] # 右上到左下return total
- 主对角线和（左上到右下） 和 副对角线和（右上到左下） 的计算。
2.2 行和列和计算
python">def getRowSum(r):return sum(matrix[r]) # 计算第 r 行的和def getColSum(c):total = 0for r in range(n):total += matrix[r][c] # 计算第 c 列的和return total
- 行和：直接使用
sum函数计算某一行的总和。 - 列和：累加某一列各元素的值，得出总和。
2.3 坐标解析
python">def getPos(pos):x = pos // ny = pos % nreturn [x, y]
- 将一维索引转换为二维坐标。虽然此函数在当前代码中未被使用，但在某些情况下可以用于根据单个索引计算行列坐标。
3. 验证与交换逻辑
python">def isValid(pos1, pos2, magic_sum):x1, y1 = pos1x2, y2 = pos2# 交换两个点的值matrix[x1][y1], matrix[x2][y2] = matrix[x2][y2], matrix[x1][y1]# 验证所有行、列、对角线的和是否为幻和ans = magic_sum == getDiagonalSum1() and magic_sum == getDiagonalSum2()if ans:for r in range(n):if getRowSum(r) != magic_sum:ans = Falsebreakif ans:for c in range(n):if getColSum(c) != magic_sum:ans = Falsebreak# 如果正确，输出结果if ans:if pos1 < pos2:print(f"{x1 + 1} {y1 + 1} {matrix[x1][y1]}")print(f"{x2 + 1} {y2 + 1} {matrix[x2][y2]}")else:print(f"{x2 + 1} {y2 + 1} {matrix[x2][y2]}")print(f"{x1 + 1} {y1 + 1} {matrix[x1][y1]}")else:# 复原交换位置matrix[x1][y1], matrix[x2][y2] = matrix[x2][y2], matrix[x1][y1]return ans
- 交换和验证：
- 将
pos1和pos2位置上的值交换。 - 验证整个矩阵的行、列和对角线是否满足幻和。
- 如果满足，按顺序输出交换的位置和对应的数值。
- 如果不满足，复原交换的值。
- 将
4. 主逻辑：修复幻方
python">def getResult():# 计算幻和magic_sum = sum(sum(row) for row in matrix) / n# 记录可能出错的行和列rows = [r for r in range(n) if getRowSum(r) != magic_sum]cols = [c for c in range(n) if getColSum(c) != magic_sum]# 特殊情况下，行或列全正确，假设交换在同一行或列if len(rows) == 0:rows = list(range(n))if len(cols) == 0:cols = list(range(n))# 生成所有可能错误的坐标点positions = [(r, c) for r in rows for c in cols]# 检查所有可能的两点组合for i in range(len(positions)):for j in range(i + 1, len(positions)):if isValid(positions[i], positions[j], magic_sum):return
- 计算幻和：计算并确定幻和的值。
- 记录异常行和列：将不等于幻和的行和列记录下来。
- 特殊情况处理：如果所有行或列都正确，则假设交换发生在同一行或列的不同位置。
- 生成可能错误的坐标：通过行和列的组合生成所有可能的错误坐标。
- 验证与修复：通过所有可能的两点组合，调用
isValid验证和修复幻方。
总结
- 通过逐步分析幻方的特性，利用行、列、对角线的和判断错误位置。
- 通过坐标组合及交换逻辑验证和修复幻方。
- 输出结果时，注意格式化输出坐标（从 1 开始）及对应的数值。
- 代码逻辑紧凑，利用 Python 的列表解析和函数功能使得代码清晰且简洁。
五、C/C++算法源码：
C++ 代码
#include <iostream>
#include <vector>using namespace std;// 声明全局变量
int n;
vector<vector<int>> matrix;// 求对角线的和（右上，到左下）
int getDiagonalSum2() {int total = 0;for (int i = 0; i < n; ++i) {total += matrix[i][n - 1 - i];}return total;
}// 求对角线的和（左上，到右下）
int getDiagonalSum1() {int total = 0;for (int i = 0; i < n; ++i) {total += matrix[i][i];}return total;
}// 求对应列的和
int getColSum(int c) {int total = 0;for (int r = 0; r < n; ++r) {total += matrix[r][c];}return total;
}// 求对应行的和
int getRowSum(int r) {int total = 0;for (int c = 0; c < n; ++c) {total += matrix[r][c];}return total;
}// 判断两个位置是否有效交换
bool isValid(pair<int, int> pos1, pair<int, int> pos2, int magic_sum) {int x1 = pos1.first, y1 = pos1.second;int x2 = pos2.first, y2 = pos2.second;// 交换两个点的值swap(matrix[x1][y1], matrix[x2][y2]);// 判断两个对角线和是否等于幻和bool ans = (magic_sum == getDiagonalSum1() && magic_sum == getDiagonalSum2());// 判断每一行的和是否相等if (ans) {for (int r = 0; r < n; ++r) {if (getRowSum(r) != magic_sum) {ans = false;break;}}}// 判断每一列的和是否相等if (ans) {for (int c = 0; c < n; ++c) {if (getColSum(c) != magic_sum) {ans = false;break;}}}if (ans) {if (x1 * n + y1 < x2 * n + y2) {cout << x1 + 1 << " " << y1 + 1 << " " << matrix[x1][y1] << endl;cout << x2 + 1 << " " << y2 + 1 << " " << matrix[x2][y2] << endl;} else {cout << x2 + 1 << " " << y2 + 1 << " " << matrix[x2][y2] << endl;cout << x1 + 1 << " " << y1 + 1 << " " << matrix[x1][y1] << endl;}} else {// 复原swap(matrix[x1][y1], matrix[x2][y2]);}return ans;
}// 主函数，进行幻方修复
void getResult() {// 计算幻和int magic_sum = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {magic_sum += matrix[i][j];}}magic_sum /= n;// 记录 和不正确的行vector<int> rows;// 记录 和不正确的列vector<int> cols;// 检查每一行for (int row = 0; row < n; ++row) {if (getRowSum(row) != magic_sum) {rows.push_back(row);}}// 检查每一列for (int col = 0; col < n; ++col) {if (getColSum(col) != magic_sum) {cols.push_back(col);}}// 两点处于同一行，不同列if (rows.empty()) {for (int i = 0; i < n; ++i) rows.push_back(i);}// 两点处于同一列，不同行if (cols.empty()) {for (int i = 0; i < n; ++i) cols.push_back(i);}// 组合出所有可能的错误点坐标vector<pair<int, int>> positions;for (int r : rows) {for (int c : cols) {positions.emplace_back(r, c);}}// 尝试所有组合进行交换for (size_t i = 0; i < positions.size(); ++i) {for (size_t j = i + 1; j < positions.size(); ++j) {if (isValid(positions[i], positions[j], magic_sum)) {return;}}}
}int main() {// 输入获取cin >> n;matrix.resize(n, vector<int>(n));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cin >> matrix[i][j];}}// 调用算法getResult();return 0;
}
C++ 代码讲解
-
输入与初始化：
- 读取矩阵阶数
n和幻方矩阵matrix。 - 使用
vector动态数组来存储矩阵。
- 读取矩阵阶数
-
辅助函数：
getDiagonalSum1和getDiagonalSum2用于计算主对角线与副对角线的和。getRowSum和getColSum计算指定行或列的和。
-
修复逻辑：
isValid函数检查两个给定坐标点是否可以通过交换恢复幻方结构。getResult函数确定幻方错误的位置，并通过组合可能错误坐标进行交换尝试。
-
输出：
- 输出修复后正确的交换点坐标和对应的数值。
C 语言代码
#include <stdio.h>
#include <stdbool.h>// 声明全局变量
int n;
int matrix[100][100]; // 假设 n 不会超过 100// 求对角线的和（右上，到左下）
int getDiagonalSum2() {int total = 0;for (int i = 0; i < n; ++i) {total += matrix[i][n - 1 - i];}return total;
}// 求对角线的和（左上，到右下）
int getDiagonalSum1() {int total = 0;for (int i = 0; i < n; ++i) {total += matrix[i][i];}return total;
}// 求对应列的和
int getColSum(int c) {int total = 0;for (int r = 0; r < n; ++r) {total += matrix[r][c];}return total;
}// 求对应行的和
int getRowSum(int r) {int total = 0;for (int c = 0; c < n; ++c) {total += matrix[r][c];}return total;
}// 判断两个位置是否有效交换
bool isValid(int x1, int y1, int x2, int y2, int magic_sum) {// 交换两个点的值int tmp = matrix[x1][y1];matrix[x1][y1] = matrix[x2][y2];matrix[x2][y2] = tmp;// 判断两个对角线和是否等于幻和bool ans = (magic_sum == getDiagonalSum1() && magic_sum == getDiagonalSum2());// 判断每一行的和是否相等if (ans) {for (int r = 0; r < n; ++r) {if (getRowSum(r) != magic_sum) {ans = false;break;}}}// 判断每一列的和是否相等if (ans) {for (int c = 0; c < n; ++c) {if (getColSum(c) != magic_sum) {ans = false;break;}}}if (ans) {if (x1 * n + y1 < x2 * n + y2) {printf("%d %d %d\n", x1 + 1, y1 + 1, matrix[x1][y1]);printf("%d %d %d\n", x2 + 1, y2 + 1, matrix[x2][y2]);} else {printf("%d %d %d\n", x2 + 1, y2 + 1, matrix[x2][y2]);printf("%d %d %d\n", x1 + 1, y1 + 1, matrix[x1][y1]);}} else {// 复原tmp = matrix[x1][y1];matrix[x1][y1] = matrix[x2][y2];matrix[x2][y2] = tmp;}return ans;
}// 主函数，进行幻方修复
void getResult() {// 计算幻和int magic_sum = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {magic_sum += matrix[i][j];}}magic_sum /= n;// 记录 和不正确的行int rows[100], rowCount = 0;// 记录 和不正确的列int cols[100], colCount = 0;// 检查每一行for (int row = 0; row < n; ++row) {if (getRowSum(row) != magic_sum) {rows[rowCount++] = row;}}// 检查每一列for (int col = 0; col < n; ++col) {if (getColSum(col) != magic_sum) {cols[colCount++] = col;}}// 两点处于同一行，不同列if (rowCount == 0) {for (int i = 0; i < n; ++i) rows[rowCount++] = i;}// 两点处于同一列，不同行if (colCount == 0) {for (int i = 0; i < n; ++i) cols[colCount++] = i;}// 尝试所有组合进行交换for (int i = 0; i < rowCount; ++i) {for (int j = 0; j < colCount; ++j) {for (int k = i + 1; k < rowCount; ++k) {for (int l = j + 1; l < colCount; ++l) {if (isValid(rows[i], cols[j], rows[k], cols[l], magic_sum)) {return;}}}}}
}int main() {// 输入获取scanf("%d", &n);for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {scanf("%d", &matrix[i][j]);}}// 调用算法getResult();return 0;
}
C 语言代码讲解
-
输入与初始化：
- 读取矩阵阶数
n和幻方矩阵matrix。 - 使用二维数组
matrix存储幻方数据，假设最大为 100x100。
- 读取矩阵阶数
-
辅助函数：
getDiagonalSum1和getDiagonalSum2用于计算主对角线与副对角线的和。getRowSum和getColSum计算指定行或列的和。
-
修复逻辑：
isValid函数检查两个给定坐标点是否可以通过交换恢复幻方结构。getResult函数确定幻方错误的位置，并通过组合可能错误坐标进行交换尝试。
-
输出：
- 输出修复后正确的交换点坐标和对应的数值。
这两个版本的代码使用了与 Python 代码相似的逻辑，通过 C++ 和 C 语言的特性实现了幻方修复算法。需要注意，在 C 语言中，我们需要手动管理数组的大小，而在 C++ 中使用了 vector 可以自动调整大小。
六、尾言
什么是华为OD？
华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。
为什么刷题很重要？
-
机试是进入技术面的第一关：
华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。 -
技术面试需要手撕代码：
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。 -
入职后的可信考试：
入职华为后，还需要通过“可信考试”。可信考试分为三个等级：- 入门级：主要考察基础算法与编程能力。
- 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。
刷题策略与说明：
2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：
-
关注历年真题：
- 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。
-
适应新题目：
- E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。
-
掌握常见算法：
华为OD考试通常涉及以下算法和数据结构：- 排序算法（快速排序、归并排序等）
- 动态规划（背包问题、最长公共子序列等）
- 贪心算法
- 栈、队列、链表的操作
- 图论（最短路径、最小生成树等）
- 滑动窗口、双指针算法
-
保持编程规范：
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言，如C++、Java、Python等。
如何获取资源？
-
官方参考：
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
-
加入刷题社区：
- 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
- 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。
-
寻找系统性的教程：
- 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程，例如数据结构与算法的在线课程。
积极心态与持续努力：
刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。
考试注意细节
-
本地编写代码
- 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。
-
调整心态，保持冷静
- 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。
-
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。
-
快捷键使用
- 删除行可用
Ctrl+D，复制、粘贴和撤销分别为Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。 - 避免使用
Ctrl+S，以免触发浏览器的保存功能。
- 删除行可用
-
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。
-
交卷相关
- 答题前，务必仔细查看题目示例，避免遗漏要求。
- 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
- 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。
-
时间和分数安排
- 总时间：150 分钟；总分：400 分。
- 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。
-
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
- 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。
-
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。
祝你考试顺利，取得理想成绩！
