iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 19
0

在討論費氏搜尋之前,要先了解一下費氏數列。

費氏數列 (Fibonacci numbers),又稱費波那契數列,是指在一串數字中,每一項是前兩項的和。數學上的定義為:

  • 第 0 項 = 0
  • 第 1 項 = 1
  • 第 n 項 = 第 n-1 項 + 第 n-2 項

公式為:f(n) = f(n-1) + f(n-2), n >= 2

直接列出前十項,觀察一下就能了解了。

f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] f[10]
0 1 1 2 3 5 8 13 21 34 55

用程式碼來寫一下,怎麼算出費氏數列。
時間複雜度為 O(2^n)

def fibonacci(n):
    if n == 0:
        return 0;
    elif n == 1:
        return 1;
    return fibonacci(n-1) + fibonacci(n-2)
    
print(fibonacci(7))

在大致了解費氏數列後,那費氏搜尋法又是如何運作呢?

假設我們要在已經排序好的數列中找到數字:
費氏數列 fib = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
查找資料 data = [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130]
搜尋值 key = 60

  1. 要事先算出費氏數列fib,費氏數列裡的值fib[i]會用來當作查找資料裡的索引值。
  2. 用查找資料的長度大小 len(data) = 11,和費氏數列的值做比較,找到費氏數列裡的值 fib[6] = 8,最接近小於或等於查找資料的長度大小 y = 6,代表查找資料這棵樹的根節點編號,也是費氏數列的索引值。
  3. 設定怎麼從查找資料跳著找。從資料索引的最大值減去 fib[y] = fib[6],m = 10 - 8 = 2
  4. 設定從費氏數列的第幾個索引開始找要給查找資料找數字的索引值。x = y - 1 = 5
  5. 如果查找資料在索引 5 處的值大於指定的搜尋值,則第一個搜尋位置就是索引 5 的位置,如果小於指定的搜尋值,則第一個搜尋位置必須加上 m,也就是 fib[5] + m = 5 + 2 = 7,也就是索引 7 的位置,其實加上 m 的原因,是為了要讓下一個搜尋值剛好是數列的最後一個位置。

(真的要用不同的資料多試幾次,才會慢慢了解查找的概念...真的蠻繞的,但只要了解,會發現速度很快)

import sys

# 產生費氏數列
def fibo(max):
    fib = [sys.maxsize] * max
    fib[0] = 0
    fib[1] = 1
    for i in range(2, max):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib

def getY(fib, n):
    i = 0
    while fib[i] <= n:
        i += 1
    return i - 1

def search(data, key):
    fib = fibo(len(data))
    max = len(data) - 1  # data的最大索引值
    y = getY(fib, max + 1) # 在費氏數列裡的值,如果比data的最大索引值還大,回傳費氏數列索引值的前一個
    m = max - fib[y] 
    x = y - 1  #找到在data搜尋的起始索引值
    print("\nx=%d, m=%d, fib[x]=%d" % (x, m, fib[x]))
    i = x
    if data[i] < key:
        i += m
    while fib[x] > 0:
        if data[i] < key:
            x -= 1
            i += fib[x]
        elif data[i] > key:
            x -= 1
            i -= fib[x]
        else:
            return i
    return -1

number = [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130]
find = search(number, 60)
print("找到數值於索引 " + str(find) if find >= 0 else "找不到數值")


上一篇
[演算法] 深度優先搜尋 (Depth-first Search)
下一篇
[演算法] 廣度優先搜尋 (Breadth-first Search)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言