我只用过gdb,不过我是用ddd（提供的图形界面还可以），它封装的gdb.
要疯了
怎么也无法枚举每种状态
已解决加乘的左右交换问题
但对减除的左面是树，右面是叶子的
表达式树，怎么也无法枚举出来
枚举打印的都缺少叶子，哎
重新写的求值函数#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define max 16
#define nmax 64 * 1024 * 1024
int calc;
int operator = { -1, -3, -2, -4 }; // + * - /
int mask; //代表数字是否被使用
int nmask; //表示的数字
int n;
int leaf; //剩余数字
int position;
int counter;
void
init (void)
{
int i;
for (i = 1; i <= max; i++)
mask = 0;
position = 0;
counter = 0;
leaf = n;
memset(nmask, 0, nmax * sizeof(int));
}
void search(void)
{
int i;
for (i = 1; i < nmax; i ++)
if (nmask == 0)
{
printf("\nmin: %d\n", i);
break;
}
}
//返回0代表表达式合法，－1代表除法不能除尽，－2代表除以0，－3代表结果为负
int print(void)
{
int i;
int opTop = 0, numTop = 0;
long long temp;
long long numBuffer;
int itemp;
for (i = 2 * n - 2; i >= 0; i --)
{
if (calc < 0)
{
switch (calc)
{
case -1:
temp = numBuffer + numBuffer;
break;
case -2:
temp = numBuffer - numBuffer;
break;
case -3:
temp = numBuffer * numBuffer;
break;
case -4:
if (numBuffer == 0)
return (-2);
if (numBuffer % numBuffer > 0)
return (-1);
temp = numBuffer / numBuffer;
break;
}
numTop -= 1;
numBuffer = temp;
}
else
numBuffer = calc;
}
temp = numBuffer;
if (temp < 0) return (-3);
if (temp < nmax)
{
itemp = temp;
if (nmask == 0)
{
counter++;
printf("%d: %d ", counter, itemp);
for (i = 0; i <= 2 * n - 2; 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");
nmask = 1;
}
}
return (0);
}
int
printOnly (void)
{
int i;
for (i = 0; i <= 2 * n - 2; 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++;
}
void
printBlank (void)
{
counter++;
}
int
top (int MaxNode)
{
int i;
if (MaxNode >= 1)
for (i = 0; i < 4; i++)
{
calc = operator;
if (i < 2)
subNode (MaxNode - 1, 1);
else
subNode (MaxNode - 1, 0);
position--;
}
}
void
addmul (void)
{
int i, j;
for (i = 1; i <= n - 1; i++)
if (mask == 0)
{
mask = 1;
leaf--;
calc = i;
for (j = i + 1; j <= n; j++)
if (mask == 0)
{
calc = j;
mask = 1;
leaf--;
if (leaf == 0)
{
// check();
print ();
}
mask = 0;
leaf++;
position--;
}
leaf++;
position--;
mask = 0;
}
}
void
subdiv (void)
{
int i, j;
for (i = 1; i <= n; i++)
if (mask == 0)
{
mask = 1;
leaf--;
calc = i;
for (j = 1; j <= n; j++)
if (mask == 0)
{
calc = j;
mask = 1;
leaf--;
if (leaf == 0)
{
// check();
print ();
}
mask = 0;
leaf++;
position--;
}
leaf++;
position--;
mask = 0;
}
}
void
leftFill (int MaxNode)
{
int i;
for (i = 1; i <= n; i++)
if (mask == 0)
{
calc = i;
leaf--;
mask = 1;
top (MaxNode);
position--;
leaf++;
mask = 0;
}
}
void
rightFill (int MaxNode)
{
int i;
for (i = 1; i <= n; i++)
if (mask == 0)
{
mask = 1;
calc = i;
leaf--;
top (MaxNode);
leaf++;
mask = 0;
}
}
int
subNode (int MaxNode, int exchange)
{
int i, j;
if (MaxNode == 0)
{
if (exchange == 1)
addmul ();
else
subdiv ();
}
if (MaxNode >= 1)
{
//1\fill left
leftFill (MaxNode);
//2\fill right
if (exchange == 0)
rightFill (MaxNode);
}
//3\top(left) top(right)
if (MaxNode >= 2)
for (i = 1; i < MaxNode; i++)
{
top (i);
top (MaxNode - i);
}
}
int
main (void)
{
struct timeval start, end;
double timeuse;
printf ("Input n value:");
scanf ("%d", &n);
printf ("\n\n");
gettimeofday (&start, NULL);
init ();
top (n - 1);
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;
}
n <=5和mathe的答案一致
从6开始就不对了
在查找原因
[ 本帖最后由 无心人 于 2008-8-4 21:48 编辑 ]
n = 7的算下
一会儿过来汇报
＝＝＝＝＝＝＝＝＝＝＝＝＝
Total: 2710
min: 1102
Used Time:105.265166
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
晕，似乎从6开始就和mathe的结果不同了啊
哎
[ 本帖最后由 无心人 于 2008-8-4 18:46 编辑 ]
1102=2*(5+7*6*(1+4*3))
有bug，从3开始就不对了
还没找到问题
我把7的都输出到文件，看是漏算还是计算函数有问题
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
已修正n到5
但从6开始还不对，有两个无法算出
279 281
[ 本帖最后由 无心人 于 2008-8-4 21:56 编辑 ]
279=(5+4)*(1+6*(3+2))
晕死
7的输出3G多
文本编辑器打不开阿
推荐个能处理这么大文件的文本编辑器
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
看n=3的结果
里面有7的结果 + 1 * 2 3
但不输出7
似乎是求值的问题
[ 本帖最后由 无心人 于 2008-8-4 19:28 编辑 ]
Input n value:3
1: 6 + 1 + 2 3
2: 7 + 1 * 2 3
3: 0 + 1 - 2 3
4: 2 + 1 - 3 2
5: 5 + 2 * 1 3
6: 4 + 2 - 3 1
7: 1 * 1 - 3 2
8: 8 * 2 + 1 3
9: 9 * 3 + 1 2
10: 3 * 3 - 2 1
Total: 10
min: 10
Used Time:1.113455
[ 本帖最后由 无心人 于 2008-8-4 21:47 编辑 ]
mathe
6的还一个281没找到解
你的解是？