#include #include #include #define max 16 #define nmax 64 * 1024 * 1024 int Expr[2 * max - 1]; //表达式树中序遍历序列 int operator[4] = { -1, -3, -2, -4 }; // + * - / int mask[max + 1]; //代表数字是否被使用 int nmask[nmax]; //表示的数字 int n; //输入的n值 int leaf; //剩余数字 int position; //在表达式序列中的当前位置 int counter; //产生的表达式计数 int loop[max]; //递归栈 int loopTop; //递归栈顶 void init (void) { int i; for (i = 1; i <= max; i++) mask[i] = 0; position = 0; counter = 0; leaf = n; loop[loopTop++] = n - 1; //memset(nmask, 0, nmax * sizeof(int)); } void search (void) { printf ("\nmin:"); int i, j = 0; for (i = 1; i < nmax; i++) if (nmask[i] == 0) { j++; printf ("%d ", i); if (j == 10) break; } printf ("\n"); } //返回0代表表达式合法,-1代表除法不能除尽,-2代表除以0,-3代表结果为负 int printValue (void) { int i; int opTop = 0, numTop = 0; long long temp; long long numBuffer[max]; int itemp; for (i = 2 * n - 2; i >= 0; i--) { if (Expr[i] < 0) { switch (Expr[i]) { case -1: temp = numBuffer[numTop - 1] + numBuffer[numTop - 2]; break; case -2: temp = numBuffer[numTop - 1] - numBuffer[numTop - 2]; break; case -3: temp = numBuffer[numTop - 1] * numBuffer[numTop - 2]; break; case -4: if (numBuffer[numTop - 2] == 0) return (-2); if (numBuffer[numTop - 1] % numBuffer[numTop - 2] > 0) return (-1); temp = numBuffer[numTop - 1] / numBuffer[numTop - 2]; break; } numTop -= 1; numBuffer[numTop - 1] = temp; } else numBuffer[numTop++] = Expr[i]; } temp = numBuffer[0]; if (temp < 0) return (-3); if (temp < nmax) { itemp = temp; if (nmask[itemp] == 0) { counter++; printf ("%d: %d ", counter, itemp); for (i = 0; i <= 2 * n - 2; i++) { if (Expr[i] < 0) { switch (Expr[i]) { case -1: printf ("+ "); break; case -2: printf ("- "); break; case -3: printf ("* "); break; case -4: printf ("/ "); break; } } else printf ("%d ", Expr[i]); } printf ("\n"); nmask[itemp] = 1; } } return (0); } int print (void) { int i; for (i = 0; i <= 2 * n - 2; i++) { if (Expr[i] < 0) { switch (Expr[i]) { case -1: printf ("+ "); break; case -2: printf ("- "); break; case -3: printf ("* "); break; case -4: printf ("/ "); break; } } else printf ("%d ", Expr[i]); } printf ("\n"); counter++; } void printBlank (void) { counter++; } void loop1 (void) { int i, j, k, t; loopTop--; for (k = 0; k <= 1; k++) { Expr[position++] = operator[k]; for (i = 1; i < n; i++) if (mask[i] == 0) { mask[i] = 1; Expr[position++] = i; for (j = i + 1; j <= n; j++) if (mask[j] == 0) { mask[j] = 1; Expr[position++] = j; t = loopTop; root (); loopTop = t; mask[j] = 0; position--; } mask[i] = 0; position--; } position--; } for (k = 2; k <= 3; k++) { Expr[position++] = operator[k]; for (i = 1; i <= n; i++) if (mask[i] == 0) { mask[i] = 1; Expr[position++] = i; for (j = 1; j <= n; j++) if (mask[j] == 0) { mask[j] = 1; Expr[position++] = j; t = loopTop; root (); loopTop = t; mask[j] = 0; position--; } mask[i] = 0; position--; } position--; } } void loopa (int level) { int i, j, k, t; level--; for (k = 0; k <= 1; k++) { Expr[position++] = operator[k]; for (i = 1; i <= level / 2; i++) { loop[loopTop - 1] = i; t = loopTop; loop[loopTop++] = level - i; root (); loopTop = t; } position--; } for (k = 2; k <= 3; k++) { Expr[position++] = operator[k]; for (i = 1; i <= level - 1; i++) { loop[loopTop - 1] = i; t = loopTop; loop[loopTop++] = level - i; root (); loopTop = t; } position--; } } void loopl (int level) { int i, k, t; for (k = 0; k <= 3; k++) { Expr[position++] = operator[k]; loop[loopTop - 1] = level - 1; for (i = 1; i <= n; i++) if (mask[i] == 0) { mask[i] = 1; Expr[position + 2 * level - 1] = i; t = loopTop; //new root (); loopTop = t; //new mask[i] = 0; } position --; } } void loopr (int level) { int i, k, t; for (k = 2; k <= 3; k++) { Expr[position++] = operator[k]; loop[loopTop - 1] = level - 1; for (i = 1; i <= n; i++) if (mask[i] == 0) { mask[i] = 1; Expr[position++] = i; t = loopTop; //new root (); loopTop = t; //new mask[i] = 0; position--; } position --; } } // int root (void) { int i, j, k; int level; if (loopTop == 0) { print (); return 0; } level = loop[loopTop - 1]; if (level == 1) loop1 (); else { loopl (level); loopr (level); if (level > 2) loopa (level); } } int main (void) { struct timeval start, end; double timeuse; printf ("Input n value:"); scanf ("%d", &n); printf ("\n\n"); gettimeofday (&start, NULL); init (); root (); printf ("\nTotal: %d\n", counter); search (); gettimeofday (&end, NULL); timeuse = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec; timeuse /= 1000000; printf ("\n\nUsed Time:%8.6f\n\n", timeuse); return 0; }