[第96期]换硬币[已总结]

香川群子

理论研究一下：

1/2+1/3+1/4=1.08333>1

1/[1-(1/2+1/3+1/4)]=1/0.08333=12

因此只要基数>12，那么就可以通过拆分得到更多的结果……

而小于12时就可以停止计算了。

数值拆分以后的增量，严格按照0-11进行变化：

因此实施上可以用很简单的函数进行迭代计算得到结果。

呵呵。用空研究一下。

香川群子

根据我的数学研究，发现规律：
因为 1/2+1/3+1/4=13/12 再减去本身则增量=13/12-1=1/12

因此事实上可以知道数列的周期规律是12 （其实，2、3、4的最小公倍数就是=12）

呵呵。

1. Dim d, dic, cnt
   
2. Sub test()
   
3.     tms = Timer
   
4.     d = Array(0, -1, -1, -1, 0, -1, 0, -1, 0, 0, 0, -1)
   
5.     Set dic = CreateObject("Scripting.Dictionary")
   
6.    
   
7.     aCoins = Array(12, 123, 1000, 50000, 600000, 30000000, 10 ^ 9)
   
8.     ReDim aRes(UBound(aCoins))
   
9.     For i = 0 To UBound(aCoins)
   
10.         aRes(i) = f(aCoins(i)) + aCoins(i)
    
11.     Next
    
12.     Set dic = Nothing
    
13.    
    
14.     Debug.Print "ID: " & "<kagawa>"
    
15.     Debug.Print "Result: " & Join(aRes, ", ")
    
16.     Debug.Print "Time: " & Format(Timer - tms, "0.000s")
    
17. End Sub
    
18. Function f(n)
    
19.     cnt = cnt + 1
    
20.     If dic.Exists(n) Then
    
21.         f = dic(n)
    
22.     Else
    
23.         If n < 12 Then
    
24.             dic(n) = 0
    
25.         Else
    
26.             f = n \ 12 + d(n Mod 12) + f(n \ 2) + f(n \ 3) + f(n \ 4)
    
27.             dic(n) = f
    
28.         End If
    
29.     End If
    
30. 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本身】

最后，需要考虑递归。
为了提高计算速度，使用字典方法……差别在于我的方法是可以直接计算得到每一个阶段的增量的。
当然，如果参数改变，则序列也会变化……因此缺乏通用性。
但就本题来说，也是一种有趣的算法变化。

香川群子

5blessyou 发表于 2013-8-30 15:30

还是需要加入字典。否则数字大了速度就不行了。

1. Function abc(ncoin)
   
2.     If dic.Exists(ncoin) Then
   
3.         abc = dic(ncoin)
   
4.     Else
   
5.         If ncoin < 12 Then
   
6.             abc = ncoin
   
7.         Else
   
8.             abc = abc(ncoin \ 2) + abc(ncoin \ 3) + abc(ncoin \ 4)
   
9.         End If
   
10.         dic(ncoin) = abc
    
11.     End If
    
12. End Function
    

复制代码

lee1892

香川群子 发表于 2013-10-29 23:34
还是需要加入字典。否则数字大了速度就不行了。

你的回帖我怎么收不到提醒呢～

参考楼上的参考答案贴。

我个人的看法，算法的内在逻辑是至关重要的。你的思路和楼上诸位并没有本质上的不同，在递归的退出机制上、在对问题的解析上。

稍微展开一点：
1、换一些数，个数不限，一些其它整数或是小数甚或是无理数，只要使其被1除的和稍大于1即可。
2、如果每一次换的时候有3种选择，比如：直接1比1的换1枚、换3枚、换4枚（某种上面提到的方案）。

我估计很多人还是没有建立这样一个概念，递归很多时候是由上至下运行，但计算则是由下至上的，可以参考常被用作案例的阶乘代码。

以上供参考。

香川群子

lee1892 发表于 2013-10-30 00:12
你的回帖我怎么收不到提醒呢～

参考楼上的参考答案贴。

【递归很多时候是由上至下运行，但计算则是由下至上的】

对啊，递归递归，把参数一路传递下去，到底以后才能计算出结果，然后再一层一层回归……很好玩的。

香川群子

lee1892 发表于 2013-10-30 00:12
你的回帖我怎么收不到提醒呢～

参考楼上的参考答案贴。

43楼是改的5bless的代码……加了字典。

42楼才是我自己想的代码……有趣的是我这样只计算增量。
特点是按12的周期，用余数求增量变化值。
d = Array(0, -1, -1, -1, 0, -1, 0, -1, 0, 0, 0, -1)
以及 = n \ 12 + d(n Mod 12) 的方法计算实际增量……这个和别人的方法不同。


其它确实也没有啥特点……再说别人的代码也都公开了，我做啥也意义不大了。

kuangben8

香川群子 发表于 2013-10-30 00:30
43楼是改的5bless的代码……加了字典。

42楼才是我自己想的代码……有趣的是我这样只计算增量。

逻辑思维太强了！

lj1226189

好厉害的算法