出去乘凉
似乎找到了方法
用线性序列表示栈
首先压入运算符号，再压入数字
得到全部组合，则会得到所有的可能解
现在问题是，似乎要限定解的上限，否则太大
我想，2*n^2是否足够大？
:L
还要实现一个基于栈的表达式计算函数
:'(
昨天想了一会儿没脸把如此显然的结论贴上来，今天来丢一下脸
还可以剪枝，设a是长度n的数列第一个无法表示的数值
a=2
a=4
a=10
...
则对于a必有a>n(n+1)/2，可以减少检测范围
证明：
对于n的情况，由数归证得的a>=n
通过构造n+(p) 可以表示n+1...n+a-1
通过构造n+n-1+(p)可以表示n+n-1+1...n+n-1+a-1
...
得n+1...n(n+1)/2都可以表示
通过构造n-(p)可以表示1到n-1的数
而n可以由n*(1)表示(1)由1...n-1表示
得证
后来在车上想到下界还能更好，没来的及好好想，楼下继续
mathe能把1...10的结果爆料一下吗？寻找一下更好的思路
[ 本帖最后由 kenmark 于 2008-8-2 14:04 编辑 ]
**** Hidden Message *****
mathe
能否证明
a <= n *
====================
PS:
还可以构造
n * a n * (n-1) * a等
用构造法应该能得到非显然的下界
但无法得到准确下界
只能暴力搜索么？
对于
+ * 2 3 - 4 1
表示(2 * 3) + (4 - 1)
类型的表达式树
如何计算比较好？
#include <stdio.h>
#include <stdlib.h>
#define max 16
int calc;
int maxlevel;
int operator = {-1, -2, -3, -4}; // + - * /
int mask;
int n;
int le; //剩余数字
int position;
int counter;
void init(void)
{
int i;
for (i = 1; i <= max; i ++)
mask = 0;
position = 0;
counter = 0;
}
//返回0代表表达式合法，－1代表除法不能除尽，－2代表除以0，－3代表结果为负
int check(void)
{
int i;
int op;
int leftNum, rightNum;
long long Result;
leftNum = 0;
rightNum = 0;
//检测得到的数字序列是否合法表达式，如果是，则计算出结果
for (i = position - 1; i >= 0; i --)
{
if (calc < 0)
switch (calc)
{
case -1:// +
break;
case -2:// -
break;
case -3:// *
break;
case -4:// /
break;
}
}
}
void print(void)
{
int i;
for (i = 0; i <= position - 1; i ++)
{
if (calc < 0)
{
switch (calc)
{
case -1: printf("+ "); break;
case -2: printf("- "); break;
case -3: printf("* "); break;
case -4: printf("/ "); break;
}
}
else
printf("%d ", calc);
}
printf("\n");
counter ++;
}
int top(int level)
{
int i, j;
if (level < n - 1)
for (i = 0; i < 4; i ++)
{
calc = operator;
left(level);
position --;
}
}
//左的长度要不大于右
int left(int level)
{
int i;
for (i = 1; i <= n; i ++)
if (mask == 0)
{
calc = i;
mask = 1;
le --;
right(level);
le ++;
mask = 0;
position --;
}
top(level + 1);
}
int right(int level)
{
int i;
if (le == 1)
{
for (i = 1; i <= n; i ++)
if (mask == 0)
{
calc = i;
mask = 1;
// check();
print();
position --;
mask = 0;
}
}
else
top(level + 1);
}
int main(void)
{
printf("Input n value:");
scanf("%d", &n);
printf("\n\n");
init();
le = n;
top(0);
printf("Total: %d\n", counter);
return 0;
}
n = 2得到8个式子
n = 396
n = 4 1536
n=4应该是错误的， 呵呵
/ 4 * 1 + 2 3
/ 4 * 1 + 3 2
/ 4 * 1 - 2 3
/ 4 * 1 - 3 2
/ 4 * 1 * 2 3
/ 4 * 1 * 3 2
就这种式子
少了
* + 2 3 - 4 1
类型的
对每个n
不考虑唯一
不考虑结果的合理性
所有可能的式子是
$2^(n-2)*4^(n-1)*n!$
所以随n增大，搜索时间迅速变大
n=10的可能是$2^8*4^9*10! = 243,524,645,683,200$
这个可以通过 http://bbs.emath.ac.cn/thread-461-1-1.html 中的统计数据，只计算不等价的表达式，还有$2,894,532,443,154$个，比上面表达式好一些:)