[279] | 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 | }
|
---|