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

lee1892

感谢各位参与，楼上有重复发贴的，均以最后一贴为准，所得运行结果如下：[code=vb]ID: <大灰狼1976>
Result: 13, 144, 1370, 96394, 1427537, 98274986,
Time: 0.000s
ID: zhyj_88
Result: 13, 144, 1370, 96394, 1427537, 98274986, 4243218150
Time: 0.016s
ID: xiaofx11
Result: 13, 144, 1370, 96394, 1427537, 98274986,
Time: 0.000s
ID: <清风_ll>
Result: 13, 144, 1370, 96394, 1427537, 98274986,
Time: 0.020s
ID: wcymiss
Result: 13, 144, 1370, 96394, 1427537, 98274986, 4243218150
Time: 0.000s
ID: 小花鹿
Result: 13, 144, 1370, 96394, 1427537, 98274986
Time: 11.066s
ID: <yuanhongly>
Result: 13, 144, 1370, 96394, 1427537, 98274986, 4243218150
Time: 0.016s
ID: xzk235
Result: 13, 144, 1370, 96394, 1427537, 98274986, 4243218150
Time: 0.016s
ID: hellohaha
Result: 13, 144, 1370, 96394, 1427537, 98274986
Time: 9.555s
ID: <huahua2005>
Result: 13, 144, 1370, 96394, 1427537, 98274986
Time: 1.234s
ID: Bodhidharma
Result: 13, 144, 1370, 96394, 1427537, 98274986, 4243218150
Time: 0.750s
ID: <JsXjd>
Result: 13, 144, 1370, 96394, 1427537, 98274986, 4243218150, 54563
Time: 0.000s
ID: <JsXjd2>
Result: 13, 144, 1370, 96394, 1427537, 98274986, 4243218150, 54563
Time: 0.000s
ID: <minjiwei>
Result: 13, 144, 1370, 96394, 1427537, 98274986
Time: 5.559s
ID: <delete_007>
Result: 13, 144, 1370, 96394, 1427537, 98274986, 4243218150
Time: 0.000s
=======================
' Not included in the attachement:
ID: 5blessyou
Result: 13, 144, 1370, 96394, 1427537, 98274986
Time: 6.275s
[/code]我个人认为的评分如下：

ID	正确结果分	1秒内计算分	可于0.1秒内计算10^9分	优秀追加分	合计得分	备注
大灰狼1976	√	√	变量类型限制	√	3	巧妙的字典使用
zhyj_88	×	√	√	×	2	看花眼了，代码不自证 11出错
xiaofx11	√	√	变量类型限制		2	代码自证，但未得前3分
清风_ll	√	√	变量类型限制		2
wcymiss	√	√	√		3
小花鹿	√	超时	超时		1
yuanhongly	√	√	√		3
xzk235	×	√	√	×	2	代码自证 11出错，按之前原则未得前3分
hellohaha	√	超时	超时		1
huahua2005	√	超时	超时		1
Bodhidharma	√	√	超时		2	代码自证，但未得前3分
JsXjd	×	√	√		2	11出错
minjiwei	√	超时	超时		1	代码自证，但未得前3分
delete_007	√	√	√		3
5blessyou	√	超时	超时		1

这是一个非常简单的利用递归或则迭代均可以得到答案的题目。

1、速度：为了达到题目要求的速度，一个简单而行之有效的方法是所谓的空间换时间，即将中间计算结果保留的内存中，以避免重复计算从而达到提速的效果。大多数同学都采用了字典对象，实际上用数组也能达到目的。

2、自证：貌似所有同学都不约而同的选择2、3、4的最小公倍数作为收敛退出条件，结果虽然正确，但我个人是反对的。理由是代码不能自证，或则将1~12的结果在帖子里列出来并证明“大于12的所有数均满足除2、3、4的和大于自身”，但没人这么做。正确的递归退出条件应当是nCoin=0 OR nCoin >= INT(nCoin/2) + INT(nCoin/3) + INT(nCoin/4)，此时递归返回值亦为0 | nCoin。

题目最初的设想是锻炼递归思维、变量类型的正确使用、代码加速技巧。

由于题目比较简单，我所准备的代码与大家大同小异，就不另贴了，呵呵~
====================================
ON 2013.09.02 REV. 1
鉴于有同学十分不满意，多说两句。
请自行仔细审题，题目中从未提到速度是评分的主要因素，充其量是个限制条件。
实际上从逻辑上而言，凡未出现类似 If nCoin >= INT(nCoin / 2) + INT(nCoin / 3) + INT(nCoin / 4) Then ... 的，使得代码能够按题意自证的，均可判错（我个人如此认为）。
如认为迭代实现比递归实现难度大的，请学习2楼大灰狼同学的代码，另外这与本题的评分标准无关。

====================================
ON 2013.09.03 REV. 2
版主说了，发现问题要改正，所以有问题的三人各少1分，呵呵~xzk同学按之前未得前3分原则，则代码自证的追加分也木有了~

5blessyou

1. Sub ChangeCoin()
   
2.     Dim aCoins(), aRes(), ncoin, t#
   
3.     ' 可更改段
   
4.     ' 只能是Dim
   
5.     Dim m As Byte
   
6.     ' 可更改结束
   
7.     aCoins = Array(12, 123, 1000, 50000, 600000, 30000000)
   
8.     ReDim aRes(UBound(aCoins))
   
9.     t = Timer
   
10.     ' 可更改段
    
11.     For Each ncoin In aCoins
    
12.         '....
    
13.         aRes(m) = abc(ncoin)
    
14.         m = m + 1
    
15.     Next
    
16.     ' 可更改结束
    
17.     Debug.Print "ID: " & "<YOUR ID>"
    
18.     Debug.Print "Result: " & Join(aRes, ", ")
    
19.     Debug.Print "Time: " & Format(Timer - t, "0.000s")
    
20. End Sub
    
21. Function abc(ncoin) As Long
    
22.     If ncoin > 11 Then
    
23.         
    
24.         abc = abc(ncoin \ 2) + abc(ncoin \ 3) + abc(ncoin \ 4)
    
25.     Else
    
26.         abc = ncoin
    
27.     End If
    
28. End Function
    

复制代码

minjiwei

lee1892 发表于 2013-8-30 13:54
感谢各位参与，楼上有重复发贴的，均以最后一贴为准，所得运行结果如下：我个人认为的评分如下：

这是一 ...

明白了。看来我是做的最粗糙的一个。{:soso_e143:}

jsxjd

lee1892 发表于 2013-8-30 13:54
感谢各位参与，楼上有重复发贴的，均以最后一贴为准，所得运行结果如下：我个人认为的评分如下：

这是一 ...

建议楼主把“aCoins”改成一样的，用下面的代码重新进行测试：

1. Sub test()
   
2.     t0 = Timer
   
3.         For i = 1 To 100:
   
4.             楼10_zhyj_88.ChangeCoin
   
5.         Next
   
6.     t1 = Timer
   
7.         For i = 1 To 100:
   
8.             Call 楼13_xzk235.ChangeCoin
   
9.         Next
   
10.     t2 = Timer
    
11.         For i = 1 To 100:
    
12.             Call 楼18_jsxjd_1.ChangeCoin
    
13.         Next
    
14.     t3 = Timer
    
15.     Debug.Print t1 - t0, t2 - t1, t3 - t2
    
16. End Sub
    

复制代码

另外，能用 Function 递归 限制程序结构还有意义吗？

Bodhidharma

jsxjd 发表于 2013-8-31 18:39
建议楼主把“aCoins”改成一样的，用下面的代码重新进行测试：另外，能用 Function 递归 限制程序结构还 ...

另外，能用 Function 递归 限制程序结构还有意义吗？

嗯…這個我也覺得有點奇怪
我也是以為不能在外面另加function(根據原題程式的結構)
所以才在原本的sub之中增加類似stack的程序，而不是直接用recursion
但是看大多數人好像都是另外在sub程序外面增加function

yuanhongly

Bodhidharma 发表于 2013-8-31 19:18
嗯…這個我也覺得有點奇怪
我也是以為不能在外面另加function(根據原題程式的結構)
所以才在原本的su ...

答题要求：
可完形填空如下，允许添加过程或函数及公共变量：

以上是出楼主出题时说明的。
看来是你们粗心没有看懂要求。

小花鹿

跟楼主讨论个问题：
楼主说“即任一正整数”，也就是说11应该也属于这个范围吧，但是，你把数组中的12改为11，看看有的代码是不是结果是错误的？

jsxjd

yuanhongly 发表于 2013-8-31 20:06
答题要求：
可完形填空如下，允许添加过程或函数及公共变量：

用函数还需要可更改段吗？

yuanhongly

jsxjd 发表于 2013-8-31 20:32
用函数还需要可更改段吗？

楼主题是这样要求的，不信你再去仔细读读题吧。

wcymiss

jsxjd 发表于 2013-8-31 20:32
用函数还需要可更改段吗？

阅卷是个体力活。
楼主的完形填空可能是为了阅卷方便和测速环境的一致而设置的。

你可以在答题期间就题目的疑虑与楼主短信交流啊。我就常这样做，我做楼主的时候也常收到别人的各种咨询。多沟通才能相互理解。

以上言语如有冒犯，还请海涵。