Đếm ô trong ma trận cho số Fibonacci khi cộng số ô lân cận trong C++

Cho ma trận [][ ] kích thước row x col. Mục tiêu: đếm số ô thỏa mãn điều kiện:

Giá trị ô matrix[i][j] + số ô lân cận = một số Fibonacci.

Dãy Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Hiểu qua ví dụ

Đầu vào: matrix[3][3] = {{1, 4, 1}, {2, 0, 1}, {5, 1, 1}}

Đầu ra: Số ô thỏa mãn: 4

Giải thích:

  0   1   2
0 1   4   1
1 2   0   1
2 5   1   1

• Ô(0,0): 1+2=3 (2 ô lân cận (1,0) và (0,1))
• Ô(0,2): 1+2=3
• Ô(1,0): 2+3=5
• Ô(2,2): 1+2=3

Đầu vào: matrix[3][3] = {{0,0,0}, {0, 1, 0}, {0, 0, 0}}

Đầu ra: Số ô thỏa mãn: 9

Giải thích: Tất cả 9 ô đều thỏa mãn.

Phương pháp sử dụng

Trong ma trận chỉ có 3 loại ô: ô góc (2 lân cận), ô cạnh (3 lân cận), ô giữa (4 lân cận). Cộng 2, 3 hoặc 4 vào giá trị ô và kiểm tra có phải số Fibonacci bằng hàm check_fibonacci(int num).

• Khởi tạo ma trận.
• Hàm check_square(long double num) kiểm tra bình phương hoàn hảo.
• Hàm check_fibonacci(int num): trả về true nếu check_square(5*num*num + 4) hoặc check_square(5*num*num - 4).
• Hàm Fibonacci_cells(int matrix[row][col]) trả về đếm.
• Khởi tạo count = 0.
• Duyệt i=0..row-1, j=0..col-1: total = matrix[i][j].
• Cộng 2/3/4 tùy vị trí ô.
• Nếu check_fibonacci(total) tăng count.
• Trả về count.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 
#define row 3 
#define col 3 

bool check_square(long double num) { 
    long double val = sqrt(num); 
    return ((val - floor(val)) == 0); 
} 

bool check_fibonacci(int num) { 
    return check_square(5 * num * num + 4) || check_square(5 * num * num - 4); 
} 

int Fibonacci_cells(int matrix[row][col]) { 
    int count = 0; 
    for (int i = 0; i < row; i++) { 
        for (int j = 0; j < col; j++) { 
            int total = matrix[i][j]; 
            if ((i == 0 && j == 0) || (i == row - 1 && j == 0) || (i == 0 && j == col - 1) || (i == row - 1 && j == col - 1)) { 
                total = total + 2; 
            } else if (i == 0 || j == 0 || i == row - 1 || j == col - 1) { 
                total = total + 3; 
            } else { 
                total = total + 4; 
            } 
            if (check_fibonacci(total)) count++; 
        } 
    } 
    return count; 
} 

int main() { 
    int matrix[row][col] = {{1, 4, 1}, {2, 0, 1}, {5, 1, 1}}; 
    cout << "Count of cells in a matrix which give a Fibonacci number when the count of adjacent cells is added are: " << Fibonacci_cells(matrix); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of cells in a matrix which give a Fibonacci number when the count of adjacent cells is added are: 4