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

ChinaUnix.net

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

[数值计算] N元一次不定方程求整数解 [复制链接]

论坛徽章:
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-01-26 17:27 |显示全部楼层
N元一次不定方程求整数解

test =
198a+180b+175c=11550
512a+345b+124c+56d=23456
1999a+1299b+1499c+2799d+2499e+3299f=2328450

a, b, c ...  >= 0 整数解

运行示例
func 198a+180b+175c=11550
输出

0 0 66
0 35 30
5 12 48
5 47 12
10 24 30
15 1 48
15 36 12
20 13 30
25 25 12
30 2 30
35 14 12
45 3 12
count = 12

论坛徽章:
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-01-27 12:00 |显示全部楼层
回复 1# dorodaloo

$ awk -f get_sol.awk get_sol.txt
7  5  3 50
----------
0  1 15
0  4 10
0  7  5
0 10  0
1  2 11
1  5  6
1  8  1
2  0 12
2  3  7
2  6  2
3  1  8
3  4  3
4  2  4
5  0  5
5  3  0
6  1  1
Call count=25
Ans  count=16

198 180 175 11550
-----------------
  0   0  66
  0  35  30
  5  12  48
  5  47  12
10  24  30
15   1  48
15  36  12
20  13  30
25  25  12
30   2  30
35  14  12
45   3  12
Call count=25
Ans  count=12


$ cat get_sol.txt
# a1*x1 + a2*x2 + a3*x3 + ...  = sum
#  a1 > a2 > a3 ... > 0,         sum > a1
   7       5        3       50
   198     180      175     11550
#   512     345      124     56   23456
#   3299    2799     2499    1999 1499 1299 2328450

$ cat get_sol.awk

func xd(p,q)  { return (q?xd(q,(p%q)):p) }
func ck(p,q) { return (!(p%q)) }

func err(s) {
  print "\n*** ERR *** "s;
  exit;
}

func get_a() {
  delete a;
  at = NF-1;
  for(n=1; n<=at; n+=1) {
    a[at-n] = $n
    n1 = n+1;
    if ($n<$n1&&n!=at) err($n"<"$n1);
  }
}
func get_b() {
  delete b;
  b[0] = a[0];
  for(n=1; n<at; n+=1) {
    b[n] = xd(a[n], b[n-1])
  }
  if (b[at-1] != xd(m,b[at-1])){
    print "***NO Solution***";
    next;
  }
}
func dm(m) {
  for (n=0; n<at; n+=1) {
    w[n] = length(a[n]);
    sLen    = length(int(m/a[n]));
    if(w[n] < sLen ) {
       w[n] = sLen;
    }
  }
  s = "";
  for(n=at-1; n>=0; n-=1) {
    s = sprintf("%s%*d ",s,w[n], a[n]);
  }
  x=s m;
  gsub(".","-",x);
  print s m
  print x;
}
func init(m) {
  get_a();
  dm(m);
  get_b();
}

func get_ans( n) {
  s = "";
  for(n=at-1; n>=0; n-=1) {
    s = sprintf("%s%*d ", s, w[n], v[n]);
  }
  print s;
  ans_cnt += 1;
}

func sol(a,t,m, cyc,n){
  sol_cnt += 1;
  t -= 1;
  #print "t="t",a["t"]="a[t]",m="m;
  if(t == 0){
    if(m%a[0]==0){
      v[0] = int(m/a[0]);
      get_ans();
    }
    return;
  }
  cyc = int(m/a[t]+1);
  for (n=0; n<cyc; n+=1) {
    nm = m - n * a[t];
    if(ck(nm,b[t-1])){
      v[t] = n;
      cnt += sol(a, t, nm);
    }
  }
}
{
  if (/^#/) next;
  sol_cnt=0;
  ans_cnt=0;
  m = $NF;
  init(m);
  sol(a,at,m);
  print "Call count="sol_cnt;
  print "Ans  count="ans_cnt;
  print "";
}

评分

参与人数 1信誉积分 +10 收起 理由
dorodaloo + 10 很给力!

查看全部评分

论坛徽章:
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-01-27 19:34 |显示全部楼层
回复 2# jason680
Call count=25
Ans  count=16

Call count=25
Ans  count=12

赞一个


看得云里雾里
一头雾水,大神,
有没有C版本的

论坛徽章:
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-01-27 20:02 |显示全部楼层
回复 3# dorodaloo

get_coin_cyc.c 改来的

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

评分

参与人数 1信誉积分 +10 收起 理由
dorodaloo + 10 很给力!

查看全部评分

论坛徽章:
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-01-27 20:20 |显示全部楼层
回复 4# jason680

仔细再看
竟然是同一道题
大神,求C代码
求get_coin_cyc2代码

论坛徽章:
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-01-29 21:18 |显示全部楼层
回复 4# jason680

仔细再看看

  1.     if (CHECK(nm, b[t - 1])){
  2.       v[t] = n;
  3.       cnt += sol(a, t, nm);
  4.     }
复制代码




赞一个

论坛徽章:
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-01 19:23 |显示全部楼层
回复 4# jason680

赞一个

get_sol.awk

512 345 124  56  25 23456
-------------------------
  0   0   0   1 936
  0   0   0  26 880
  0   0   0  51 824
...
44   0   2   5  16
44   0   3   1  20
45   0   2   3   0
COUNT = 449699
CALL  = 555841

get_sol2.c

SUM = 23456
COE = 25 56 124 345 512
0 3 2 0 45
20 1 3 0 44
16 5 2 0 44
...
824 51 0 0 0
880 26 0 0 0
936 1 0 0 0
COUNT = 449699
CALL  = 25536


帮我解决这个问题,非常感谢

论坛徽章:
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 21:05 |显示全部楼层
回复 2# jason680

大神
不知如何释放
怎写destroy函数
  1. void destroy(Node *no) {
  2.     /* HOW TO DESTROY? */
  3. }
复制代码

代码
  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. }


复制代码


论坛徽章:
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 21:07 |显示全部楼层
本帖最后由 dorodaloo 于 2018-02-11 21:09 编辑

审核中...

大神 how to write destroy function
  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. }


复制代码

论坛徽章:
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 21:13 |显示全部楼层
尼玛, 发一帖究竟要审核多久
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP