关于求5元硬币找零的问题

dorodaloo

回复 10# jason680
大牛求
get_coin_cyc1的代码

jason680

回复 11# dorodaloo

$ time ./get_coin_cyc2 3000; time ./get_coin_cyc1 3000
   Total count=452756092626
function count=14708260

real    0m1.067s
user    0m0.468s
sys    0m0.004s
   Total count=452756092626
function count=1795441446

real    0m47.081s
user    0m22.777s
sys    0m0.072s

get_coin_cyc.c
  if(--num == 0) return 1;

get_coin_cyc1.c
  if(--num == 1) return( ... );

get_coin_cyc2.c
  --num
  if(num == 2&& money%5==0) return( ... );
  if(num == 1) return( ... );

wslm31

#include <stdio.h>
#define MAX 50
int main(int argc,char* argv[])
{
        int count=0;
        for(int i=0;i<=5;i++)
        {
                for(int j=0;j<=10;j++)
                {
                        for(int k=0;k<=50;k++)
                        {
                                if(i*10+j*5+k==50)
                                        {
                                                count++;
                                                printf("1元硬币：%d;5角硬币：%d;1角硬币：%d\n",i,j,k);
                                                }
                                }
                        }
                }
                printf("总方法：%d\n",count);
        return 0;
        }

dorodaloo

回复 12# jason680

大牛求get_coin_cyc2代码

dorodaloo

回复 12# jason680

越来越牛逼，结果还是令人震惊的，竟然只有1s

jason680

dorodaloo 发表于 2017-12-28 13:17
回复 10# jason680
大牛求
get_coin_cyc1的代码

找出"更快"的算法/方法...

money=0
5 2 1
------
x 0 0
count = 1

money=1
5 2 1
------
x 0 1
count = 1

money=2
5 2 1
------
x 0 2
x 1 0
count = 2

money=3
5 2 1
------
x 0 3
x 1 1
count = 2

money=4
5 2 1
------
x 0 4
x 1 2
x 2 0
count = 3

money=5
5 2 1
------
x 0 5
x 1 3
x 2 1
count = 3

...

money 0,1,2,3,4,5,...
count  1,1,2,2,3,3,....

// get_coin_cyc1.c
if(--num == 1) return(money/2+1);

// get_coin_cyc.c
if(--num == 0) return 1;


Note: in coin array
... [3] [2] [1] [0]  <== num
...  10  5    2    1  <== value

dorodaloo

回复 16# jason680

非常感谢
太强了，绝对要顶啊.

这一般不单纯啊

bskay

用python (C++++)

count = []
for c10 in range(6):
    s0 = c10*10
    if s0 > 50:
        break
    for c5 in range(11):
        s1 = s0+c5*5
        if s1 > 50:
            break
        for c1 in range(51):
            s2 = s1+c1
            if s2 == 50:
                count.append((c10,c5,c1))
            if s2 > 50:
                break
print len(count)