ការស្វែងរកហ្វីបូណាឆី

បច្ចេកទេសស្វែងរកប្រៀបធៀបដែលប្រើលេខហ្វីបូណាឆីដើម្បីបែងចែកអារេទៅជាផ្នែកមិនស្មើ។ វាស្រដៀងនឹងការស្វែងរកគោលពីរប៉ុន្តែបែងចែកអារេដោយប្រើលេខហ្វីបូណាឆីជំនួសឱ្យបែងចែកពាក់កណ្តាល។

Visualization

Step 1 / 4

Speed:

Details

Analogy

ស្រមៃថាស្វែងរកសៀវភៅលើធ្នើ ប៉ុន្តែជំនួសឱ្យបែងចែកធ្នើពាក់កណ្តាលរៀងរាល់ពេល (ការស្វែងរកគោលពីរ) អ្នកបែងចែកវាតាមសមាមាត្រមាស (ប្រហែល 0.618)។ នេះគឺជាអ្វីដែលការស្វែងរកហ្វីបូណាឆីធ្វើ - វាប្រើលេខហ្វីបូណាឆី ដែលប្រហាក់ប្រហែលសមាមាត្រមាស ដើម្បីកំណត់ទីតាំងបន្ទាប់។

Purpose

ដើម្បីស្វែងរកអារេដែលបានតម្រៀបយ៉ាងមានប្រសិទ្ធភាពដោយប្រើលេខហ្វីបូណាឆីសម្រាប់ការបែងចែក។ វាពិសេសមានប្រយោជន៍នៅពេលតម្លៃនៃប្រតិបត្តិការចែកមានតម្លៃថ្លៃ ព្រោះវាប្រើតែបូក និងដក។ ក្បួនដោះស្រាយផ្អែកលើវិធីសាស្ត្របែងចែក-ជំនះ។

Use Cases

មានប្រយោជន៍លើប្រព័ន្ធដែលប្រតិបត្តិការចែក ឬគុណមានតម្លៃថ្លៃ (ប្រព័ន្ធបង្កប់ ដំណើរការចាស់)។ ល្អសម្រាប់សំណុំទិន្នន័យធំដែលរក្សាទុកក្នុងអង្គចងចាំយឺត (ខ្សែអាត់ ថាស) ដែលការចូលដំណើរការតាមលំដាប់ត្រូវបានពេញចិត្ត។ ប្រើក្នុងក្បួនដោះស្រាយហិរញ្ញវត្ថុដែលពាក់ព័ន្ធនឹងលំដាប់ហ្វីបូណាឆីតាមធម្មជាតិ។

Algorithm Steps

Line 1

fib2 = 0, fib1 = 1, fib = 1

while fib < n:

fib2 = fib1; fib1 = fib; fib = fib1 + fib2

offset = -1

while fib > 1:

i = min(offset + fib2, n-1)

if arr[i] < target: offset = i; fib = fib1; fib1 = fib2; fib2 = fib - fib1

elif arr[i] > target: fib = fib2; fib1 = fib1 - fib2; fib2 = fib - fib1

else: return i

if fib1 and arr[offset+1] == target: return offset+1

return -1

Current

Executed

Pending

Explanation

What's Happening?

Step 1/4

អារេដែលបានតម្រៀបដំបូង: [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]។ ចាប់ផ្តើមការស្វែងរកហ្វីបូណាឆីជាមួយជួរស្វែងរក [0, 10]។

Updates with each step • Clickfor full view

Code Implementation

def fibonacci_search(arr, target):
    n = len(arr)
    fib2, fib1 = 0, 1
    fib = fib2 + fib1

    while fib < n:
        fib2 = fib1
        fib1 = fib
        fib = fib2 + fib1

    offset = -1

    while fib > 1:
        i = min(offset + fib2, n - 1)

        if arr[i] < target:
            fib = fib1
            fib1 = fib2
            fib2 = fib - fib1
            offset = i
        elif arr[i] > target:
            fib = fib2
            fib1 = fib1 - fib2
            fib2 = fib - fib1
        else:
            return i

    if fib1 and offset + 1 < n and arr[offset + 1] == target:
        return offset + 1

    return -1