1 | #include <stdlib.h>
|
---|
2 | #include <stdio.h>
|
---|
3 |
|
---|
4 | #define N 20
|
---|
5 |
|
---|
6 | int nb_num;
|
---|
7 | int tab[N];
|
---|
8 | int stack_ptr;
|
---|
9 | int stack_op[N];
|
---|
10 | int stack_res[60];
|
---|
11 | int result;
|
---|
12 |
|
---|
13 | int find(int n, int i1, int a, int b, int op)
|
---|
14 | {
|
---|
15 | int i, j;
|
---|
16 | int c;
|
---|
17 |
|
---|
18 | if (stack_ptr >= 0) {
|
---|
19 | stack_res[3*stack_ptr] = a;
|
---|
20 | stack_op[stack_ptr] = op;
|
---|
21 | stack_res[3*stack_ptr+1] = b;
|
---|
22 | stack_res[3*stack_ptr+2] = n;
|
---|
23 | if (n == result)
|
---|
24 | return 1;
|
---|
25 | tab[i1] = n;
|
---|
26 | }
|
---|
27 |
|
---|
28 | for(i=0;i<nb_num;i++) {
|
---|
29 | for(j=i+1;j<nb_num;j++) {
|
---|
30 | a = tab[i];
|
---|
31 | b = tab[j];
|
---|
32 | if (a != 0 && b != 0) {
|
---|
33 |
|
---|
34 | tab[j] = 0;
|
---|
35 | stack_ptr++;
|
---|
36 |
|
---|
37 | if (find(a + b, i, a, b, '+'))
|
---|
38 | return 1;
|
---|
39 | if (find(a - b, i, a, b, '-'))
|
---|
40 | return 1;
|
---|
41 | if (find(b - a, i, b, a, '-'))
|
---|
42 | return 1;
|
---|
43 | if (find(a * b, i, a, b, '*'))
|
---|
44 | return 1;
|
---|
45 | if (b != 0) {
|
---|
46 | c = a / b;
|
---|
47 | if (find(c, i, a, b, '/'))
|
---|
48 | return 1;
|
---|
49 | }
|
---|
50 |
|
---|
51 | if (a != 0) {
|
---|
52 | c = b / a;
|
---|
53 | if (find(c, i, b, a, '/'))
|
---|
54 | return 1;
|
---|
55 | }
|
---|
56 |
|
---|
57 | stack_ptr--;
|
---|
58 | tab[i] = a;
|
---|
59 | tab[j] = b;
|
---|
60 | }
|
---|
61 | }
|
---|
62 | }
|
---|
63 |
|
---|
64 | return 0;
|
---|
65 | }
|
---|
66 |
|
---|
67 | int main(int argc, char **argv)
|
---|
68 | {
|
---|
69 | int i, res, p;
|
---|
70 |
|
---|
71 | if (argc < 3) {
|
---|
72 | printf("usage: %s: result numbers...\n"
|
---|
73 | "Try to find result from numbers with the 4 basic operations.\n", argv[0]);
|
---|
74 | exit(1);
|
---|
75 | }
|
---|
76 |
|
---|
77 | p = 1;
|
---|
78 | result = atoi(argv[p]);
|
---|
79 | printf("result=%d\n", result);
|
---|
80 | nb_num = 0;
|
---|
81 | for(i=p+1;i<argc;i++) {
|
---|
82 | tab[nb_num++] = atoi(argv[i]);
|
---|
83 | }
|
---|
84 |
|
---|
85 | stack_ptr = -1;
|
---|
86 | res = find(0, 0, 0, 0, ' ');
|
---|
87 | if (res) {
|
---|
88 | for(i=0;i<=stack_ptr;i++) {
|
---|
89 | printf("%d %c %d = %d\n",
|
---|
90 | stack_res[3*i], stack_op[i],
|
---|
91 | stack_res[3*i+1], stack_res[3*i+2]);
|
---|
92 | }
|
---|
93 | return 0;
|
---|
94 | } else {
|
---|
95 | printf("Impossible\n");
|
---|
96 | return 1;
|
---|
97 | }
|
---|
98 | }
|
---|