每日一题：[题目]有足够量的2分、5分、1分硬币，请问凑齐1元钱有多少种方法？

netegg

回复 15# annybaby
讨论下去无意义,看看吧[au3]$hTime1 = TimerInit()
For $i=1 To 10
        For $j=1 To 10
                $s=1
        Next
Next
$iTime1 = TimerDiff($hTime1)
$hTime2 = TimerInit()
For $i=1 To 10
        For $j=1 To 10
                $s=1
        Next
Next
$iTime2 = TimerDiff($hTime2)
MsgBox(0, 0, $iTime1&@LF&$iTime2)
[/au3]
要不就试试看，第一遍循环完了记录下时间，重新启动下，再换种方法循环第二遍，可能能比出来

annybaby

回复 16# netegg

看什么????

netegg

回复 17# annybaby
两个循环从理论上讲是一样的，看看时间

524443834

擦擦。，。这种问题好头痛

annybaby

回复 18# netegg

是啊,我前面不是已经说了,是计时精度的问题??因为时间太短了,所以需要多一点的运算才能看得出~~

happytc

回复 15# annybaby


    意思是不能简单说大循环放里面效率高，还是放外面效率高。我们不能从‘表面’看出那个更好！因其充满了不确定性，优化程序性，还要考虑别的关键因素，如编译器编译时的优化（当然au3基本不存在优化的说法）。另外影响程序性能的另一个关键因素是：CPU缓存。在CPU中，性能最快的存储设备当属“寄存器”，但数量很有限，于是就是cpu的一级缓存，二级缓存等。读取速度是：一级缓存>二级缓存>内存>硬盘（虚拟内存机制）

有个单词Locality（局域性）用于专门描述这种缓存对程序性能的影响，如下面的两种方法，那种效率更高呢？可能表面一看，肯定会说是方法一，因为它少了$i的累加和跳转。
方法一：

For $i = 0 To 10000
        FunA()
        FunB()
Next

方法二：

For $i = 0 To 10000
        FunA()
Next
For $i = 0 To 10000
        FunB()
Next

从局域性的两个方面‘空间局域性’和‘时间局域性’，空间局域性是指当加载一个数据后，再在它附近加载另外一个数据，时间局域性是指加载一个数据后，短时间内重新加载这块数据。明显在它附近再加载的速度会非常快，也就是从较快的缓存中加载“热”的数据效率很高（就象为什么冷启动慢一样的道理）
   再来具体看上面的例子， 虽然方法一减少了$i的累加次数和条件跳转的次数，但是它在一次循环中做了两件事情，可能在执行B函数时，A函数刚刚进入缓存的数据便冷却了，于是在下次执行A函数时又要重新从较慢的存储设备中加载数据。而在方法二中，它“持续密集”地执行万次的A函数或B函数的调用，此间大量的数据访问都是集中在一级缓存上，速度性能优势不言而喻的。

  同样，象上面的双循环也一个道理，主要还是要看这两个循环里分别执行了什么，而不能仅仅说‘大循环在内层循环好’。也就是我们要考虑Locality的空间和时间两个方面。而不是只考虑时间局域性。

netegg

回复  annybaby


    意思是不能简单说大循环放里面效率高，还是放外面效率高。我们不能从‘表面’看出 ...
happytc 发表于 2013-1-19 15:31

这个好像比较靠谱

annybaby

回复 21# happytc

呵呵~~你想太多了~
请回头看下我和M兄的帖子,其实可以说是完全一样的,只不过他把小的循环放在最内层,导致CPU在循环层之间切换得多一些罢了,以你渊博的知识,当然也知道有这么回事`~
后面的举例的帖子显然已经证明了这一点`

happytc

回复  happytc

呵呵~~你想太多了~
请回头看下我和M兄的帖子,其实可以说是完全一样的,只不过他把小的循 ...
annybaby 发表于 2013-1-19 15:57

其实象上面的这种最简单双循环情况，在编译型语言里，基本上随便那种放外面/里面都可以，因为编译器自己会优化的。
再则，上面的这种双循环，那个在里面，那个在外面，循环次数不是最重要的，最重要的是要看循环体。
如有$aArr[j] 一般 j 放内层好；如有$aArr[j] 一般 i 放内层好。如果两样都有 ，就差不多相当于矩阵乘法了，优化就会复杂多了，难于一般地说那种方式好，只能具体问题，具本优化。

annybaby

回复 24# happytc

前面其实已经很清楚了,除了CPU在循环层之间的切换次数不同之外,其它的都是一样的
所以两者的时间差就是这里了~~
根本不涉及其它东西~
呵~

Duvet

Local $sResult
_OneDollar()
ConsoleWrite($sResult & @CRLF)
Exit

Func _OneDollar($x = 0, $y = 0)
        Local $z = 100 - $x * 5 - $y * 2
        $sResult &= $z & "個壹分" & @TAB & $y & "個貳分" & @TAB & $x & "個伍分" & @CRLF
        If $y < 50 - Ceiling($x*2.5) Then
                _OneDollar($x, $y+1)
        ElseIf $x < 20 Then
                _OneDollar($x+1, 0)
        EndIf
EndFunc

happytc

嗯，不错，终于有人来递归了。我上面还是说呢，那个来个递归的。

其实我一直很喜欢递归代替循环，因为它看起来简单易懂，代码还简洁，虽然可能效率不比循环高

wua0550

循环 递归都有人做了我来个不一样的数组法
先声明这个方法不是一般的慢 所以 我只做了 和为 10的。
因为这方法没什么实用价格所以本来应该加的结果去重也懒得加了~~~~只是为了提供另一种思路

#include <Array.au3>
Local $aArray[10 + 5 + 2], $andnum
For $i = 0 To 10 + 5 + 2 - 1
        Select
                Case $i >= 10 And $i < 10 + 5
                        $aArray[$i] = "2"
                Case $i >= 10 + 5
                        $aArray[$i] = "5"
                Case $i >= 0 And $i < 10
                        $aArray[$i] = "1"
        EndSelect
Next

For $i = 1 To 10
        Local $aArrayCombo = _ArrayCombinations($aArray, $i, "+")
        If $i>1 Then OK($aArrayCombo)
Next


Func OK($aArrayCombo)
        For $i = 1 To $aArrayCombo[0]
                $num = StringSplit($aArrayCombo[$i], "+")
                $andnum=0
                For $x = 1 To $num[0]
                        $andnum += $num[$x]
                Next
                If $andnum = 10 Then ConsoleWrite($aArrayCombo[$i] & @CRLF)
        Next
EndFunc   ;==>OK

zch11230

感觉和那个 8个8组成1000有点像还只需要计算相加
手机码字求验证

for $i1＝0 to 100
for $i2 ＝ 0 to 50
for $i5 ＝ 0 to 20

if $i1＋$i2*2＋$i5*5＝ 100 then consolewrite ($i1&"个1分"&$i2&"个2分"&$i5&"个5分"&@lf)

next
next
next

sleep365

回复  MicroBlue

汗!!
坛子时间显示好像又有些问题了,我刚刚回复时看到只有你一个回复,而且不是这样的 ...
annybaby 发表于 2013-1-19 11:22

    annybaby说的很对，有专业水平啊。