/* Задача 2.3 АРИТМЕТИКА Дадени са целите положителни числа N и a1, a2, .., am. С помощта на операциите + (събиране), - (изваждане), * (умножение) и / (деление) и числата a1, a2, .., am образуваме аритметични изрази със стойност N и такива, че всеки техен подизраз е цяло положително число. Всяко от числата a1, a2, .., am е различно от другите и може да участва в такъв израз не повече от веднъж. Колко къс израз от този вид можем да образуваме? Напишете програма EXPR.EXE, която по дадени N, a1, a2, .., am (всичките по-малки от 3000, m <= 20) намира един най-къс израз с описаните свойства. Числата N и a1, a2, .., am се въвеждат от два последователни реда на стандартния вход, а резултатът се отпечатва на един ред на стандартния изход, като за всяка аритметична операция в израза са поставени скоби. РЕШЕНИЕ от Иван Анев Решението на поставената задача изисква познаване на обратния полски запис, или наречен по друг начин постфиксен запис на аритметичен израз. Решението се основава на генериране на всички изрази с една операция, с две, с три и т.н., докато се намери решение. За всеки генериран израз се изчислява неговата стойност. След като се намери търсения израз, трябва да се преобразува постфиксния запис в нормалния инфиксен запис. Как ще генерираме постфиксния израз. За всяка позиция от него имаме два варианта. Да сложим един от четирите оператора (+, -, *, /) или една от неизползваните променливи. Ограниченията, които трябва да спазваме са броят на сложените операторите да е поне с едно по-малък от броят на сложените променливи, и броят на сложените променливи и оператори да не надвишава зададения брой, за конкретно генерирания израз. Изчисляването на израз записан в обратен полски запис и преобразуването от постфиксен в инфиксен запис, са теми които са свързани със съответната теория и нямат място в описанието на решението. */ /* NAME: Ivan Anev PROG: expr LANG: C */ #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXM 8 #define MAXLEN 16 #define MAXANS 256 #define OP_S -1 #define OP_M -2 #define OP_P -3 #define OP_D -4 int n, m; int a[MAXM]; int used[MAXM]; int expr[MAXLEN]; char ans[MAXANS]; void readf(void); void solve(void); void writef(void); int main(void) { readf(); solve(); writef(); return 0; } void readf(void) { int b; scanf("%d", &n); while (scanf("%d", &b) != -1) a[m++] = b; } void solve(void) { int l; int gen(int nump, int no, int l, int ml); void posttoinfix(int expr[], int len, char *s); for (l = 2; l <= m && gen(0, 0, 0, l) == 0; ++l) ; posttoinfix(expr, 2 * l - 1, ans); } void writef(void) { printf("%s\n", ans); } int gen(int nump, int no, int l, int ml) { int i; int compute(int expr[], int len); if (l == 2 * ml - 1) return (compute(expr, l) == n); else { if (no >= 2) { expr[l] = OP_S; if (gen(nump, no - 1, l + 1, ml)) return 1; expr[l] = OP_M; if (gen(nump, no - 1, l + 1, ml)) return 1; expr[l] = OP_D; if (gen(nump, no - 1, l + 1, ml)) return 1; expr[l] = OP_P; if (gen(nump, no - 1, l + 1, ml)) return 1; } if (nump < ml) { for (i = 0; i < m; ++i) if (used[i] == 0) { expr[l] = a[i]; used[i] = 1; if (gen(nump + 1, no + 1, l + 1, ml)) return 1; used[i] = 0; } } } return 0; } int compute(int expr[], int len) { int stack[MAXM], sp; int op1, op2, i; for (i = sp = 0; i < len; ++i) if (expr[i] > 0) stack[sp++] = expr[i]; else { op2 = stack[--sp]; op1 = stack[--sp]; switch (expr[i]) { case OP_S: stack[sp++] = op1 + op2; break; case OP_M: if (op1 - op2 <= 0) return -1; stack[sp++] = op1 - op2; break; case OP_P: stack[sp++] = op1 * op2; break; case OP_D: if (op1 % op2) return -1; stack[sp++] = op1 / op2; break; } } return stack[0]; } void posttoinfix(int expr[], int len, char *s) { int i, sp; char *stack[MAXM]; char *op1, *op2; for (i = 0; i < MAXM; ++i) stack[i] = (char*)malloc(sizeof(char) * MAXANS); for (i = sp = 0; i < len; ++i) if (expr[i] > 0) sprintf(stack[sp++], "%d", expr[i]); else { op2 = stack[--sp]; op1 = stack[--sp]; switch (expr[i]) { case OP_S: sprintf(s, "(%s+%s)", op1, op2); break; case OP_M: sprintf(s, "(%s-%s)", op1, op2); break; case OP_P: sprintf(s, "(%s*%s)", op1, op2); break; case OP_D: sprintf(s, "(%s/%s)", op1, op2); break; } strcpy(stack[sp++], s); } strcpy(s, stack[0]); for (i = 0; i < m; ++i) free(stack[i]); }