|
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用 · 内置多项VBA编程加强工具 ★ 免费下载 ★ ★ 使用手册★
本帖最后由 香川群子 于 2013-10-29 22:31 编辑
根据我的数学研究,发现规律:
因为 1/2+1/3+1/4=13/12 再减去本身则增量=13/12-1=1/12
因此事实上可以知道数列的周期规律是12 (其实,2、3、4的最小公倍数就是=12)
呵呵。- Dim d, dic, cnt
- Sub test()
- tms = Timer
- d = Array(0, -1, -1, -1, 0, -1, 0, -1, 0, 0, 0, -1)
- Set dic = CreateObject("Scripting.Dictionary")
-
- aCoins = Array(12, 123, 1000, 50000, 600000, 30000000, 10 ^ 9)
- ReDim aRes(UBound(aCoins))
- For i = 0 To UBound(aCoins)
- aRes(i) = f(aCoins(i)) + aCoins(i)
- Next
- Set dic = Nothing
-
- Debug.Print "ID: " & "<kagawa>"
- Debug.Print "Result: " & Join(aRes, ", ")
- Debug.Print "Time: " & Format(Timer - tms, "0.000s")
- End Sub
- Function f(n)
- cnt = cnt + 1
- If dic.Exists(n) Then
- f = dic(n)
- Else
- If n < 12 Then
- dic(n) = 0
- Else
- f = n \ 12 + d(n Mod 12) + f(n \ 2) + f(n \ 3) + f(n \ 4)
- dic(n) = f
- End If
- End If
- End Function
复制代码 分析0-11个数可知,按本题的要求处理,
本质上是每个数在除2、除3、除4并去整的过程中,会把多余的小数舍掉、扔掉。
那么舍掉了就是减少了。而如果没有减少则整体会增加。
详细变化,请看下图。
因此,最后得到了增量变化的结果序列:Array(0, -1, -1, -1, 0, -1, 0, -1, 0, 0, 0, -1)
按此原理,就有了增量 = n \ 12 + d(n Mod 12) 的计算结果。
【这个结果仅仅是增量,不含拆分前n本身】
最后,需要考虑递归。
为了提高计算速度,使用字典方法……差别在于我的方法是可以直接计算得到每一个阶段的增量的。
当然,如果参数改变,则序列也会变化……因此缺乏通用性。
但就本题来说,也是一种有趣的算法变化。
|
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有账号?免费注册
x
|