忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 2601 | 回复: 9

[C] 不知道free怎么写 [复制链接]

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-02-11 20:52 |显示全部楼层
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. typedef struct Node {
  4.     unsigned ans;
  5.     struct Node *branch;
  6.     struct Node *node;
  7. } Node;

  8. typedef struct {
  9.     unsigned sum;
  10.     Node *node;
  11. } Table;

  12. Table *TAB;
  13. unsigned SUM;
  14. unsigned CALL;

  15. unsigned gcd(unsigned, unsigned);
  16. void calculate(unsigned *, unsigned, unsigned);
  17. Table calUtil(unsigned *, unsigned, unsigned, unsigned *);
  18. void print(Node *, unsigned, unsigned *, unsigned);
  19. void destroy(Node *);

  20. int main() {
  21.     //unsigned coefficient[] = { 25, 56, 124, 345, 512 };
  22.     //unsigned sum   = 23456;
  23.    
  24.     // 5a+10b+25c+50d=200   5 < 10 < 25 < 50
  25.     unsigned coefficient[] = {5, 10, 25, 50};
  26.     unsigned sum = 200;
  27.     unsigned num = sizeof(coefficient) / sizeof(unsigned);

  28.     calculate(coefficient, num, sum);
  29. }

  30. unsigned gcd(unsigned m, unsigned n) { return n ? gcd(n, m % n) : m; }

  31. void destroy(Node *no) {
  32.     /* HOW TO DESTROY? */
  33. }

  34. void calculate(unsigned *coefficient, unsigned num, unsigned sum) {
  35.     CALL = 0;
  36.     SUM = sum;
  37.     unsigned Gcd[num];
  38.     Gcd[0] = coefficient[0];
  39.     for (unsigned i = 1; i < num - 1; i++)
  40.         Gcd[i] = gcd(coefficient[i], Gcd[i - 1]);

  41.     TAB = calloc(num * (SUM + 1), sizeof(Table));
  42.     Table ret = calUtil(coefficient, num - 1, sum, Gcd);

  43.     unsigned answer[num];
  44.     printf("SUM = %u\nCOE = ", sum);
  45.     for (int i = 0; i < num; i++) {
  46.         printf("%d ", coefficient[i]);
  47.     }
  48.     printf("\n");

  49.     print(ret.node, num - 1, answer, num);
  50.     printf("COUNT = %u\n", ret.sum);
  51.     printf("CALL  = %u\n", CALL);
  52.    
  53.     // HOW TO DESTROY??
  54.     //destroy (ret.node);
  55.     //free (TAB);

  56. }

  57. void print(
  58.     Node *no,
  59.     unsigned index,
  60.     unsigned *ans,
  61.     unsigned num) {
  62.    
  63.     if (!no) {
  64.         for (unsigned i = 0; i < num; i++)
  65.             printf("%u ", ans[i]);
  66.         printf("\n");
  67.     }
  68.    
  69.     while (no) {
  70.         ans[index] = no->ans;
  71.         print(no->branch, index - 1, ans, num);
  72.         no = no->node;
  73.     }
  74. }

  75. Table calUtil(
  76.     unsigned *coefficient,
  77.     unsigned index,
  78.     unsigned sum,
  79.     unsigned *Gcd) {
  80.    
  81.     CALL++;
  82.     Table(*tab)[SUM + 1] = (Table(*)[SUM + 1]) TAB;

  83.     if (!index) {
  84.         Node *n = calloc(1, sizeof(Node));
  85.         n->ans = sum / coefficient[index];
  86.         return tab[index][sum] = (Table){1, n};
  87.     }

  88.     Table this = {0};
  89.     unsigned newSum = sum;
  90.     unsigned max = sum / coefficient[index];

  91.     for (unsigned value = 0; value <= max; value++) {
  92.         /* HAS SOLUTION */
  93.         if (newSum % Gcd[index - 1] == 0) {
  94.             Table branch = tab[index - 1][newSum].node
  95.                 ? tab[index - 1][newSum]
  96.                 : calUtil(coefficient, index - 1, newSum, Gcd);

  97.             if (branch.sum) {
  98.                 this.sum += branch.sum;
  99.                 Node *node = malloc(sizeof(Node));
  100.                 *node = (Node){value, branch.node, this.node};
  101.                 this.node = node;
  102.             }
  103.         }
  104.         newSum -= coefficient[index];
  105.     }
  106.     return tab[index][sum] = this;
  107. }


复制代码


打赏鼓励一下!

论坛徽章:
130
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07巳蛇
日期:2014-05-09 16:43:18巨蟹座
日期:2014-10-23 17:48:38子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59
发表于 2018-02-12 20:20 |显示全部楼层
回复 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}

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-02-13 17:11 |显示全部楼层
回复 2# jason680
感谢回复

这是用眼睛解题啊

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

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

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






论坛徽章:
130
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07巳蛇
日期:2014-05-09 16:43:18巨蟹座
日期:2014-10-23 17:48:38子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59
发表于 2018-02-13 21:49 |显示全部楼层
回复 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

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-02-14 19:15 |显示全部楼层
回复 4# jason680


感谢回复

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


1楼
COUNT = 473
CALL  = 197


论坛徽章:
130
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07巳蛇
日期:2014-05-09 16:43:18巨蟹座
日期:2014-10-23 17:48:38子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59
发表于 2018-02-24 22:14 |显示全部楼层
回复 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

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-02-25 10:01 |显示全部楼层
回复 6# jason680

感谢回复
Call count=26

赞一个

大神,求代码

论坛徽章:
130
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07巳蛇
日期:2014-05-09 16:43:18巨蟹座
日期:2014-10-23 17:48:38子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59
发表于 2018-02-28 09:13 |显示全部楼层
回复 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

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

论坛徽章:
6
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:4415-16赛季CBA联赛之北京
日期:2018-03-04 17:01:50
发表于 2018-02-28 15:32 |显示全部楼层
回复 6# jason680

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

论坛徽章:
130
操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57数据库技术版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:052022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57IT运维版块每日发帖之星
日期:2016-05-11 17:06:49操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57程序设计版块每日发帖之星
日期:2016-05-11 17:06:57
发表于 2018-02-28 16:13 来自手机 |显示全部楼层
shell处理数值,感觉很快很强大
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:wangnan@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP