[精讚] [會員登入]
185

[VB.NET] 分治法+遞迴練習

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

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

分享連結 [VB.NET] 分治法+遞迴練習@大塚 宏 ~認真玩・輕鬆學~
(文章歡迎轉載,務必尊重版權註明連結來源)
2022-03-01 09:10:12 最後編修
2022-02-24 14:52:30 By 大塚 宏
 

自動目錄

前言

假設桌上有12枚硬幣
12枚硬幣中,有一枚偽幣重量較輕(設為0),其他正常硬幣重量較重(設為1)
透過分治法+遞迴(遞迴是什麼?),找出偽幣的位置

分治法

分治法(Divide and conquer algorithms)
將一個大問題分成多個小問題,然後逐一擊破解決。
舉例來說,可以將桌上的硬幣,分為2堆去秤重量
其中必定有一堆當中,包含一枚偽幣,重量是5
(另一堆重量是6,代表全部都是正常幣)
把包含偽幣的那一堆,再度分成兩堆去秤重量,找出比較輕的那一堆,再度分兩堆......
直到找出最輕的那枚硬幣為止。

解題過程

假設第三枚硬幣為偽幣,執行結果如下:

執行過程,先從findCoin(1,12)當中分一半
發現左半邊比較輕,於是再度執行findCoin(1,6)
仍然是左半邊比較輕,於是再度執行findCoin(1,3)
這次是右半邊比較輕,執行findCoin(3,3)
只剩下3自己了,得知3=偽幣

 

假設第十枚硬幣為偽幣,執行結果如下:

執行過程,先從findCoin(1,12)當中分一半
發現右半邊比較輕,於是再度執行findCoin(7,12)
仍然是右半邊比較輕,於是再度執行findCoin(10,12)
發現10比12還要輕
得知10=偽幣

 

假設第二枚硬幣為偽幣,執行結果如下:

執行過程,先從findCoin(1,12)當中分一半
發現左半邊比較輕,於是再度執行findCoin(1,6)
仍然是左半邊比較輕,於是再度執行findCoin(1,3)
發現兩邊(1跟3)一樣重,因此最輕的是位於"中間"的那一枚
得知2=偽幣

程式碼分享

開新專案,空白處點兩下進入後端
後端清空程式碼,並直接複製貼上底下的程式碼,即可執行。
(前端留白就好,不需新增控制項)
Public Class Form1
    Public coin As Array = {99, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1} 'coin(0)不使用,設為99
    Public TextBox1 As New TextBox '宣告前端控制項

    Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load

        '前端控制項屬性設定
        Me.Size = New Size(440, 645)

        TextBox1.Name = "TextBox1"
        TextBox1.Location = New Point(12, 12)
        TextBox1.Size = New Size(400, 580)
        TextBox1.Multiline = True
        TextBox1.ScrollBars = ScrollBars.Both
        Me.Controls.Add(TextBox1)


        '呼叫函式findCoin
        findCoin(1, 12, 1) 'findCoin(最左邊硬幣, 最右邊硬幣, 遞迴層次)
    End Sub

    Sub findCoin(startCoin As Integer, endCoin As Integer, round As Integer)
        Dim left, right As Integer

        TextBox1.Text += "findCoin(" & startCoin & " ," & endCoin & "), round: " & round & " start."
        TextBox1.Text += vbNewLine

        For i = startCoin To Int((startCoin + endCoin) / 2)  '左半邊的重量
            left += coin(i)
            TextBox1.Text += "left += " & coin(i) & ", i = " & i & ", left = " & left
            TextBox1.Text += vbNewLine
        Next

        TextBox1.Text += vbNewLine

        For i = Int((startCoin + endCoin) / 2) + 1 To endCoin '右半邊的重量
            right += coin(i)
            TextBox1.Text += "right += " & coin(i) & ", i = " & i & ", right = " & right
            TextBox1.Text += vbNewLine
        Next

        TextBox1.Text += vbNewLine

        If left < right Then '左半邊比較輕,左半邊繼續秤重
            findCoin(startCoin, Int((startCoin + endCoin) / 2), round + 1)
        ElseIf left > right Then '右半邊比較輕,右半邊繼續秤重
            findCoin(Int((startCoin + endCoin) / 2) + 1, endCoin, round + 1)
        ElseIf left = right Then '左右兩邊一樣重
            If startCoin = endCoin Then '只剩下自己 ex. findCoin(3,3)
                TextBox1.Text += "answer: " & startCoin
            ElseIf coin(startCoin) < coin(endCoin) Then '左邊那顆最輕
                TextBox1.Text += "answer: " & startCoin
            ElseIf coin(startCoin) > coin(endCoin) Then '右邊那顆最輕
                TextBox1.Text += "answer: " & endCoin
            Else
                TextBox1.Text += "answer: " & startCoin + 1 '中間那顆最輕
            End If
        End If
        TextBox1.Text += vbNewLine
        TextBox1.Text += vbNewLine
        TextBox1.Text += "findCoin(" & startCoin & " ," & endCoin & "), round: " & round & " end."
    End Sub
End Class

 

END

你可能感興趣的文章

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

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

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

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

我有話要說

>>

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

訪客留言

[無留言]

隨機好文

[寶可夢-劍盾] 單打對戰術語解說 本篇介紹一些對戰術語,方便初學者更快上手對戰

[對戰筆記] 2022年 3月 第一回 [S28] 對戰札記,2022年 3月 第一回筆記

[警告] 虛擬貨幣投資的詐騙手法 最近虛擬貨幣投資非常盛行,畢竟能賺錢的事情,自然會吸引大票投資客入場

[理財筆記] 甚麼是造市商? 用處是甚麼? 造市商看起來有點難懂,我自己是用"遊戲王卡"來解釋

[加密貨幣] 幣牛量化機器人註冊教學 幣牛量化機器人註冊教學