猴子选大王的四种VB解法

题目:

一堆猴子编号依次是1，2，3 ...n ,这群猴子（n个）按照1到n的顺序围坐一圈，从第1开始报数，报双数的猴子离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

解法:

1.集合的方法(O(2N)):

Function Monkeyking(ByVal n As Long) As Long
Dim all As New Collection, i As Long
For i = 1 To n
all.Add i
Next
While all.Count > 1
all.Add all(1)
all.Remove 1
all.Remove 1
Wend
Monkeyking = all(1)
End Function

2.直接循环取模(O(N)):

Function Monkeyking(ByVal n As Long) As Long
Dim i As Long, K As Long
For i = 2 To n
K = (K + 2) Mod i
Next
Monkeyking = K + 1
End Function

3.递归(O(LOG N)):

Function Monkeyking(ByVal n As Long) As Long
If n = 1 Then Monkeyking = 1: Exit Function
Monkeyking = 2 * (Monkeyking(n \ 2) + (n And 1)) - 1
End Function

4. 公式:

Function Monkeyking(ByVal n As Long) As Long
Monkeyking = 2 * (n - 2 ^ Int(Log(n) / Log(2))) + 1
End Function

以上四种方法不仅代码越来越短,而且效率越来越高.