不知道free怎么写

dorodaloo

N元一次不定方程整数解的 free



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

这里系数由大到小排列: 5 < 10 < 25 < 50
a, b, c, d ... 都是整数 >= 0

// 代码可以省略解析字符串  "5a+10b+25c+50d=200" 过程
unsigned coe[] = {5, 10, 25, 50};
unsigned sum = 200;
   


非常感谢, 不知道destroy怎么写？

代码:

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct Node {
   
5.     unsigned ans;
   
6.     struct Node *branch;
   
7.     struct Node *node;
   
8. } Node;
   
9. 
   
10. typedef struct {
    
11.     unsigned sum;
    
12.     Node *node;
    
13. } Table;
    
14. 
    
15. Table *TAB;
    
16. unsigned SUM;
    
17. unsigned CALL;
    
18. 
    
19. unsigned gcd(unsigned, unsigned);
    
20. void calculate(unsigned *, unsigned, unsigned);
    
21. Table calUtil(unsigned *, unsigned, unsigned, unsigned *);
    
22. void print(Node *, unsigned, unsigned *, unsigned);
    
23. void destroy(Node *);
    
24. 
    
25. int main() {
    
26.     //unsigned coefficient[] = { 25, 56, 124, 345, 512 };
    
27.     //unsigned sum   = 23456;
    
28.    
    
29.     // 5a+10b+25c+50d=200   5 < 10 < 25 < 50
    
30.     unsigned coefficient[] = {5, 10, 25, 50};
    
31.     unsigned sum = 200;
    
32.     unsigned num = sizeof(coefficient) / sizeof(unsigned);
    
33. 
    
34.     calculate(coefficient, num, sum);
    
35. }
    
36. 
    
37. unsigned gcd(unsigned m, unsigned n) { return n ? gcd(n, m % n) : m; }
    
38. 
    
39. void destroy(Node *no) {
    
40.     /* HOW TO DESTROY? */
    
41. }
    
42. 
    
43. void calculate(unsigned *coefficient, unsigned num, unsigned sum) {
    
44.     CALL = 0;
    
45.     SUM = sum;
    
46.     unsigned Gcd[num];
    
47.     Gcd[0] = coefficient[0];
    
48.     for (unsigned i = 1; i < num - 1; i++)
    
49.         Gcd[i] = gcd(coefficient[i], Gcd[i - 1]);
    
50. 
    
51.     TAB = calloc(num * (SUM + 1), sizeof(Table));
    
52.     Table ret = calUtil(coefficient, num - 1, sum, Gcd);
    
53. 
    
54.     unsigned answer[num];
    
55.     printf("SUM = %u\nCOE = ", sum);
    
56.     for (int i = 0; i < num; i++) {
    
57.         printf("%d ", coefficient[i]);
    
58.     }
    
59.     printf("\n");
    
60. 
    
61.     print(ret.node, num - 1, answer, num);
    
62.     printf("COUNT = %u\n", ret.sum);
    
63.     printf("CALL  = %u\n", CALL);
    
64.    
    
65.     // HOW TO DESTROY??
    
66.     //destroy (ret.node);
    
67.     //free (TAB);
    
68. 
    
69. }
    
70. 
    
71. void print(
    
72.     Node *no,
    
73.     unsigned index,
    
74.     unsigned *ans,
    
75.     unsigned num) {
    
76.    
    
77.     if (!no) {
    
78.         for (unsigned i = 0; i < num; i++)
    
79.             printf("%u ", ans[i]);
    
80.         printf("\n");
    
81.     }
    
82.    
    
83.     while (no) {
    
84.         ans[index] = no->ans;
    
85.         print(no->branch, index - 1, ans, num);
    
86.         no = no->node;
    
87.     }
    
88. }
    
89. 
    
90. Table calUtil(
    
91.     unsigned *coefficient,
    
92.     unsigned index,
    
93.     unsigned sum,
    
94.     unsigned *Gcd) {
    
95.    
    
96.     CALL++;
    
97.     Table(*tab)[SUM + 1] = (Table(*)[SUM + 1]) TAB;
    
98. 
    
99.     if (!index) {
    
100.         Node *n = calloc(1, sizeof(Node));
     
101.         n->ans = sum / coefficient[index];
     
102.         return tab[index][sum] = (Table){1, n};
     
103.     }
     
104. 
     
105.     Table this = {0};
     
106.     unsigned newSum = sum;
     
107.     unsigned max = sum / coefficient[index];
     
108. 
     
109.     for (unsigned value = 0; value <= max; value++) {
     
110.         /* HAS SOLUTION */
     
111.         if (newSum % Gcd[index - 1] == 0) {
     
112.             Table branch = tab[index - 1][newSum].node
     
113.                 ? tab[index - 1][newSum]
     
114.                 : calUtil(coefficient, index - 1, newSum, Gcd);
     
115. 
     
116.             if (branch.sum) {
     
117.                 this.sum += branch.sum;
     
118.                 Node *node = malloc(sizeof(Node));
     
119.                 *node = (Node){value, branch.node, this.node};
     
120.                 this.node = node;
     
121.             }
     
122.         }
     
123.         newSum -= coefficient[index];
     
124.     }
     
125.     return tab[index][sum] = this;
     
126. }
     
127. 
     
128. 
     

复制代码

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}

dorodaloo

回复 2# jason680
感谢回复

这是用眼睛解题啊

如用户输入?
3a+5b+23c=556

或者是
unsigned coefficient[] = { 25, 56, 124, 345, 512 };
unsigned sum   = 23456;

这一帖.的问题是
如何写destory函数

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

dorodaloo

回复 4# jason680


感谢回复

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


1楼
COUNT = 473
CALL  = 197

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

dorodaloo

回复 6# jason680

感谢回复

Call count=26

赞一个

大神,求代码

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

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

dorodaloo

回复 6# jason680

看不到帖子
发一帖究竟要审核多久

shang2010

shell处理数值，感觉很快很强大