数学研发论坛

 找回密码
 欢迎注册
楼主: mathe

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

[复制链接]
发表于 2008-8-1 22:23:13 | 显示全部楼层
出去乘凉
似乎找到了方法
用线性序列表示栈
首先压入运算符号,再压入数字
得到全部组合,则会得到所有的可能解
现在问题是,似乎要限定解的上限,否则太大
我想,2*n^2是否足够大?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-2 09:12:05 | 显示全部楼层

还要实现一个基于栈的表达式计算函数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-2 10:41:28 | 显示全部楼层
昨天想了一会儿没脸把如此显然的结论贴上来,今天来丢一下脸
还可以剪枝,设a[n]是长度n的数列第一个无法表示的数值
a[1]=2
a[2]=4
a[3]=10
...
则对于a[n]必有a[n]>n(n+1)/2,可以减少检测范围
证明:
对于n的情况,由数归证得的a[n-1]>=n
通过构造n+(p[n-1]) 可以表示n+1...n+a[n-1]-1
通过构造n+n-1+(p[n-2])可以表示n+n-1+1...n+n-1+a[n-2]-1
...
得n+1...n(n+1)/2都可以表示
通过构造n-(p[n-1])可以表示1到n-1的数
而n可以由n*(1)表示(1)由1...n-1表示
得证
后来在车上想到下界还能更好,没来的及好好想,楼下继续

mathe能把1...10的结果爆料一下吗?寻找一下更好的思路

[ 本帖最后由 kenmark 于 2008-8-2 14:04 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-2 11:56:57 | 显示全部楼层
游客,如果您要查看本帖隐藏内容请回复
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-3 07:46:40 | 显示全部楼层
mathe
能否证明
a[n] <= n * [n-1]
====================
PS:
还可以构造
n * a[n-1] n * (n-1) * a[n - 1]等

用构造法应该能得到非显然的下界
但无法得到准确下界
只能暴力搜索么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-3 08:58:16 | 显示全部楼层
对于
+ * 2 3 - 4 1
表示(2 * 3) + (4 - 1)
类型的表达式树
如何计算比较好?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-3 09:14:24 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #define max 16

  4. int calc[max * max];
  5. int maxlevel;
  6. int operator[4] = {-1, -2, -3, -4}; // + - * /
  7. int mask[max + 1];
  8. int n;
  9. int le; //剩余数字  
  10. int position;
  11. int counter;

  12. void init(void)
  13. {
  14.   int i;
  15.   for (i = 1; i <= max; i ++)
  16.     mask[i] = 0;
  17.   position = 0;
  18.   counter = 0;
  19. }

  20. //返回0代表表达式合法,-1代表除法不能除尽,-2代表除以0,-3代表结果为负
  21. int check(void)
  22. {
  23.   int i;
  24.   int op;
  25.   int leftNum, rightNum;
  26.   long long Result;
  27.   leftNum = 0;
  28.   rightNum = 0;
  29. //检测得到的数字序列是否合法表达式,如果是,则计算出结果
  30.   for (i = position - 1; i >= 0; i --)
  31.   {
  32. if (calc[i] < 0)
  33.     switch (calc[i])
  34.     {
  35.       case -1:// +
  36.         break;
  37.       case -2:// -
  38.         break;
  39.       case -3:// *
  40.         break;
  41.       case -4:// /
  42.         break;
  43.     }
  44.   }

  45. }

  46. void print(void)
  47. {
  48.   int i;
  49.   for (i = 0; i <= position - 1; i ++)
  50.   {
  51.     if (calc[i] < 0)
  52.     {
  53.             switch (calc[i])
  54.         {
  55.           case -1: printf("+ "); break;
  56.           case -2: printf("- "); break;
  57.           case -3: printf("* "); break;
  58.           case -4: printf("/ "); break;
  59.         }
  60.     }
  61.     else
  62.       printf("%d ", calc[i]);
  63.   }
  64.   printf("\n");
  65.   counter ++;
  66. }

  67. int top(int level)
  68. {
  69.    int i, j;
  70.    if (level < n - 1)
  71.      for (i = 0; i < 4; i ++)
  72.       {
  73.        calc[position++] = operator[i];
  74.        left(level);
  75.        position --;
  76.       }
  77. }

  78. //左的长度要不大于右
  79. int left(int level)
  80. {
  81.   int i;
  82.   for (i = 1; i <= n; i ++)
  83.     if (mask[i] == 0)
  84.       {
  85.        calc[position++] = i;
  86.        mask[i] = 1;
  87.        le --;
  88.        right(level);
  89.        le ++;
  90.        mask[i] = 0;
  91.        position --;
  92.       }       
  93.   top(level + 1);
  94. }

  95. int right(int level)
  96. {
  97.   int i;
  98.   if (le == 1)
  99.   {
  100.     for (i = 1; i <= n; i ++)
  101.       if (mask[i] == 0)
  102.         {
  103.          calc[position++] = i;
  104.          mask[i] = 1;
  105. //         check();
  106.          print();
  107.          position --;
  108.          mask[i] = 0;
  109.         }
  110.   }
  111.   else       
  112.     top(level + 1);
  113. }

  114. int main(void)
  115. {
  116.   printf("Input n value:");
  117.   scanf("%d", &n);
  118.   printf("\n\n");
  119.   init();
  120.   le = n;
  121.   top(0);
  122.   printf("Total: %d\n", counter);
  123.   return 0;
  124. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-3 09:16:50 | 显示全部楼层
n = 2得到8个式子
n = 3  96
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
类型的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-3 18:11:58 | 显示全部楼层
对每个n
不考虑唯一
不考虑结果的合理性

所有可能的式子是
$2^(n-2)*4^(n-1)*n!$
所以随n增大,搜索时间迅速变大

n=10的可能是$2^8*4^9*10! = 243,524,645,683,200$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-4 07:27:21 | 显示全部楼层
这个可以通过 /thread-461-1-1.html 中的统计数据,只计算不等价的表达式,还有$2,894,532,443,154$个,比上面表达式好一些
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-9-17 21:49 , Processed in 0.158372 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表