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

ChinaUnix.net

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

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

论坛徽章:
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-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

论坛徽章:
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-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 很给力!

查看全部评分

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

Call count=25
Ans  count=12

赞一个


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

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

get_coin_cyc.c 改来的

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

评分

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

查看全部评分

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

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

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

仔细再看看

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




赞一个

论坛徽章:
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-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


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

论坛徽章:
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 21:13 |显示全部楼层
尼玛, 发一帖究竟要审核多久

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


审核了一天,终于通过
大神,这个destroy函数怎么个写法

http://bbs.chinaunix.net/thread-4292613-1-1.html

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

本版积分规则

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP