最小无法表达的正整数

mathe · 发表于 2008-8-4 11:28:48

我只用过gdb,不过我是用ddd（提供的图形界面还可以），它封装的gdb.

无心人 · 发表于 2008-8-4 16:01:14

要疯了怎么也无法枚举每种状态已解决加乘的左右交换问题但对减除的左面是树，右面是叶子的表达式树，怎么也无法枚举出来枚举打印的都缺少叶子，哎

无心人 · 发表于 2008-8-4 16:02:40

重新写的求值函数

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define max 16
#define nmax 64 * 1024 * 1024
int calc[2 * max - 1];
int operator[4] = { -1, -3, -2, -4 }; // + * - /
int mask[max + 1]; //代表数字是否被使用
int nmask[nmax]; //表示的数字
int n;
int leaf; //剩余数字
int position;
int counter;
void
init (void)
{
int i;
for (i = 1; i <= max; i++)
mask[i] = 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[i] == 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[max];
int itemp;
for (i = 2 * n - 2; i >= 0; i --)
{
if (calc[i] < 0)
{
switch (calc[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 ++] = calc[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 (calc[i] < 0)
{
switch (calc[i])
{
case -1:
printf ("+ ");
break;
case -2:
printf ("- ");
break;
case -3:
printf ("* ");
break;
case -4:
printf ("/ ");
break;
}
}
else
printf ("%d ", calc[i]);
}
printf ("\n");
nmask[itemp] = 1;
}
}
return (0);
}
int
printOnly (void)
{
int i;
for (i = 0; i <= 2 * n - 2; i++)
{
if (calc[i] < 0)
{
switch (calc[i])
{
case -1:
printf ("+ ");
break;
case -2:
printf ("- ");
break;
case -3:
printf ("* ");
break;
case -4:
printf ("/ ");
break;
}
}
else
printf ("%d ", calc[i]);
}
printf ("\n");
counter++;
}
void
printBlank (void)
{
counter++;
}
int
top (int MaxNode)
{
int i;
if (MaxNode >= 1)
for (i = 0; i < 4; i++)
{
calc[position++] = operator[i];
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[i] == 0)
{
mask[i] = 1;
leaf--;
calc[position++] = i;
for (j = i + 1; j <= n; j++)
if (mask[j] == 0)
{
calc[position++] = j;
mask[j] = 1;
leaf--;
if (leaf == 0)
{
// check();
print ();
}
mask[j] = 0;
leaf++;
position--;
}
leaf++;
position--;
mask[i] = 0;
}
}
void
subdiv (void)
{
int i, j;
for (i = 1; i <= n; i++)
if (mask[i] == 0)
{
mask[i] = 1;
leaf--;
calc[position++] = i;
for (j = 1; j <= n; j++)
if (mask[j] == 0)
{
calc[position++] = j;
mask[j] = 1;
leaf--;
if (leaf == 0)
{
// check();
print ();
}
mask[j] = 0;
leaf++;
position--;
}
leaf++;
position--;
mask[i] = 0;
}
}
void
leftFill (int MaxNode)
{
int i;
for (i = 1; i <= n; i++)
if (mask[i] == 0)
{
calc[position++] = i;
leaf--;
mask[i] = 1;
top (MaxNode);
position--;
leaf++;
mask[i] = 0;
}
}
void
rightFill (int MaxNode)
{
int i;
for (i = 1; i <= n; i++)
if (mask[i] == 0)
{
mask[i] = 1;
calc[position + 2 * MaxNode + 1] = i;
leaf--;
top (MaxNode);
leaf++;
mask[i] = 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 编辑 ]

无心人 · 发表于 2008-8-4 18:42:42

n = 7的算下一会儿过来汇报＝＝＝＝＝＝＝＝＝＝＝＝＝ Total: 2710 min: 1102 Used Time:105.265166 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝晕，似乎从6开始就和mathe的结果不同了啊哎 [ 本帖最后由无心人于 2008-8-4 18:46 编辑 ]

mathe · 发表于 2008-8-4 18:52:31

1102=2*(5+7*6*(1+4*3))

无心人 · 发表于 2008-8-4 18:55:50

有bug，从3开始就不对了还没找到问题我把7的都输出到文件，看是漏算还是计算函数有问题＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝已修正n到5 但从6开始还不对，有两个无法算出 279 281 [ 本帖最后由无心人于 2008-8-4 21:56 编辑 ]

mathe · 发表于 2008-8-4 18:56:51

279=(5+4)*(1+6*(3+2))

无心人 · 发表于 2008-8-4 19:24:39

晕死 7的输出3G多文本编辑器打不开阿推荐个能处理这么大文件的文本编辑器＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝看n=3的结果里面有7的结果 + 1 * 2 3 但不输出7 似乎是求值的问题 [ 本帖最后由无心人于 2008-8-4 19:28 编辑 ]

无心人 · 发表于 2008-8-4 19:32:29

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 编辑 ]

无心人 · 发表于 2008-8-4 21:37:55

mathe 6的还一个281没找到解你的解是？

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 最小无法表达的正整数