[精讚] [會員登入]
412

[VB.NET] 費式數列的2種解法 [遞迴 + 記憶法]

記憶法(Memoization) 將計算的結果保存起來,以備下次遇到同樣問題時使用。

分享此文連結 //n.sfs.tw/15613

分享連結 [VB.NET] 費式數列的2種解法 [遞迴 + 記憶法]@大塚 宏 ~認真玩・輕鬆學~
(文章歡迎轉載,務必尊重版權註明連結來源)
2022-03-01 09:14:19 最後編修
2022-02-25 13:32:30 By 大塚 宏
 

自動目錄

前言

本文開始前,先簡單介紹一下費式數列。以下列出費式數列的前15項內容。
1、1、2、3、5、8、13、21、34、55、89、144、233、377、610
可以發現,除了前兩項固定為1,之後的數列都是前面兩個數字相加
例如
F(3) = F(1) + F(2) = 1+1 = 2
F(5) = F(3) + F(4) = 2+3 = 5
本篇將使用"遞迴"方式,讓程式可以計算出指定的費式數列。

方式一(遞迴)

使用function,自己呼叫自己的方式,即為遞迴
遞迴(Recursion)
是指在函式中使用函式自身的方法。遞迴函式必須有終止條件,才能被計算。
 
遞迴是什麼? 舉例如下
Function add(x As Integer)
    If x = 1 Then
        Return 1
    Else
        Return add(x - 1) + 1
    End If
End Function
先宣告一個函式add(x)
可以看出函式內部,一直在呼叫add自己,直到x=1時才會Return 1(停止呼叫自己,"x=1"為終止條件)
實際上呼叫此函式時,比方說Msgbox(add(3)),就會看到提示視窗顯示「3」
這是因為:
add(3)會執行Return add(3-1)+1 
add(2)會執行Return add(2-1)+1
add(1)會執行Return 1 
由最後的add(1),逆推回去add(3),會發現其實Return add(3)等同於Return 1+1+1,因此回傳「3」
這就是遞迴的基本應用。

 

至於應用在費式數列當中,寫法則為:
Function Fibo(x As Integer)
    If x <= 2 Then '費式數列前兩項都是1
        Return 1
    Else
        Return Fibo(x - 1) + Fibo(x - 2)
    End If
End Function
這個程式碼,單純依賴人腦去逆推比較困難,因此我將計算過程記錄在Textbox裡面觀察
Fibo(12)為例,計算出費式數列第12項:

答案144,是正確的
但是執行時間居然超過5秒

 

往上看一下計算過程,發現重複計算的部分很多
Fibo(3)、Fibo(2)、Fibo(1)出現了好多次,這些重複的部分都會造成效能浪費
導致執行時間大幅上升
這種計算方式叫做"迭代法"
迭代法(Iterative method)
重複使用計算出來的結果,就叫迭代法。
雖然程式碼撰寫方便,也比較直觀
但是浪費效能的確是個硬傷
 
猜猜看Fibo(15)要花多少時間呢?

超過54秒,快要1分鐘了

這個費式數列也太費事了吧

想想看,有沒有辦法改進程式的執行效能。

方式二(記憶法)

其實還是有辦法解決的

 

既然拖垮效能的元凶是"重複計算"
那只要宣告一個陣列,把運算過的值存起來
以後再遇到,就不必計算第二次,這個稱之為"記憶法"
記憶法(Memoization)
將計算的結果保存起來,以備下次遇到同樣問題時使用。
程式碼範例如下:
Public fiArray(200) As Integer '費式數列(陣列)

Function Fibo(x As Integer)
    If x <= 2 Then '費式數列前兩項都是1
        Return 1
    ElseIf fiArray(x) = 0 then '這個位置尚未計算過,才會使用遞迴計算
        fiArray(x) = Fibo(x - 1) + Fibo(x - 2) '存進fiArray陣列,提供下次使用
    End If

    Return fiArray(x) '回傳fiArray陣列
End Function
宣告陣列fiArray(200),用來存放已經計算完成的費式數列
馬上來檢視一下,改善後的程式效能吧。

 

試試看Fibo(15)

執行時間0.12秒,成功改善效能。

 

至於運算過程,經過效能提升,省去了多餘的重複計算之後,總算是簡化成人腦也能看懂的程度了
例如Fibo(10)

可以試著推算看看,能夠抓到程式執行的流向,才能搞懂"遞迴"是怎麼一回事。

程式碼分享

底下提供VB.NET程式碼
開新專案,在空白處點兩下,進入後端
後端清空程式碼,並直接複製貼上底下的程式碼,即可執行。
(前端留白就好,不需新增控制項)
Public Class Form1
    Public fiArray(200) As Integer '費式數列(陣列)
    Public TextBox1 As New TextBox '宣告前端控制項
    Public Button1 As New Button
    Public Button2 As New Button

    Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
        '前端控制項屬性設定
        Me.Size = New Size(326, 660)

        Button1.Name = "Button1"
        Button1.Text = "使用遞迴"
        Button1.Location = New Point(55, 586)
        Me.Controls.Add(Button1)
        AddHandler Button1.Click, AddressOf Button1_Click

        Button2.Name = "Button2"
        Button2.Text = "遞迴+陣列"
        Button2.Location = New Point(165, 586)
        Me.Controls.Add(Button2)
        AddHandler Button2.Click, AddressOf Button2_Click

        TextBox1.Name = "TextBox1"
        TextBox1.Location = New Point(12, 12)
        TextBox1.Size = New Size(286, 550)
        TextBox1.Multiline = True
        TextBox1.ScrollBars = ScrollBars.Both
        Me.Controls.Add(TextBox1)
        AddHandler TextBox1.TextChanged, AddressOf TextBox1_TextChanged
    End Sub

    Function Fibo(x As Integer)
        TextBox1.Text += "Fibo(" & x & ") start."
        TextBox1.Text += vbNewLine

        If x <= 2 Then '費式數列前兩項都是1
            TextBox1.Text += "Return 1"
            TextBox1.Text += vbNewLine
            Return 1
        Else
            TextBox1.Text += "Return Fibo(" & x - 1 & ") + Fibo(" & x - 2 & ")"
            TextBox1.Text += vbNewLine
            Return Fibo(x - 1) + Fibo(x - 2)
        End If
    End Function

    Function Fibo2(x As Integer)
        TextBox1.Text += "Fibo2(" & x & ") start."
        TextBox1.Text += vbNewLine

        If x <= 2 Then '費式數列前兩項都是1
            TextBox1.Text += "Return 1"
            TextBox1.Text += vbNewLine
            fiArray(x) = 1
        ElseIf fiArray(x) <> 0 Then '已運算過此步驟,直接回傳數值
            TextBox1.Text += "Return fiArray(" & x & ") = " & fiArray(x)
            TextBox1.Text += vbNewLine
        Else
            TextBox1.Text += "Return Fibo2(" & x - 1 & ") + Fibo2(" & x - 2 & ")"
            TextBox1.Text += vbNewLine
            fiArray(x) = Fibo2(x - 1) + Fibo2(x - 2)
        End If

        Return fiArray(x)
    End Function

    Private Sub Button1_Click(sender As Object, e As EventArgs)
        Dim dteStart As DateTime = Now '記錄開始的時間

        TextBox1.Text = "" 'textbox初始化

        TextBox1.Text += "費式數列第12項(使用遞迴): "
        TextBox1.Text += vbNewLine
        TextBox1.Text += "計算過程:"
        TextBox1.Text += vbNewLine
        Dim ans As Integer = Fibo(12)
        TextBox1.Text += vbNewLine
        TextBox1.Text += "答案: " & ans.ToString
        TextBox1.Text += vbNewLine

        Dim TS As TimeSpan = Now.Subtract(dteStart) '計算執行時間
        TextBox1.Text += "執行時間: " & TS.TotalSeconds & " 秒"
        TextBox1.Text += vbNewLine
    End Sub

    Private Sub Button2_Click(sender As Object, e As EventArgs)
        Dim dteStart As DateTime = Now '記錄開始的時間

        For i = 0 To fiArray.Length - 1 '陣列初始化
            fiArray(i) = 0
        Next

        TextBox1.Text = "" 'textbox初始化

        TextBox1.Text += "費式數列第12項(使用遞迴+陣列): "
        TextBox1.Text += vbNewLine
        TextBox1.Text += "計算過程:"
        TextBox1.Text += vbNewLine
        Dim ans As Integer = Fibo2(12)
        TextBox1.Text += vbNewLine
        TextBox1.Text += "答案: " & ans.ToString
        TextBox1.Text += vbNewLine

        Dim TS As TimeSpan = Now.Subtract(dteStart) '計算執行時間
        TextBox1.Text += "執行時間: " & TS.TotalSeconds & " 秒"
        TextBox1.Text += vbNewLine
    End Sub

    Private Sub TextBox1_TextChanged(sender As Object, e As EventArgs)
        TextBox1.SelectionStart = TextBox1.Text.Length
        TextBox1.ScrollToCaret()
    End Sub
End Class
 

 

END

你可能感興趣的文章

[VB.NET] 分治法+遞迴練習 12個硬幣中,有一個偽幣重量較輕(設為0),其他正常硬幣重量較重(設為1) 透過分治法+遞迴,找出偽幣的位置

[VB.NET] 費式數列的2種解法 [遞迴 + 記憶法] 記憶法(Memoization) 將計算的結果保存起來,以備下次遇到同樣問題時使用。

[VB.NET] ComboBox 使用For迴圈移除項目 ComboBox 使用For迴圈移除項目,看起來很簡單,實際上會遇到什麼問題呢

[VB.NET] A=B小遊戲(附原始碼) A=B小遊戲(附原始碼)

我有話要說

>>

限制:留言最高字數1000字。 限制:未登入訪客,每則留言間隔需超過10分鐘,每日最多5則留言。

訪客留言

[無留言]

隨機好文

[寶可夢-劍盾] 級別對戰 單打隊伍分享 [S27] 全新規則登場,雙傳說組隊開放,隊伍組合更多樣化! 你的傳說隊伍組合是甚麼呢?

[jQuery] 一行搞定if判斷式 一行搞定if判斷式

[量化交易] 幣牛各種獲利模式的簡介 幣牛有各種獲利模式,常讓新手眼花撩亂,以下進行簡單介紹

[C#] 加密圖片,透過Logistic混沌演算法 加密圖片,透過Logistic混沌演算法

朱紫組隊(筆記) カイリュー たちまき ひこう/ドラゴン/テラノーマル げきりん/しんそく/ほのおのパンチ/じしん キノガッサ たすき く