用C++语言实现NxN数字旋转方阵的递归算法
时间: 2024-09-29 12:14:17 浏览: 21
在C++中,使用递归实现N x N数字矩阵顺时针旋转可以分为两步:首先将第一行复制到其他所有行,然后逐行将每个元素向右移动一位直到移到最后一列。以下是递归函数的基本思路:
```cpp
void rotateMatrix(int matrix[N][N], int n, int start = 0) {
// 如果数组只剩一行或一列,无需旋转,直接返回
if (start >= n - 1) return;
// 将第一行复制到剩余每一行对应位置
for (int i = 0; i < n; ++i) {
matrix[start][i] = matrix[i][n - 1 - start];
}
// 递归地对剩下的矩阵进行旋转
rotateMatrix(matrix, n, start + 1);
}
// 调用函数,传入矩阵和其大小
void rotateMatrixRecursive(vector<vector<int>>& matrix, int n) {
rotateMatrix(matrix.data(), n); // 使用vector的data()获取原始数组
}
```
在这个例子中,`rotateMatrix()`是一个辅助函数,它接受一个矩阵、矩阵的大小以及当前处理行的位置。当开始位置超过(n-1),意味着我们已经完成了第一层的复制,然后递归地对下一层进行同样的操作。
相关问题
用C语言编写程序实现用C++语言实现NxN数字旋转方阵的递归算法
在C++中,我们可以使用递归来实现一个N x N数字矩阵的旋转操作。这里我们假设你要把矩阵顺时针旋转90度。下面是一个递归函数的例子:
```cpp
#include <iostream>
using namespace std;
// 递归函数,用于矩阵旋转
void rotateMatrix(int matrix[N][N], int n, int start, int end) {
if (start >= end) { // 当前块已经处理完毕,退出递归
return;
}
// 对当前块进行旋转
for (int i = start; i < end; ++i) {
int temp = matrix[start][i];
matrix[start][i] = matrix[end - 1 - i][start]; // 将最左边元素移到最右下边
matrix[end - 1 - i][start] = matrix[i][end - 1]; // 将最右边元素移到最左下边
matrix[i][end - 1] = matrix[end][end - 1 - i]; // 将最下边元素移到中间
matrix[end][end - 1 - i] = temp; // 将中间元素移到最上面
}
// 继续递归处理剩余部分(每两层之间的边界)
rotateMatrix(matrix, n, start + 1, end);
}
// 主函数测试
void printMatrix(int matrix[N][N], int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
int n = 4;
int matrix[n][n] = {1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16};
cout << "Original Matrix:\n";
printMatrix(matrix, n);
rotateMatrix(matrix, n, 0, n - 1); // 顺时针旋转90度
cout << "\nRotated Matrix:\n";
printMatrix(matrix, n);
return 0;
}
```
这个程序首先定义了一个`rotateMatrix` 函数,它接受一个N x N的矩阵和两个边界索引(start 和 end),然后逐层递归地旋转矩阵的局部部分。最后,在主函数中创建一个示例矩阵,并展示旋转前后的情况。
NxN方阵LU分解C语言实现
下面是一个简单的NxN方阵LU分解的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define N 3 // 方阵的大小
int main() {
int i, j, k;
double A[N][N] = {{1, 4, 7}, {2, 5, 8}, {3, 6, 10}}; // 输入矩阵
double L[N][N], U[N][N];
double sum;
// 初始化 L 和 U 矩阵
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (i == j) {
L[i][j] = 1;
} else {
L[i][j] = 0;
}
U[i][j] = 0;
}
}
// 进行 LU 分解
for (i = 0; i < N; i++) {
// 计算 U 矩阵的第 i 行
for (j = i; j < N; j++) {
sum = 0;
for (k = 0; k < i; k++) {
sum += L[i][k] * U[k][j];
}
U[i][j] = A[i][j] - sum;
}
// 计算 L 矩阵的第 i 列
for (j = i + 1; j < N; j++) {
sum = 0;
for (k = 0; k < i; k++) {
sum += L[j][k] * U[k][i];
}
L[j][i] = (A[j][i] - sum) / U[i][i];
}
}
// 输出 L 和 U 矩阵
printf("L = \n");
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
printf("%f ", L[i][j]);
}
printf("\n");
}
printf("U = \n");
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
printf("%f ", U[i][j]);
}
printf("\n");
}
return 0;
}
```
输出结果为:
```
L =
1.000000 0.000000 0.000000
2.000000 1.000000 0.000000
3.000000 2.000000 1.000000
U =
1.000000 4.000000 7.000000
0.000000 -3.000000 -6.000000
0.000000 0.000000 1.000000
```
其中,L矩阵的对角线元素都是1,其余元素是计算得到的下三角矩阵,U矩阵是计算得到的上三角矩阵。