论坛 › 编程擂台 › 最小无法表达的正整数

无心人 发表于 2008-8-7 09:00:17

任何一个瞬间的递归函数有两个状态
第一个状态是当前左子节点的所有情况
局部保存，第二个状态是所有右子节点的状态
压栈保存
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
呵呵
实际代码
说简单也不简单
说复杂也不复杂
等我想好了
等我写好了
等我调试了
发上来

无心人 发表于 2008-8-8 16:29:30

呵呵
光说原理，到现在程序还没写呢
学校有点忙
已经想明白如何做了
等写完检验吧
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
PS:
更直接的方法也得到了
我想到
由表达式树中序遍历的序列
其特点是，
1、操作符和数字共2n-1个，操作符n-1个，数字n个
2、操作符可以任意多个并在一起，
3、如果一个从开始起的部分序列，已经有操作符k个，那么接下来，从开始算的操作数字必须也有k个，才能出现新的操作符
4、2n-1最后两个位置不得是操作符

所以如果按照上面规则，可以递归产生出合法的序列，而不用树
从而简化程序

无心人 发表于 2008-8-10 21:57:53

补充上面的叙述
有多少连续操作符
后面就要跟多少操作数

而且最后结束的两个必须是数字

满足这两个条件的序列将为合法且为某个表达式树中序遍历序列
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
PS
使用栈的递归方式还是没调试好
希望两天内能调试好
否则，将直接实现本帖子的算法
（还是希望能现实现栈算法，某些题目可能有用处）

无心人 发表于 2008-8-10 22:01:35

发上当前使用栈递归的代码
但提前声明，存在错误
未调试好#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define max 16
#define nmax 64 * 1024 * 1024

int Expr;                //表达式树中序遍历序列
int operator = { -1, -3, -2, -4 };        // + * - /
int mask;                //代表数字是否被使用
int nmask;                //表示的数字
int n;                                //输入的n值
int leaf;                        //剩余数字
int position;                        //在表达式序列中的当前位置
int counter;                        //产生的表达式计数
int loop;                        //递归栈
int loopTop;                        //递归栈顶

void
init (void)
{
int i;
for (i = 1; i <= max; i++)
    mask = 0;
position = 0;
counter = 0;
leaf = n;
loop = 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 == 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;
int itemp;

for (i = 2 * n - 2; i >= 0; i--)
    {
      if (Expr < 0)
        {
          switch (Expr)
          {
          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 = Expr;
    }

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 (Expr < 0)
                {
                  switch (Expr)
                  {
                  case -1:
                      printf ("+ ");
                      break;
                  case -2:
                      printf ("- ");
                      break;
                  case -3:
                      printf ("* ");
                      break;
                  case -4:
                      printf ("/ ");
                      break;
                  }
                }
              else
                printf ("%d ", Expr);
          }
          printf ("\n");

          nmask = 1;
        }
    }

return (0);
}

int
print (void)
{
int i;
for (i = 0; i <= 2 * n - 2; i++)
    {
      if (Expr < 0)
        {
          switch (Expr)
          {
          case -1:
              printf ("+ ");
              break;
          case -2:
              printf ("- ");
              break;
          case -3:
              printf ("* ");
              break;
          case -4:
              printf ("/ ");
              break;
          }
        }
      else
        printf ("%d ", Expr);
    }
printf ("\n");
counter++;
}

void
printBlank (void)
{
counter++;
}

void
loop1 (void)
{
int i, j, k;
loopTop--;
for (k = 0; k <= 1; k++)
    {
      Expr = operator;
      for (i = 1; i < n; i++)
        if (mask == 0)
          {
          mask = 1;
          Expr = i;
          for (j = i + 1; j <= n; j++)
              if (mask == 0)
                {
                  mask = 1;
                  Expr = j;
                  root ();
                  mask = 0;
                  position--;
                }
          mask = 0;
          position--;
          }
      position--;
    }

for (k = 2; k <= 3; k++)
    {
      Expr = operator;
      for (i = 1; i <= n; i++)
        if (mask == 0)
          {
          mask = 1;
          Expr = i;
          for (j = 1; j <= n; j++)
              if (mask == 0)
                {
                  mask = 1;
                  Expr = j;
                  root ();
                  mask = 0;
                  position--;
                }
          mask = 0;
          position--;
          }
      position--;
    }
}

void
loopa (int level)
{
int i, j, k;
level--;
for (k = 0; k <= 1; k++)
    {
      Expr = operator;
      for (i = 1; i <= level / 2; i++)
        {
          loop = i;
          loop = level - i;
          root ();
        }
      position--;
    }

for (k = 2; k <= 3; k++)
    {
      Expr = operator;
      for (i = 1; i <= level - 1; i++)
        {
          loop = i;
          loop = level - i;
          root ();
        }
      position--;
    }

}

void
loopl (int level)
{
int i, k;
for (k = 0; k <= 3; k++)
    {
      Expr = operator;
      loop = level - 1;
      for (i = 1; i <= n; i++)
        if (mask == 0)
          {
          mask = 1;
          Expr = i;
          root ();
          mask = 0;
          }
        position --;
    }
}

void
loopr (int level)
{
int i, k;
for (k = 2; k <= 3; k++)
    {
      Expr = operator;
      loop = level - 1;
      for (i = 1; i <= n; i++)
        if (mask == 0)
          {
          mask = 1;
          Expr = i;
          root ();
          mask = 0;
          position--;
          }
                position --;
    }
}

//
int
root (void)
{
int i, j, k;
int level;
if (loopTop == 0)
    {
      print ();
      return 0;
    }
level = loop;
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;
}

无心人 发表于 2008-8-16 20:08:38

栈似乎可以工作了
但3的对
4的不对
存在重复的数字#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define max 16
#define nmax 64 * 1024 * 1024

int Expr;                //表达式树中序遍历序列
int operator = { -1, -3, -2, -4 };        // + * - /
int mask;                //代表数字是否被使用
int nmask;                //表示的数字
int n;                                //输入的n值
int leaf;                        //剩余数字
int position;                        //在表达式序列中的当前位置
int counter;                        //产生的表达式计数
int loop;                        //递归栈
int loopTop;                        //递归栈顶

void
init (void)
{
int i;
for (i = 1; i <= max; i++)
    mask = 0;
position = 0;
counter = 0;
leaf = n;
loop = 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 == 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;
int itemp;

for (i = 2 * n - 2; i >= 0; i--)
    {
      if (Expr < 0)
        {
          switch (Expr)
          {
          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 = Expr;
    }

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 (Expr < 0)
                {
                  switch (Expr)
                  {
                  case -1:
                      printf ("+ ");
                      break;
                  case -2:
                      printf ("- ");
                      break;
                  case -3:
                      printf ("* ");
                      break;
                  case -4:
                      printf ("/ ");
                      break;
                  }
                }
              else
                printf ("%d ", Expr);
          }
          printf ("\n");

          nmask = 1;
        }
    }

return (0);
}

int
print (void)
{
int i;
for (i = 0; i <= 2 * n - 2; i++)
    {
      if (Expr < 0)
        {
          switch (Expr)
          {
          case -1:
              printf ("+ ");
              break;
          case -2:
              printf ("- ");
              break;
          case -3:
              printf ("* ");
              break;
          case -4:
              printf ("/ ");
              break;
          }
        }
      else
        printf ("%d ", Expr);
    }
printf ("\n");
counter++;
}

void
printBlank (void)
{
counter++;
}

void
loop1 (void)
{
int i, j, k, t;
loopTop--;
for (k = 0; k <= 1; k++)
    {
      Expr = operator;
      for (i = 1; i < n; i++)
          if (mask == 0)
          {
              mask = 1;
              Expr = i;
              for (j = i + 1; j <= n; j++)
                if (mask == 0)
                  {
                  mask = 1;
                  Expr = j;
                        t = loopTop;
                  root ();
                        loopTop = t;
                  mask = 0;
                  position--;
                  }
              mask = 0;
              position--;
          }
      position--;
    }

for (k = 2; k <= 3; k++)
    {
      Expr = operator;
      for (i = 1; i <= n; i++)
          if (mask == 0)
          {
              mask = 1;
              Expr = i;
              for (j = 1; j <= n; j++)
                if (mask == 0)
                  {
                  mask = 1;
                  Expr = j;
                        t = loopTop;
                  root ();
                        loopTop = t;
                  mask = 0;
                  position--;
                  }
              mask = 0;
              position--;
          }
      position--;
    }
}

void
loopa (int level)
{
int i, j, k, t;
level--;
for (k = 0; k <= 1; k++)
    {
      Expr = operator;
      for (i = 1; i <= level / 2; i++)
          {
          loop = i;
      t = loopTop;
          loop = level - i;
          root ();
                loopTop = t;
          }
      position--;
    }

for (k = 2; k <= 3; k++)
    {
      Expr = operator;
      for (i = 1; i <= level - 1; i++)
          {
          loop = i;
                t = loopTop;
          loop = level - i;
          root ();
                loopTop = t;
          }
      position--;
    }

}

void
loopl (int level)
{
int i, k, t;
for (k = 0; k <= 3; k++)
    {
      Expr = operator;
      loop = level - 1;
      for (i = 1; i <= n; i++)
          if (mask == 0)
          {
              mask = 1;
              Expr = i;
          t = loopTop; //new
              root ();
                  loopTop = t; //new
              mask = 0;
          }
          position --;
    }
}

void
loopr (int level)
{
int i, k, t;
for (k = 2; k <= 3; k++)
    {
      Expr = operator;
      loop = level - 1;
      for (i = 1; i <= n; i++)
          if (mask == 0)
          {
              mask = 1;
              Expr = i;
          t = loopTop; //new
              root ();
                  loopTop = t; //new
              mask = 0;
              position--;
          }
                position --;
    }
}

//
int
root (void)
{
int i, j, k;
int level;
if (loopTop == 0)
    {
      print ();
      return 0;
    }
level = loop;
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;
}


[ 本帖最后由 无心人 于 2008-8-16 20:38 编辑 ]

无心人 发表于 2008-8-16 21:58:28

mathe：
有现成程序快速的对具体的数字m求连续n个数字的四则表示么？？
我想，我不完整程序版本33＃的速度似乎快很多
可修改之使输出连续32个无法表示的
我们可从最小的一个个排除

修改下面的函数
#define SearchMax 32

void
search (void)
{
printf ("\nmin:");
int i, j = 0;
for (i = 1; i < nmax; i++)
    if (nmask == 0)
      {
        j++;
        printf ("%d", i);
        if (j == SearchMax)
          break;
      }
printf ("\n");
}刚对11的测试，输出到48733项
48730: 20994 + 1 + 2 + 3 + 8 + 10 * 5 * 9 + 4 * 6 * 7 11
48731: 20634 + 1 + 2 + 3 + 8 + 10 * 5 * 9 - * 6 * 7 11 4
48732: 13614 + 1 + 2 + 3 + 8 + 10 * 5 * 9 - * 4 * 7 11 6
48733: 16686 + 1 + 2 + 3 + 8 + 10 * 6 + 5 * 4 * 7 * 9 11


real        4m57.256s
user        3m35.929s
sys        0m2.212s
估计11的要输出500万项以上吧
最小无法表示的当在200万－400万之间
这么作唯一的担心是输出32个连续最小无法表示的是否足够
或者干脆是把无法表示的输出个10000个到文件？

[ 本帖最后由 无心人 于 2008-8-16 22:18 编辑 ]

mathe 发表于 2008-8-18 12:28:46

也许可以快速构造部分表达式。
不过这种方法最大的问题在于后面构造失败以后，如何去证明后面那个数不存在合法的表达式（而且如果实际上合法表达式存在，那么更加麻烦）

无心人 发表于 2008-8-18 12:53:15

我有点不明白你的意思
你是否说这个意思

假设对于小于等于
$f(n)=3 / 2 n!$（1－n构造的四则运算结果所有可能数字中最大的）的正整数
用不完全构造的方法没构造出表达式的
数字组成集合
$Fa$
对集合中的数字
有没有确定方法证明存在构造表达式？

[ 本帖最后由 无心人 于 2008-8-18 12:56 编辑 ]

无心人 发表于 2008-8-18 12:59:20

我想这个问题可以提出
另外一个问题
对于确定的正整数$N$
是否存在$1..n$的$n$个数字
构造的四则运算式
使得结果是$N$

我觉得这个问题比本帖子讨论的问题简单的多

无心人 发表于 2008-8-18 13:04:24

以n = 11为例
可证明最大可构造表达式值是59875200
最小不可构造数字大于n=10的不可构造数字
假设不完全构造后
得到无法构造的数字序列
其最小值应该大于n=10的确定的最小值a
即使小于
也应该能证明小于11a且大于a的数字应该绝大部分能构造

呵呵，所以我想问你是否存在程序能构造具体数字的表达式

查看完整版本: 最小无法表达的正整数