กำหนดเมทริกซ์ [ ][ ] ที่มีมิติเป็น row x col เป้าหมายคือหาจำนวนเซลล์ของเมทริกซ์ที่ตรงตามเงื่อนไขที่กำหนด:
ค่าของเซลล์ matrix[i][j] + จำนวนเซลล์ติดกัน = เลขฟีโบนัชชี
ตัวเลขในอนุกรมฟีโบนัชชี: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
ทำความเข้าใจด้วยตัวอย่าง
ตัวอย่าง
Input - matrix[row][col] = {{1, 4, 1}, {2, 0, 1}, {5, 1, 1}}
Output - จำนวนเซลล์ในเมทริกซ์ที่บวกจำนวนเซลล์ติดกันแล้วได้เลขฟีโบนัชชีคือ: 4
คำอธิบาย
0 1 2
0 1 4 1
1 2 0 1
2 5 1 1
Cell(0,0) → 1+2=3 (2 เซลล์ติดกันคือ (1,0) และ (0,1))
Cell(0,2) → 1+2=3
Cell(1,0) → 2+3=5
Cell(2,2) → 1+2=3
Input - matrix[row][col] = {{0,0,0}, {0, 1, 0}, {0, 0, 0}}
Output - จำนวนเซลล์ในเมทริกซ์ที่บวกจำนวนเซลล์ติดกันแล้วได้เลขฟีโบนัชชีคือ: 9
คำอธิบาย
0 1 2
0 0 0 0
1 0 1 0
2 0 0 0
Cell(0,0) → 0+2=2 (2 เซลล์ติดกัน (1,0) และ (0,1)) เหมือนกัน (0,2), (2,2), (2,0)
Cell(0,1) → 0+3=3 (3 เซลล์ติดกัน (0,0), (0,2), (1,1)) เหมือนกัน (1,0), (1,2), (2,1)
Cell(1,1) → 1+4=5
เซลล์ทั้ง 9 ตัวถูกนับ
แนวทางที่ใช้ในโปรแกรมด้านล่าง
ในเมทริกซ์แบบใดก็ตาม จะมีเพียงสามประเภทของเซลล์เท่านั้น เซลล์มุมจะมีเซลล์ติดกัน 2 ตัว เซลล์ขอบมี 3 ตัว และเซลล์ภายในมี 4 ตัว บวก 2, 3 หรือ 4 เข้ากับค่าของเซลล์เหล่านี้และตรวจสอบว่าผลรวมเป็นเลขฟีโบนัชชีหรือไม่โดยใช้ฟังก์ชัน check_fibonacci(int num)
- รับเมทริกซ์[][] และเริ่มต้นค่า
- ฟังก์ชัน check_square(long double num) รับตัวเลขและคืนค่า true ถ้าเป็น perfect square
- ฟังก์ชัน check_fibonacci(int num) คืนค่า true ถ้า num เป็นเลขฟีโบนัชชี
- ถ้า check_square(5 * num * num + 4) || check_square(5 * num * num - 4) คืนค่า true แล้ว num เป็นเลขฟีโบนัชชี
- ฟังก์ชัน Fibonacci_cells(int matrix[row][col]) คืนค่าจำนวนเซลล์ในเมทริกซ์ที่บวกจำนวนเซลล์ติดกันแล้วได้เลขฟีโบนัชชี
- ตั้งค่า count เริ่มต้นเป็น 0
- วนลูป for จาก i = 0 ถึง i < row และ j = 0 ถึง j < col รับ total = matrix[i][j]
- บวก 2, 3 หรือ 4 เข้า total ตามเซลล์ติดกันของมัน
- ถ้า total ใหม่เป็นเลขฟีโบนัชชี check_fibonacci(total) จะคืนค่า true เพิ่ม count
- ในท้ายที่สุดของ for loops ทั้งหมด คืนค่า count เป็นผลลัพธ์
ตัวอย่าง
#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;
}
หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้
ผลลัพธ์
Count of cells in a matrix which give a Fibonacci number when the count of adjacent cells is added are: 4
