NOIP基础算法(C++)-模拟算法例题3-神奇的幻方
NOIP基础算法(C++)-模拟算法例题3-神奇的幻方:
【题目描述】 幻方是一种很神奇的N*N矩阵：它由数字 1,2,3,......,N×N构成，且每行、每列及两条 对角线上的数字之和都相同。 当 N 为奇数时，我们可以通过下方法构建一个幻方： 首先将 1写在第一行的中间。 之后，按如下方式从小到大依次填写每个数 K(K=2,3,...,N×N): 1.若 (K-1)(在第一行但不在最后一列，则将 K 填在最后一行，(K-1)所在列的右一列； 2.若 (K-1) 在最后一列但不在第一行，则将 K填在第一列，(K-1) 所在行的上一行； 3.若 (K-1)在第一行最后一列，则将 K填在 (K-1) 的正下方； 4.若 (K-1) 既不在第一行，也最后一列，如果 (K-1)的右上方还未填数，则将K填在 (K-1) 的右上方，否则将 L填在(K-1) 的正下方。 现给定N，请按上述方法构造 N×N的幻方 输入格式： 一个正整数N，即幻方的大小。 输出格式： 共N行，每行N个整数，即按上述方法构造出的N*N幻方，相邻两个整数之间用单空格隔开。 输入样例： 3 输出样例： 8 1 6 3 5 7 4 9 2
方法一：
#include <iostream>
#include <vector>
using namespace std;
// 生成幻方的函数
vector<vector<int> > generateMagicSquare(int n) {
// 创建一个大小为N×N的二维向量，初始值都为0
vector<vector<int> > magicSquare(n, vector<int>(n, 0));
int row = 0; // 当前行的索引
int col = n / 2; // 当前列的索引
// 将数字1放在第一行的中间位置
magicSquare[row][col] = 1;
// 依次填充数字2到N×N
for (int num = 2; num <= n * n; num++) {
// 检查(K-1)的位置
if (magicSquare[(row - 1 + n) % n][(col + 1) % n] == 0) {
// 如果(K-1)的右上方还未填充数字，则将K放在右上方
row = (row - 1 + n) % n;
col = (col + 1) % n;
} else {
// 否则将K放在(K-1)的正下方
row = (row + 1) % n;
}
// 填充数字K
magicSquare[row][col] = num;
}
return magicSquare;
}
int main() {
int n;
cin >> n; // 读取输入的n
// 生成幻方
vector<vector<int> > magicSquare = generateMagicSquare(n);
// 打印幻方
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << magicSquare[i][j] << " ";
}
cout << endl;
}
return 0;
}这段代码首先定义了一个函数generateMagicSquare，该函数接受一个整数n作为参数，返回一个N×N的幻方，其中N为输入的n的值。
在generateMagicSquare函数中，我们首先创建一个大小为N×N的二维向量magicSquare，并将其所有元素初始化为0。
接下来，我们使用两个变量row和col来追踪当前要填充的位置。我们将数字1放在第一行的中间位置，即row = 0和col = n / 2。然后，我们按照题目描述的规则填充剩余的数字。具体而言，对于数字K（从2到N×N），我们检查(K-1)的位置，并根据规则决定将K放置在哪个位置。如果(K-1)的右上方还未填充数字，则将K放在右上方，否则将K放在(K-1)的正下方。
最后，我们在main函数中读取输入的n，调用generateMagicSquare函数生成幻方，并将其打印出来。
请注意，这段代码假设输入的n是一个正整数，并且不会进行输入验证。在实际应用中，应该添加适当的输入验证和错误处理机制。
方法二：
#include <iostream>
using namespace std;
// 生成幻方的函数
int** generateMagicSquare(int n) {
// 创建一个大小为N×N的二维动态数组，初始值都为0
int** magicSquare = new int*[n];
for (int i = 0; i < n; i++) {
magicSquare[i] = new int[n];
for (int j = 0; j < n; j++) {
magicSquare[i][j] = 0;
}
}
int row = 0; // 当前行的索引
int col = n / 2; // 当前列的索引
// 将数字1放在第一行的中间位置
magicSquare[row][col] = 1;
// 依次填充数字2到N×N
for (int num = 2; num <= n * n; num++) {
// 检查(K-1)的位置
if (magicSquare[(row - 1 + n) % n][(col + 1) % n] == 0) {
// 如果(K-1)的右上方还未填充数字，则将K放在右上方
row = (row - 1 + n) % n;
col = (col + 1) % n;
} else {
// 否则将K放在(K-1)的正下方
row = (row + 1) % n;
}
// 填充数字K
magicSquare[row][col] = num;
}
return magicSquare;
}
int main() {
int n;
cin >> n; // 读取输入的n
// 生成幻方
int** magicSquare = generateMagicSquare(n);
// 打印幻方
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << magicSquare[i][j] << " ";
}
cout << endl;
}
// 释放动态数组内存
for (int i = 0; i < n; i++) {
delete[] magicSquare[i];
}
delete[] magicSquare;
return 0;
}这段代码使用了动态数组代替了向量。在generateMagicSquare函数中，我们使用new运算符动态分配了一个大小为N×N的二维数组，并将所有元素初始化为0。在main函数中，我们也使用new运算符分配了幻方的动态数组。最后，记得在程序结束前使用delete运算符释放动态数组所占用的内存。
请注意，使用动态数组需要手动管理内存，并确保适当地释放分配的内存，以避免内存泄漏。
