算法
(暴力枚举)
这个C++程序的主要目标是判断如何将一个N×N的原始图案转换为目标图案。程序采用了暴力的方法,逐个尝试7种不同的转换方式,然后判断是否与目标图案相匹配。以下是程序的算法分析:
equals 函数: 这个函数用于比较两个图案是否相等。它通过遍历两个图案的每一个元素,判断是否相等。时间复杂度为 O(N^2),其中 N 是图案的大小。
revolve 函数: 该函数实现了将图案逆时针旋转90度的操作。它创建了一个临时数组 t,将旋转后的图案存储在 t 中,然后使用 memcpy 将 t 的内容复制回原始数组 a。因为这个操作只涉及一次遍历,所以时间复杂度为 O(N^2)。
reverse 函数: 该函数实现了沿中垂直线翻转图案的操作。对每一行的前一半元素与后一半元素进行交换。时间复杂度为 O(N^2)。
print 函数: 该函数用于输出图案,但在程序中并未被使用。
主函数 main: 主函数首先读取输入,包括图案的大小 N 和原始图案、目标图案的内容。然后,程序使用 7 种不同的转换方式逐一尝试,每尝试一种都会调用 equals 函数进行匹配。如果匹配成功,则输出对应的序号。整个主函数的时间复杂度为 O(7N^2)。
总体而言,这个程序虽然使用了一些比较简单的图案操作,但由于采用了暴力遍历的方式,因此算法复杂度较高。在这里,N 的范围是 1 到 10,因此算法的性能是可接受的。在更大的输入规模下,可能需要考虑一些优化的方法。
C++ 代码
#include<cstdio>
#include<cstring>
const int N = 12;
int n;
char a[N][N], b[N][N];
// 比较两个图案是否相等
bool equals() {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(a[i][j] != b[i][j]) return false;
return true;
}
// 顺时针旋转90度
void revolve() {
static char t[N][N];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
t[i][j] = a[n - j + 1][i];
memcpy(a, t, sizeof t);
}
// 沿中垂直线翻转图案
void reverse() {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n / 2; j++) {
char t = a[i][j];
a[i][j] = a[i][n - j + 1];
a[i][n - j + 1] = t;
}
}
// 输出图案(未被使用)
void print() {
for(int i = 1; i <= n; i++) puts(a[i] + 1); puts("");
}
int main() {
// 读取输入
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
for(int i = 1; i <= n; i++) scanf("%s", b[i] + 1);
// 逐一尝试不同的转换方式
revolve(); if(equals()) return puts("1"), 0;
revolve(); if(equals()) return puts("2"), 0;
revolve(); if(equals()) return puts("3"), 0;
revolve();
reverse(); if(equals()) return puts("4"), 0;
revolve(); if(equals()) return puts("5"), 0;
revolve(); if(equals()) return puts("5"), 0;
revolve(); if(equals()) return puts("5"), 0;
revolve();
reverse(); if(equals()) return puts("6"), 0;
// 如果没有匹配的转换方式,输出 7(无效转换)
puts("7");
return 0;
}