不知道free怎么写

jason680

回复 1# dorodaloo

They are the same issue

5a+10b+25c+50d=200

-------------------------------------


http://bbs.chinaunix.net/forum.p ... mp;fromuid=24785593

int coin[] = { 1, 2, 5, 10, 20, 25, 50 };

   {1,2,5,10} x5
={5,10,25,50}

jason680

回复 3# dorodaloo

http://bbs.chinaunix.net/forum.p ... mp;fromuid=24785593

$ echo 23 5 3 556 | awk -f get_sol.awk
23   5   3 556
--------------
0   2 182
0   5 177
0   8 172
0  11 167
...
22  10   0
23   0   9
23   3   4
Call count=499
Ans  count=473

jason680

回复 5# dorodaloo

$ echo 23 5 3 556 | awk -f get_sol.awk | grep count
Call count=499
Ans  count=473

$ echo 23 5 3 556 | awk -f get_sol1.awk | grep count
Call count=26
Ans  count=473

$ echo 23 5 3 556 | awk -f get_sol2.awk | grep count
Call count=26
Ans  count=473

$ echo 23 5 3 556 | awk -f get_sol3.awk | grep count
Call count=26
Ans  count=473

$ echo 50 25 10 5 2000 | awk -f get_sol.awk | grep count
Call count=115744
Ans  count=114021

$ echo 50 25 10 5 2000 | awk -f get_sol1.awk | grep count
Call count=1723
Ans  count=114021

$ echo 50 25 10 5 2000 | awk -f get_sol2.awk | grep count
Call count=123
Ans  count=114021

$ echo 50 25 10 5 2000 | awk -f get_sol3.awk | grep count
Call count=123
Ans  count=114021

$ echo 512 345 124  56  25 23456 | awk -f get_sol.awk | grep count
Call count=555841
Ans  count=449699

$ echo 512 345 124  56  25 23456 | awk -f get_sol1.awk | grep count
Call count=106142
Ans  count=449699

$ echo 512 345 124  56  25 23456 | awk -f get_sol2.awk | grep count
Call count=101302
Ans  count=449699

$ echo 512 345 124  56  25 23456 | awk -f get_sol3.awk | grep count
Call count=16984
Ans  count=449699

jason680

回复 7# dorodaloo

想法与算法...
get_solX.awk与get_coin_cycX.c想法也差不多
属同一个问题
递归调用，可得知答案（值）时返回

以图23A+5B+3C=556为例
get_sol.awk算法

$ echo 23 5 3 556 | awk -f get_sol.awk  
23   5   3 556
--------------
0   2 182
0   5 177
0   8 172
0  11 167
0  14 162
...
22   7   5
22  10   0
23   0   9
23   3   4
Call count=499
Ans  count=473


算法提高 get_sol1.awk算法

0   2 182   
0   5 177
0   8 172
...
0 110   2

算法提高，
0 2 x
...
0 110 x
若能在t = 1时，就可知所有答案(值)，则不须再递归调用
0 n0 x0
0 n1 x1
0 n2 x2
...
0 nn xn

23   5   3 556
--------------
0   2   x   ==>找23*0 所有答案

sum = 556 - 23*0 - 5*2 = 546

n = 取整( 546 / (5 * 3 / gcd(5,3)) )  
由0到n, n值再加1

int(546/15)+1 ==>37


23   5   3 556
--------------
1   1 176 ==>找23*1 所有答案

sum = 556 - 23*1 - 5*1 = 528

int(528/15)+1 ==>36


-------------------------------------------------------
  for (n=0; n<cyc; n+=1) {
    nm = m - n * a[t];
    if(ck(nm,b[t-1])){
      v[t] = n;
      if(t==1){
        return(int(nm/(a[1]*a[0]/b[1]))+1)
      }


=======================================

算法提高 get_sol2.awk算法
t=2, sum=546, 递归调用 得37
t=2, sum=528, 递归调用 得36
...

下次再有t=2, sum=546, 不须再递归调用,直接得37

优点： 不须重复递归调用
缺点： 须纪录复递归调用结果

$ diff get_sol1.awk get_sol2.awk
82,88c82,91
<       #if(t==2&& t"-"nm in c){
<       #  cnt += c[t"-"nm];
<       #  contine;
<       #}
<       x= sol(a, t, nm);
<       if(t==2) c[t"-"nm]=x;
<       cnt += x;
---
>       if(t==2 && (t"-"nm in c)){   #下次再有t=2, sum=546, 不须再递归调用,直接得37
>         #print "get",t,nm,c[t"-"nm];
>         cnt += c[t"-"nm];
>         continue;
>       }
>       xc= sol(a, t, nm);
>       if(t==2){ c[t"-"nm]=xc;  #须纪录复递归调用结果
>         #print t,nm,c[t"-"nm];
>       }
>       cnt += xc;



=======================================

算法提高 get_sol3.awk算法(与get_sol2.awk算法一样, t=3)
t=3, sum=x1, 递归调用 得N1
t=3, sum=x2, 递归调用 得N2
...

下次再有t=3, sum=x1, 不须再递归调用,直接得N1

优点： 不须重复递归调用
缺点： 须纪录复递归调用结果