自動目錄
前言
假設桌上有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
'呼叫函式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
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
