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

dorodaloo

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

回复 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 "";
}

dorodaloo

回复 2# jason680

Call count=25
Ans  count=16

Call count=25
Ans  count=12

赞一个


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

jason680

回复 3# dorodaloo

get_coin_cyc.c 改来的

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

dorodaloo

回复 4# jason680

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

dorodaloo

回复 4# jason680

仔细再看看

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

复制代码

赞一个

dorodaloo

回复 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


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

dorodaloo

回复 2# jason680

大神
不知如何释放
怎写destroy函数

1. void destroy(Node *no) {
   
2.     /* HOW TO DESTROY? */
   
3. }

复制代码

代码

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct Node {
   
5.     unsigned ans;
   
6.     struct Node *branch;
   
7.     struct Node *node;
   
8. } Node;
   
9. 
   
10. typedef struct {
    
11.     unsigned sum;
    
12.     Node *node;
    
13. } Table;
    
14. 
    
15. Table *TAB;
    
16. unsigned SUM;
    
17. unsigned CALL;
    
18. 
    
19. unsigned gcd(unsigned, unsigned);
    
20. void calculate(unsigned *, unsigned, unsigned);
    
21. Table calUtil(unsigned *, unsigned, unsigned, unsigned *);
    
22. void print(Node *, unsigned, unsigned *, unsigned);
    
23. void destroy(Node *);
    
24. 
    
25. int main() {
    
26.     //unsigned coefficient[] = { 25, 56, 124, 345, 512 };
    
27.     //unsigned sum   = 23456;
    
28.    
    
29.     // 5a+10b+25c+50d=200   5 < 10 < 25 < 50
    
30.     unsigned coefficient[] = {5, 10, 25, 50};
    
31.     unsigned sum = 200;
    
32.     unsigned num = sizeof(coefficient) / sizeof(unsigned);
    
33. 
    
34.     calculate(coefficient, num, sum);
    
35. }
    
36. 
    
37. unsigned gcd(unsigned m, unsigned n) { return n ? gcd(n, m % n) : m; }
    
38. 
    
39. void destroy(Node *no) {
    
40.     /* HOW TO DESTROY? */
    
41. }
    
42. 
    
43. void calculate(unsigned *coefficient, unsigned num, unsigned sum) {
    
44.     CALL = 0;
    
45.     SUM = sum;
    
46.     unsigned Gcd[num];
    
47.     Gcd[0] = coefficient[0];
    
48.     for (unsigned i = 1; i < num - 1; i++)
    
49.         Gcd[i] = gcd(coefficient[i], Gcd[i - 1]);
    
50. 
    
51.     TAB = calloc(num * (SUM + 1), sizeof(Table));
    
52.     Table ret = calUtil(coefficient, num - 1, sum, Gcd);
    
53. 
    
54.     unsigned answer[num];
    
55.     printf("SUM = %u\nCOE = ", sum);
    
56.     for (int i = 0; i < num; i++) {
    
57.         printf("%d ", coefficient[i]);
    
58.     }
    
59.     printf("\n");
    
60. 
    
61.     print(ret.node, num - 1, answer, num);
    
62.     printf("COUNT = %u\n", ret.sum);
    
63.     printf("CALL  = %u\n", CALL);
    
64.    
    
65.     // HOW TO DESTROY??
    
66.     //destroy (ret.node);
    
67.     //free (TAB);
    
68. 
    
69. }
    
70. 
    
71. void print(
    
72.     Node *no,
    
73.     unsigned index,
    
74.     unsigned *ans,
    
75.     unsigned num) {
    
76.    
    
77.     if (!no) {
    
78.         for (unsigned i = 0; i < num; i++)
    
79.             printf("%u ", ans[i]);
    
80.         printf("\n");
    
81.     }
    
82.    
    
83.     while (no) {
    
84.         ans[index] = no->ans;
    
85.         print(no->branch, index - 1, ans, num);
    
86.         no = no->node;
    
87.     }
    
88. }
    
89. 
    
90. Table calUtil(
    
91.     unsigned *coefficient,
    
92.     unsigned index,
    
93.     unsigned sum,
    
94.     unsigned *Gcd) {
    
95.    
    
96.     CALL++;
    
97.     Table(*tab)[SUM + 1] = (Table(*)[SUM + 1]) TAB;
    
98. 
    
99.     if (!index) {
    
100.         Node *n = calloc(1, sizeof(Node));
     
101.         n->ans = sum / coefficient[index];
     
102.         return tab[index][sum] = (Table){1, n};
     
103.     }
     
104. 
     
105.     Table this = {0};
     
106.     unsigned newSum = sum;
     
107.     unsigned max = sum / coefficient[index];
     
108. 
     
109.     for (unsigned value = 0; value <= max; value++) {
     
110.         /* HAS SOLUTION */
     
111.         if (newSum % Gcd[index - 1] == 0) {
     
112.             Table branch = tab[index - 1][newSum].node
     
113.                 ? tab[index - 1][newSum]
     
114.                 : calUtil(coefficient, index - 1, newSum, Gcd);
     
115. 
     
116.             if (branch.sum) {
     
117.                 this.sum += branch.sum;
     
118.                 Node *node = malloc(sizeof(Node));
     
119.                 *node = (Node){value, branch.node, this.node};
     
120.                 this.node = node;
     
121.             }
     
122.         }
     
123.         newSum -= coefficient[index];
     
124.     }
     
125.     return tab[index][sum] = this;
     
126. }
     
127. 
     
128. 
     

复制代码

dorodaloo

审核中...

大神 how to write destroy function

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct Node {
   
5.     unsigned ans;
   
6.     struct Node *branch;
   
7.     struct Node *node;
   
8. } Node;
   
9. 
   
10. typedef struct {
    
11.     unsigned sum;
    
12.     Node *node;
    
13. } Table;
    
14. 
    
15. Table *TAB;
    
16. unsigned SUM;
    
17. unsigned CALL;
    
18. 
    
19. unsigned gcd(unsigned, unsigned);
    
20. void calculate(unsigned *, unsigned, unsigned);
    
21. Table calUtil(unsigned *, unsigned, unsigned, unsigned *);
    
22. void print(Node *, unsigned, unsigned *, unsigned);
    
23. void destroy(Node *);
    
24. 
    
25. int main() {
    
26.     //unsigned coefficient[] = { 25, 56, 124, 345, 512 };
    
27.     //unsigned sum   = 23456;
    
28.    
    
29.     // 5a+10b+25c+50d=200   5 < 10 < 25 < 50
    
30.     unsigned coefficient[] = {5, 10, 25, 50};
    
31.     unsigned sum = 200;
    
32.     unsigned num = sizeof(coefficient) / sizeof(unsigned);
    
33. 
    
34.     calculate(coefficient, num, sum);
    
35. }
    
36. 
    
37. unsigned gcd(unsigned m, unsigned n) { return n ? gcd(n, m % n) : m; }
    
38. 
    
39. void destroy(Node *no) {
    
40.     /* HOW TO DESTROY? */
    
41. }
    
42. 
    
43. void calculate(unsigned *coefficient, unsigned num, unsigned sum) {
    
44.     CALL = 0;
    
45.     SUM = sum;
    
46.     unsigned Gcd[num];
    
47.     Gcd[0] = coefficient[0];
    
48.     for (unsigned i = 1; i < num - 1; i++)
    
49.         Gcd[i] = gcd(coefficient[i], Gcd[i - 1]);
    
50. 
    
51.     TAB = calloc(num * (SUM + 1), sizeof(Table));
    
52.     Table ret = calUtil(coefficient, num - 1, sum, Gcd);
    
53. 
    
54.     unsigned answer[num];
    
55.     printf("SUM = %u\nCOE = ", sum);
    
56.     for (int i = 0; i < num; i++) {
    
57.         printf("%d ", coefficient[i]);
    
58.     }
    
59.     printf("\n");
    
60. 
    
61.     print(ret.node, num - 1, answer, num);
    
62.     printf("COUNT = %u\n", ret.sum);
    
63.     printf("CALL  = %u\n", CALL);
    
64.    
    
65.     // HOW TO DESTROY??
    
66.     //destroy (ret.node);
    
67.     //free (TAB);
    
68. 
    
69. }
    
70. 
    
71. void print(
    
72.     Node *no,
    
73.     unsigned index,
    
74.     unsigned *ans,
    
75.     unsigned num) {
    
76.    
    
77.     if (!no) {
    
78.         for (unsigned i = 0; i < num; i++)
    
79.             printf("%u ", ans[i]);
    
80.         printf("\n");
    
81.     }
    
82.    
    
83.     while (no) {
    
84.         ans[index] = no->ans;
    
85.         print(no->branch, index - 1, ans, num);
    
86.         no = no->node;
    
87.     }
    
88. }
    
89. 
    
90. Table calUtil(
    
91.     unsigned *coefficient,
    
92.     unsigned index,
    
93.     unsigned sum,
    
94.     unsigned *Gcd) {
    
95.    
    
96.     CALL++;
    
97.     Table(*tab)[SUM + 1] = (Table(*)[SUM + 1]) TAB;
    
98. 
    
99.     if (!index) {
    
100.         Node *n = calloc(1, sizeof(Node));
     
101.         n->ans = sum / coefficient[index];
     
102.         return tab[index][sum] = (Table){1, n};
     
103.     }
     
104. 
     
105.     Table this = {0};
     
106.     unsigned newSum = sum;
     
107.     unsigned max = sum / coefficient[index];
     
108. 
     
109.     for (unsigned value = 0; value <= max; value++) {
     
110.         /* HAS SOLUTION */
     
111.         if (newSum % Gcd[index - 1] == 0) {
     
112.             Table branch = tab[index - 1][newSum].node
     
113.                 ? tab[index - 1][newSum]
     
114.                 : calUtil(coefficient, index - 1, newSum, Gcd);
     
115. 
     
116.             if (branch.sum) {
     
117.                 this.sum += branch.sum;
     
118.                 Node *node = malloc(sizeof(Node));
     
119.                 *node = (Node){value, branch.node, this.node};
     
120.                 this.node = node;
     
121.             }
     
122.         }
     
123.         newSum -= coefficient[index];
     
124.     }
     
125.     return tab[index][sum] = this;
     
126. }
     
127. 
     
128. 
     

复制代码

dorodaloo

尼玛, 发一帖究竟要审核多久