![[Bài 40] Ma Trận Xoắn Ốc](/storage/photos/1/cpp/ma-tran-xoan-oc.png "[Bài 40] Ma Trận Xoắn Ốc")
Trong bài viết này mình sẽ hướng dẫn các bạn cách xây dựng ma trận xoáy ốc trong lập trình c++.
1. Ma Trận Xoắn Ốc
Ma trận xoáy ốc (Spiral matrix) là một ma trận vuông có N dòng và N cột, các số trong ma trận được sắp xếp như một xoáy ốc gồm các số từ 1 tới N2.
Ma trận xoáy ốc cũng có thể là một ma trận không vuông có N dòng và M cột, các số trong ma trận được đánh số từ 1 tới N * M theo hình xoáy ốc
Ví dụ dưới đây là một ma trận xoáy ốc cỡ 5
Để xây dựng ma trận xoáy ốc thì ta tiến hành xây dựng từng vòng của xoáy ốc gồm 4 cạnh và lưu vào một mảng 2 chiều cỡ N x N
Ta duy trì 4 biến số :
- h1 : hàng trên của xoáy ốc
- h2 : hàng dưới của xoáy ốc
- c1 : cột trái của xoáy ốc
- c2 : cột phải của xoáy ốc
Ví dụ khi bạn xây dựng xoáy ốc ngoài cùng này thì h1, h2, c1, c2 sẽ có giá trị như sau :
Sau khi xây dựng xong vòng xoáy ốc ngoài cùng, ta sẽ tăng h1, giảm h2, tăng c1, giảm c2 để xây dựng vòng xoáy ốc tiếp theo
Code :
#include <math.h>
using namespace std;
int main() {
int n = 5;
int a[100][100];
int h1 = 0, h2 = n - 1, c1 = 0, c2 = n - 1;
int dem = 1;
while (h1 <= h2 && c1 <= c2) {
// Xây dựng cạnh trên : hàng h1 từ cột c1 => cột c2
for (int i = c1; i <= c2; i++) {
a[h1][i] = dem; ++dem;
}
// Tăng h1 để xây dựng cạnh bên phải, cột c2 từ hàng h1 tới hàng h2
++h1;
for (int i = h1; i <= h2; i++) {
a[i][c2] = dem;
++dem;
}
// giảm c2 để xây dựng cạnh dưới, hàng h2 từ c2 => cột c1
--c2;
for (int i = c2; i >= c1; i--) {
a[h2][i] = dem;
++dem;
}
// giảm h2 để xây dựng cạnh bên phải, cột c1 từ hàng h2 tới hàng h1
--h2;
for (int i = h2; i >= h1; i--) {
a[i][c1] = dem;
++dem;
}
// tăng c1
++c1;
}
cout << "Ma tran xoay oc co 5 : \n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
Output :
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
2. Ma Trận Xoắn Ốc Nguyên Tố
Ma trận xoáy ốc nguyên tố là ma trận xoáy ốc nhưng các số xuất hiện trong ma trận sẽ là các số nguyên tố từ nhỏ tới lớn.
Ví dụ ma trận xoáy ốc cỡ 5 thì bạn cần 25 số nguyên tố đầu tiên
Cách xây dựng ma trận xoáy ốc nguyên tố tương tự xây dựng ma trận xoáy ốc thường, ta cần chuẩn bị trước 1 số lượng số nguyên tố vừa đủ với số lượng phần tử trong ma trận xoáy ốc và gán lần lượt.
Code :
#include <math.h>
using namespace std;
bool nt(int n) {
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return n > 1;
}
int main() {
int n = 5;
int a[100][100];
int X[10000], idx = 0, i = 0;
while (idx < n * n) {
if (nt(i)) {
X[idx] = i;
++idx;
}
++i;
}
int h1 = 0, h2 = n - 1, c1 = 0, c2 = n - 1;
int dem = 0;
while (h1 <= h2 && c1 <= c2) {
for (int i = c1; i <= c2; i++) {
a[h1][i] = X[dem];
++dem;
}
++h1;
for (int i = h1; i <= h2; i++) {
a[i][c2] = X[dem];
++dem;
}
--c2;
for (int i = c2; i >= c1; i--) {
a[h2][i] = X[dem];
++dem;
}
--h2;
for (int i = h2; i >= h1; i--) {
a[i][c1] = X[dem];
++dem;
}
++c1;
}
cout << "Ma tran xoay oc nguyen to co 5 :\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
Output :
2 3 5 7 11
53 59 61 67 13
47 89 97 71 17
43 83 79 73 19
41 37 31 29 23
3. Ma Trận Xoắn Ốc Fibonacci
Ma trận xoáy ốc Fibonacci chứa các số lần lượt là các số trong dãy Fibonacci, bạn tiến hành xây dựng trước mảng các số Fibo và gán lần lượt cho ma trận xoáy ốc
Thông thường cỡ ma trận xoáy ốc Fibonacci không quá 9
Nếu bạn chưa biết dãy Fibonacci có thể tham khảo tại đây
Code :
#include <math.h>
using namespace std;
int main() {
int n = 4;
long long a[100][100];
long long F[100];
F[0] = 0;
F[1] = 1;
for (int i = 2; i < n * n; i++) {
F[i] = F[i - 1] + F[i - 2];
}
int h1 = 0, h2 = n - 1, c1 = 0, c2 = n - 1;
int dem = 0;
while (h1 <= h2 && c1 <= c2) {
for (int i = c1; i <= c2; i++) {
a[h1][i] = F[dem];
++dem;
}
++h1;
for (int i = h1; i <= h2; i++) {
a[i][c2] = F[dem];
++dem;
}
--c2;
for (int i = c2; i >= c1; i--) {
a[h2][i] = F[dem];
++dem;
}
--h2;
for (int i = h2; i >= h1; i--) {
a[i][c1] = F[dem];
++dem;
}
++c1;
}
cout << "Ma tran xoay oc Fibonacci co 4 : \n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
Output :
0 1 1 2
89 144 233 3
55 610 377 5
34 21 13 8
