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

happytc

[题目]有足够量的1分、2分、5分硬币，请问凑齐1元钱有多少种方法？
下面隐藏的是我写了个，周末闲着没有事，玩玩，大家也乐乐。

游客，如果您要查看本帖隐藏内容请回复

MicroBlue

笨方法：

Local $intOne  = 1
Local $intTwo  = 2
Local $intFive = 5
Local $intSum  = 100


For $i = 0 To 100
        For $j = 0 To 50
                For $k = 0 To 20
                        If $intOne * $i + $intTwo *$j + $intFive * $k == $intSum Then
                                ConsoleWrite($intOne & "X" & $i & "+" & $intTwo & "X" & $j & " + "& $intFive  & "X" & $k & "== 100" & @CRLF)
                        EndIf
                Next
        Next
Next

netegg

回复 1# happytc
三种硬币是必须都要有吗？

Local $i = 0, $j = 0, $k = 0, $o =0
While $i <= 100
        Do
                For $k = 0 To (100-$i-(2*$j))/5
                        If $i + 2 * $j + 5 * $k = 100 Then 
                           ConsoleWrite($i & '个1分' & $j & '个2分' & $k & '个5分' & @CR)
                           $o+=1
                        else
                           $o+=1
                       endif
                Next
                $j += 1
        Until $j > (100-$i)/2
        $j = 0
        $k = 0
        $i += 1
WEnd
consolewrite('共计算'&$o&'次')

happytc

回复 3# netegg


    看题意嘛，肯定不是必须了，只要凑足一元就可以了。如，100个1分硬币，就是一种方法

annybaby

回复 1# happytc

木有想到好办法:

For $i=0 To 20
        For $j= 0 To 50
                For $k= 0 To 100
                        If ($k+$j*2+$i*5)=100 Then ConsoleWrite($k&'个1分+'&$j&'个2分+'&$i&'个5分=1元'&@LF)
                Next
        Next
Next

====================删除了结果,看得累~

annybaby

回复 2# MicroBlue

汗!!
坛子时间显示好像又有些问题了,我刚刚回复时看到只有你一个回复,而且不是这样的,我马上也贴了个,再看,你的已经是N久前修改了的~

PS:循环大的,放在越里面越好~~

happytc

没有人来发个递归的？

MicroBlue

回复 6# annybaby


    谢谢提醒！！

netegg

回复 5# annybaby

108171次？是指定终值的5倍，递归的还没整出来，上面那个代码只用计算19006次

haijie1223

Dim $x, $y, $z
Dim $i = 0
For $x = 0 To 20
        For $y = 0 To 50
                For $z = 0 To 100
                        If (5 * $x) + (2 * $y) + $z = 100 Then
                                $i += 1
                                ConsoleWrite("$x:" & $x & @TAB & " $y:" & $y & @TAB & " $z:" & $z & ";" & @TAB & $i & @CR)
                        EndIf
                Next
        Next
Next

netegg

[au3]
For $i = 0 To 20
        For $j = 0 To Int((100 - $i * 5) / 2)
                ConsoleWrite($i & '个5分+' & $j & '个2分+' & 100 - $i * 5 - $j * 2 & '个1分' & @LF)
        Next
next
[/au3]
只循环541次

happytc

回复  MicroBlue

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

"PS:循环大的,放在越里面越好~~" --- 这个可说不定，一般只能这样说：尽量保证访问的数据具有连续性，避免跳跃。并不能说循环大的在内层就效率高。
如你的代码，跟下面的比较，并不能得出：循环大的,放在越里面越好

$hTime = TimerInit()
For $i = 0 To 100
        For $j = 0 To 50
                For $k = 0 To 20
                        If ($i + $j * 2 + $k * 5) = 100 Then ConsoleWrite($i & '个1分+' & $j & '个2分+' & $k & '个5分=1元' & @LF)
                Next
        Next
Next
$iTime = TimerDiff($hTime)
MsgBox(0, 0, $iTime)

netegg

[au3]$hTime = TimerInit()
$i = 0
$o = 0
While $i <= 20
        For $j = 0 To Int((100 - $i * 5) / 2)
                ConsoleWrite($i & '个5分+' & $j & '个2分+' & 100 - $i * 5 - $j * 2 & '个1分' & @LF)
        Next
        $i += 1
WEnd
$iTime = TimerDiff($hTime)
$hTime = TimerInit()
For $i = 0 To 100
        For $j = 0 To 50
                For $k = 0 To 20
                        If ($i + $j * 2 + $k * 5) = 100 Then ConsoleWrite($i & '个1分+' & $j & '个2分+' & $k & '个5分=1元' & @LF)
                Next
        Next
Next
$iTime &= @CRLF & TimerDiff($hTime)
MsgBox(0, 0, $iTime)

[/au3]

netegg

就算最不济也比那么循环快
[au3]$hTime = TimerInit()
For $i = 0 To 100
For $j = 0 To 100 step 2
For $k = 0 To 100 step 5
        If $i +$j+$j = 100 Then ConsoleWrite($i & '+' & $j/2 & '+'&$k/5)
Next
Next
next
$iTime = TimerDiff($hTime)
MsgBox(0, 0, $iTime)
[/au3]

annybaby

回复 12# happytc

当然是针对这两种循环的放法,毫无疑问是大的放在里面更快些,不一定每说一句话都必须具有普遍性嘛

不能得出这个结论只是因为计时精度问题而已~~
比如说:

$hTime = TimerInit()
For $i=1 To 10000
        $m=1
Next
$iTime = TimerDiff($hTime)
MsgBox(0, 0, $iTime)

$hTime = TimerInit()
For $i=1 To 10001
        $m=1
Next
$iTime = TimerDiff($hTime)
MsgBox(0, 0, $iTime)

上面的循环会比下面的快一点(因为少算了一次),但是计时反映出来的结果也无法证明这一点

********************这样估计就看得出来了************

$hTime1 = TimerInit()
For $i=1 To 1000000
        For $j=1 To 10
                $s=1
        Next
Next
$iTime1 = TimerDiff($hTime1)
$hTime2 = TimerInit()
For $i=1 To 10
        For $j=1 To 1000000
                $s=1
        Next
Next
$iTime2 = TimerDiff($hTime2)
MsgBox(0, 0, $iTime1&@LF&$iTime2)

两者都是进行1千万次赋值操作,效率相差20%!!