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

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 徽章 文库 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 1138 | 回复: 4

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

论坛徽章:
5
数据库技术版块每日发帖之星
日期: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:44
发表于 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. }


复制代码


打赏鼓励一下!

论坛徽章:
128
技术图书徽章
日期: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}

论坛徽章:
5
数据库技术版块每日发帖之星
日期: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:44
发表于 2018-02-13 17:11 |显示全部楼层
回复 2# jason680
感谢回复

这是用眼睛解题啊

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

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

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






论坛徽章:
128
技术图书徽章
日期: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

论坛徽章:
5
数据库技术版块每日发帖之星
日期: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:44
发表于 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


您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP