รู้จัก Pisano Period ตัวช่วยทำโจทย์ Fibonacci

2024-12-19 728 words 4 minutes

Contents

ทุกคนที่ได้เรียนเขียนโปรแกรมคงคุ้นเคยกับโจทย์หาค่าของ Fibonacci ตำแหน่งที่ i ซึ่งมีสูตรการคำนวณดังนี้ f_i = f_i-1 + f_i-2 โดยที่ f₀ = 0 และ f₁ = 1

ซึ่งสามารถเขียนโปรแกรมออกมาได้หลายรูปแบบที่พบบ่อยคงเป็นการเขียนด้วยวิธีวนซ้ำแบบ (Recursive) ดังตัวอย่างด้านล่าง

def fibonacci(i):
    if i == 0:
        return 0
    elif i == 1:
        return 1
    else:
        return fibonacci(i - 1) + fibonacci(i - 2)

รูปด้านล่างแสดงตัวอย่างค่าของ Fibonacci ณ ตำแหน่งที่ i ตั้งแต่ 0 (ซ้าย) ถึง 10 (ขวา) (f₀ = 0, f₁ = 1, f₂ = 1, f₃ = 2, f₄ = 3, f₅ = 5, f₆ = 8, f₇ = 13, f₈ = 21, f₉ = 34 และ f₁₀ = 55)

แล้วอะไรคือ Pisano Period มีความเกี่ยวข้องอย่างไรกับ Fibonacci

Pisano Period¹ แทนด้วยสัญญาลักษณ์ π หรือในรูป π(n) เมื่อต้องการหาค่า Pisano Period ที่ n ใดๆ โดยค่า Pisano Period ที่ n คือค่าที่บ่งบอกว่าเศษของ Fibonacci ที่หารด้วย n จะซ้ำกันทุกๆกี่ค่า

เช่น π(2) มีค่าเท่ากับ 3 เพราะว่า เมื่อนำค่า Fibonacci ณ ตำแหน่งใดๆ หารด้วย 2 พบว่าเศษของการหารด้วย 2 จะได้ค่าเศษที่ซ้ำกันทุกๆ 3 ครั้ง คือ 0, 1, 1 ไปเรื่อยๆ

ตัวอย่างการคำนวณหาค่า Pisano Period เมื่อ n มีค่าเท่ากับ 2

เมื่อต้องการคำนวณค่า Pisano Period เมื่อ n = 2 เขียนได้ในรูป π(2)

เริ่มต้นด้วยการคำนวณค่าของ Fibonacci ณ ตำแหน่งที่ 0 (ซ้าย) ถึง 8 (ขวา) ได้ผลลัพธ์ดังนี้
คำนวณเศษของการหารด้วย n (ในกรณีนี้ n = 2) กับค่าของ Fibonacci (ในข้อที่ 1) ณ ตำแหน่งที่ 0 (ซ้าย) ถึง 8 (ขวา)
ผลลัพท์การหาคำนวณเศษของการหาร Fibonacci ด้วย 2 (จากข้อที่ 2) ซึ่งเศษของการหารซ้ำกันทุกๆ 3 ค่า คือ 0, 1, 1 เพราะฉะนั้นค่าของ π(2) คือ 3

ตารางแสดงค่า Pisano Period เมื่อ n เท่ากับ 1 ถึง 10 ดังนี้ ²

n	π(n)	ค่าเศษที่เป็นไปได้ เมื่อหารด้วย n
1	1	0
2	1	011
3	3	0112 0221
4	6	011231
5	20	01123 03314 04432 02241
6	24	011235213415 055431453251
7	16	01123516 06654261
8	12	011235 055271
9	24	011235843718 088764156281
10	60	011235831459437 077415617853819 099875279651673 033695493257291

ตัวอย่างโปรแกรมในการหาค่า Pisano Period ในภาษา Python

จากตารางด้านบนสังเกตได้ว่าเศษจากการหารด้วย n ใดก็ตามเริ่มต้นด้วย 0 และ 1 เสมอ เพราะว่าเมื่อใช้ n มาหารกับค่า Fibbonacci ณ ตำแหน่งที่ 0 และ 1 (f₀ = 0 และ f₁ = 1) หารด้วย n ใดก็ตาม จะได้เศษเป็น 0 และ 1 ตามลำดับ

เราจึงสามารถคำนวณหาค่าเศษของการหารด้วย n ของ Fibonacci ณ ตำแหน่งที่ i และ i+1 เมื่อมีค่า 0 และ 1 เพื่อบอกตำแหน่งที่ค่าเศษของการหารวนกลับมาซ้ำกัน ซึ่งสามารถเขียนโปรแกรมออกมาดังตัวอย่างด้านล่าง

def pisano_period(n):
    if n == 1:
        # special case: Pisano period for n=1 is 1
        return 1  

    # f(0) % n = 0
    # f(1) % n = 1
    f_i_mod_n, f_i_plus_1_mod_n = 0, 1
    for i in range(2, n * n + 1):
        
        # f(i) is a f(i+1) from previous iteration
        # f(i) mod n = f(i-1) mod n
        #
        # f(i+1) is a f(i) and f(i+1) from previous iteration modulo by n 
        # f(i+1) mod n = (f(i-1) mod n + f(i)) mod n
        #
        # eg. n=2, 
        #   when i = 2;
        #       f(2) mod 2 = 0, 
        #       f(2+1) mod 2 = 1
        #   when i = 3
        #       f(3) mod 2 = 1, 
        #       f(4) mod 2 = (f(2) mod 2 + f(3) mod 2) mod 2 = 0 + 1 mod 2 = 1
        f_i_mod_n, f_i_plus_1_mod_n = f_i_plus_1_mod_n, (f_i_mod_n + f_i_plus_1_mod_n) % n

        # exit condition: when remaining remainder at f(i) is 0 and f(i+1) is 1
        if f_i_mod_n == 0 and f_i_plus_1_mod_n == 1:
            # repeat remainder f(i) = 0 and f(i+1) = 1, found Pisano period
            return i - 1

แล้วค่า Pisano Period ช่วยทำโจทย์ Fibonacci อย่างไร

สำหรับโจทย์การคำนวณหาเลขกี่หลักสุดท้ายของค่า Fibonacci ณ ตำแหน่งใดๆ สามารถใช้คุณสมบัติของ Pisano Period ที่ n มาช่วยในการลดการคำนวณได้

เช่น Pisano Period เมื่อ n มีค่าเท่ากับ 10 เพื่อใช้ในการคำนวณเลขหลักสุดท้ายของค่า Fibonacci ณ ตำแหน่งใดๆ (หรือ f_i mod 10) โดย π(10) บอกถึงจำนวนเศษของที่วนกลับมาซ้ำกัน หากรู้จำนวนเลขที่วนซ้ำกลับมาซ้ำกันแล้ว ทำให้ไม่จำเป็นต้องคำนวณค่า Fibonacci ณ ตำแหน่งที่ต้องการ แต่คำนวณค่า Fibbonacci ถึงค่า π(10) ก็สามารถหาคำตอบของเลขหลักสุดท้าย ณ ตำแหน่งที่ต้องการได้

ค่าของ π(10) คือ 60 แสดงว่าค่า Fibonacci ณ ตำแหน่งใดๆ หารด้วย 10 จะได้เศษซ้ำกันทุกๆ 60 ค่า คือ 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1 ใช้คุณสมบัติการซ้ำกันทุกๆ 60 ค่า มาใช้ในการหาเลขหลักสุดท้ายของค่า Fibonacci ณ ตำแหน่งใดๆ ตามตัวอย่างด้านล่าง

ตัวอย่าง

ต้องการหาค่า f₆₁ mod 10 เท่ากับการหาค่า f₁ mod 10 มีค่าเท่ากับ 1
ต้องการหาค่า f_1000000 mod 10 เท่ากับการหาค่า F₄₀ mod 10 มีค่าเท่ากับ 5

การโปรแกรมของการหาเลขหลักสุดท้ายของค่า Fibonacci ณ ตำแหน่งใดๆ ในภาษา Python ดังตัวอย่างด้านล่าง

def last_digit_fibonacci(i):
    remaining_cycle = [
        0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 
        0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 
        0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 
        0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1
    ]
    return remaining_cycle[i % 60]