dorodaloo 发表于 2018-01-26 17:27

N元一次不定方程求整数解

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

jason680 发表于 2018-01-27 12:00

回复 1# dorodaloo

$ awk -f get_sol.awk get_sol.txt
753 50
----------
01 15
04 10
075
0 100
12 11
156
181
20 12
237
262
318
343
424
505
530
611
Call count=25
Anscount=16

198 180 175 11550
-----------------
0   066
03530
51248
54712
102430
15   148
153612
201330
252512
30   230
351412
45   312
Call count=25
Anscount=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 = $n
    n1 = n+1;
    if ($n<$n1&&n!=at) err($n"<"$n1);
}
}
func get_b() {
delete b;
b = a;
for(n=1; n<at; n+=1) {
    b = xd(a, b)
}
if (b != xd(m,b)){
    print "***NO Solution***";
    next;
}
}
func dm(m) {
for (n=0; n<at; n+=1) {
    w = length(a);
    sLen    = length(int(m/a));
    if(w < sLen ) {
       w = sLen;
    }
}
s = "";
for(n=at-1; n>=0; n-=1) {
    s = sprintf("%s%*d ",s,w, a);
}
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, v);
}
print s;
ans_cnt += 1;
}

func sol(a,t,m, cyc,n){
sol_cnt += 1;
t -= 1;
#print "t="t",a["t"]="a",m="m;
if(t == 0){
    if(m%a==0){
      v = int(m/a);
      get_ans();
    }
    return;
}
cyc = int(m/a+1);
for (n=0; n<cyc; n+=1) {
    nm = m - n * a;
    if(ck(nm,b)){
      v = 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 "Anscount="ans_cnt;
print "";
}

dorodaloo 发表于 2018-01-27 19:34

回复 2# jason680

Call count=25
Anscount=16

Call count=25
Anscount=12
赞一个{:qq11:}


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

jason680 发表于 2018-01-27 20:02

回复 3# dorodaloo

get_coin_cyc.c 改来的

http://bbs.chinaunix.net/forum.php?mod=redirect&goto=findpost&ptid=4291348&pid=24679072&fromuid=24785593

dorodaloo 发表于 2018-01-27 20:20

回复 4# jason680

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

dorodaloo 发表于 2018-01-29 21:18

回复 4# jason680

仔细再看看

    if (CHECK(nm, b)){
      v = n;
      cnt += sol(a, t, nm);
    }



赞一个{:qq11:}

dorodaloo 发表于 2018-02-01 19:23

回复 4# jason680

赞一个{:qq11:}

get_sol.awk

512 345 1245625 23456
-------------------------
0   0   0   1 936
0   0   026 880
0   0   051 824
...
44   0   2   516
44   0   3   120
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


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

dorodaloo 发表于 2018-02-11 21:05

回复 2# jason680

大神
不知如何释放
怎写destroy函数
void destroy(Node *no) {
    /* HOW TO DESTROY? */
}
代码
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    unsigned ans;
    struct Node *branch;
    struct Node *node;
} Node;

typedef struct {
    unsigned sum;
    Node *node;
} Table;

Table *TAB;
unsigned SUM;
unsigned CALL;

unsigned gcd(unsigned, unsigned);
void calculate(unsigned *, unsigned, unsigned);
Table calUtil(unsigned *, unsigned, unsigned, unsigned *);
void print(Node *, unsigned, unsigned *, unsigned);
void destroy(Node *);

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

    calculate(coefficient, num, sum);
}

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

void destroy(Node *no) {
    /* HOW TO DESTROY? */
}

void calculate(unsigned *coefficient, unsigned num, unsigned sum) {
    CALL = 0;
    SUM = sum;
    unsigned Gcd;
    Gcd = coefficient;
    for (unsigned i = 1; i < num - 1; i++)
      Gcd = gcd(coefficient, Gcd);

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

    unsigned answer;
    printf("SUM = %u\nCOE = ", sum);
    for (int i = 0; i < num; i++) {
      printf("%d ", coefficient);
    }
    printf("\n");

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

}

void print(
    Node *no,
    unsigned index,
    unsigned *ans,
    unsigned num) {
   
    if (!no) {
      for (unsigned i = 0; i < num; i++)
            printf("%u ", ans);
      printf("\n");
    }
   
    while (no) {
      ans = no->ans;
      print(no->branch, index - 1, ans, num);
      no = no->node;
    }
}

Table calUtil(
    unsigned *coefficient,
    unsigned index,
    unsigned sum,
    unsigned *Gcd) {
   
    CALL++;
    Table(*tab) = (Table(*)) TAB;

    if (!index) {
      Node *n = calloc(1, sizeof(Node));
      n->ans = sum / coefficient;
      return tab = (Table){1, n};
    }

    Table this = {0};
    unsigned newSum = sum;
    unsigned max = sum / coefficient;

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

            if (branch.sum) {
                this.sum += branch.sum;
                Node *node = malloc(sizeof(Node));
                *node = (Node){value, branch.node, this.node};
                this.node = node;
            }
      }
      newSum -= coefficient;
    }
    return tab = this;
}




dorodaloo 发表于 2018-02-11 21:07

本帖最后由 dorodaloo 于 2018-02-11 21:09 编辑

审核中...:time::time:

大神 how to write destroy function
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    unsigned ans;
    struct Node *branch;
    struct Node *node;
} Node;

typedef struct {
    unsigned sum;
    Node *node;
} Table;

Table *TAB;
unsigned SUM;
unsigned CALL;

unsigned gcd(unsigned, unsigned);
void calculate(unsigned *, unsigned, unsigned);
Table calUtil(unsigned *, unsigned, unsigned, unsigned *);
void print(Node *, unsigned, unsigned *, unsigned);
void destroy(Node *);

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

    calculate(coefficient, num, sum);
}

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

void destroy(Node *no) {
    /* HOW TO DESTROY? */
}

void calculate(unsigned *coefficient, unsigned num, unsigned sum) {
    CALL = 0;
    SUM = sum;
    unsigned Gcd;
    Gcd = coefficient;
    for (unsigned i = 1; i < num - 1; i++)
      Gcd = gcd(coefficient, Gcd);

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

    unsigned answer;
    printf("SUM = %u\nCOE = ", sum);
    for (int i = 0; i < num; i++) {
      printf("%d ", coefficient);
    }
    printf("\n");

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

}

void print(
    Node *no,
    unsigned index,
    unsigned *ans,
    unsigned num) {
   
    if (!no) {
      for (unsigned i = 0; i < num; i++)
            printf("%u ", ans);
      printf("\n");
    }
   
    while (no) {
      ans = no->ans;
      print(no->branch, index - 1, ans, num);
      no = no->node;
    }
}

Table calUtil(
    unsigned *coefficient,
    unsigned index,
    unsigned sum,
    unsigned *Gcd) {
   
    CALL++;
    Table(*tab) = (Table(*)) TAB;

    if (!index) {
      Node *n = calloc(1, sizeof(Node));
      n->ans = sum / coefficient;
      return tab = (Table){1, n};
    }

    Table this = {0};
    unsigned newSum = sum;
    unsigned max = sum / coefficient;

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

            if (branch.sum) {
                this.sum += branch.sum;
                Node *node = malloc(sizeof(Node));
                *node = (Node){value, branch.node, this.node};
                this.node = node;
            }
      }
      newSum -= coefficient;
    }
    return tab = this;
}



dorodaloo 发表于 2018-02-11 21:13

尼玛, 发一帖究竟要审核多久:time:
页: [1] 2
查看完整版本: N元一次不定方程求整数解