การตรวจสอบเลขฟีโบนัชชี (Fibonacci Number Check)
เลข n เป็นฟีโบนัชชี ก็ต่อเมื่อ 5n² + 4 หรือ 5n² - 4 เป็น Perfect Square (จำนวนกำลังสองสมบูรณ์)
ตัวอย่างโค้ด
public class Demo {
// ตรวจสอบ Perfect Square
static boolean isPerfectSquare(int x) {
int s = (int) Math.sqrt(x);
return s * s == x;
}
// ตรวจสอบเลขฟีโบนัชชี
static boolean isFibonacci(int n) {
return isPerfectSquare(5 * n * n + 4)
|| isPerfectSquare(5 * n * n - 4);
}
public static void main(String[] args) {
System.out.println("ตรวจสอบเลข 6 ถึง 17:");
for (int i = 6; i <= 17; i++) {
System.out.println(i + (isFibonacci(i) ? " เป็นเลขฟีโบนัชชี" : " ไม่ใช่เลขฟีโบนัชชี"));
}
}
}
ผลลัพธ์
6 ไม่ใช่เลขฟีโบนัชชี 7 ไม่ใช่เลขฟีโบนัชชี 8 เป็นเลขฟีโบนัชชี 9 ไม่ใช่เลขฟีโบนัชชี 10 ไม่ใช่เลขฟีโบนัชชี 11 ไม่ใช่เลขฟีโบนัชชี 12 ไม่ใช่เลขฟีโบนัชชี 13 เป็นเลขฟีโบนัชชี 14 ไม่ใช่เลขฟีโบนัชชี 15 ไม่ใช่เลขฟีโบนัชชี 16 ไม่ใช่เลขฟีโบนัชชี 17 ไม่ใช่เลขฟีโบนัชชี
คำอธิบายทฤษฎี
คุณสมบัติทางคณิตศาสตร์: n เป็นฟีโบนัชชี ⟺ 5n²±4 เป็น perfect square
พิสูจน์มาจากสูตร Binet และคุณสมบัติของ continued fractions
ลำดับฟีโบนัชชี: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
การทดสอบตัวอย่าง
n=8: 5×64+4=324=18² ✓ -> Fibonacci n=13: 5×169+4=849 (ไม่ใช่ square), 5×169-4=841=29² ✓ -> Fibonacci n=21: 5×441+4=2209=47² ✓ -> Fibonacci
ข้อจำกัดของ int
5 * n * n overflow ได้เร็ว (n > ~20,000)
// ใช้ long
static boolean isPerfectSquareLong(long x) {
long s = (long) Math.sqrt(x);
return s * s == x;
}
static boolean isFibonacciLong(long n) {
return isPerfectSquareLong(5 * n * n + 4)
|| isPerfectSquareLong(5 * n * n - 4);
}
// หรือ BigInteger สำหรับเลขใหญ่มาก
static boolean isFibonacciBig(BigInteger n) {
BigInteger five = BigInteger.valueOf(5);
BigInteger four = BigInteger.valueOf(4);
BigInteger n2 = n.multiply(n);
return isPerfectSquareBig(five.multiply(n2).add(four))
|| isPerfectSquareBig(five.multiply(n2).subtract(four));
}
วิธีอื่น: Iterative Generation
// สร้างฟีโบนัชชีจนเกิน n แล้วเช็ค
static boolean isFibonacciIterative(int n) {
if (n < 0) return false;
int a = 0, b = 1;
while (b < n) {
int temp = a + b;
a = b;
b = temp;
}
return b == n || n == 0;
}
การประยุกต์ใช้
- อัลกอริทึมคอมพิวเตอร์ (Fibonacci Heap, Search)
- คณิตศาสตร์ ทฤษฎีจำนวน
- การสร้าง Procedural Generation (เกม, กราฟิก)
- Financial modeling (Fibonacci retracement)
