数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2008-8-4 11:28:48 | 显示全部楼层
我只用过gdb,不过我是用ddd(提供的图形界面还可以),它封装的gdb.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-4 16:01:14 | 显示全部楼层
要疯了
怎么也无法枚举每种状态
已解决加乘的左右交换问题
但对减除的左面是树,右面是叶子的
表达式树,怎么也无法枚举出来
枚举打印的都缺少叶子,哎
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-4 16:02:40 | 显示全部楼层
重新写的求值函数
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <sys/time.h>

  4. #define max 16
  5. #define nmax 64 * 1024 * 1024

  6. int calc[2 * max - 1];
  7. int operator[4] = { -1, -3, -2, -4 };        // + * - /
  8. int mask[max + 1]; //代表数字是否被使用
  9. int nmask[nmax]; //表示的数字
  10. int n;
  11. int leaf;                        //剩余数字  
  12. int position;
  13. int counter;

  14. void
  15. init (void)
  16. {
  17.         int i;
  18.         for (i = 1; i <= max; i++)
  19.                 mask[i] = 0;
  20.         position = 0;
  21.         counter = 0;
  22.         leaf = n;
  23.         memset(nmask, 0, nmax * sizeof(int));
  24. }

  25. void search(void)
  26. {
  27.         int i;
  28.         for (i = 1; i < nmax; i ++)
  29.                 if (nmask[i] == 0)
  30.         {
  31.                 printf("\nmin: %d\n", i);
  32.                 break;
  33.         }
  34. }

  35. //返回0代表表达式合法,-1代表除法不能除尽,-2代表除以0,-3代表结果为负
  36. int print(void)
  37. {
  38.         int i;
  39.         int opTop = 0, numTop = 0;
  40.         long long temp;
  41.         long long numBuffer[max];
  42.         int itemp;
  43.        
  44.         for (i = 2 * n - 2; i >= 0; i --)
  45.         {
  46.                 if (calc[i] < 0)
  47.                 {
  48.                         switch (calc[i])
  49.                         {
  50.                                 case -1:
  51.                                         temp = numBuffer[numTop - 1] + numBuffer[numTop - 2];
  52.                                         break;
  53.                                 case -2:
  54.                                         temp = numBuffer[numTop - 1] - numBuffer[numTop - 2];
  55.                                         break;
  56.                                 case -3:
  57.                                         temp = numBuffer[numTop - 1] * numBuffer[numTop - 2];
  58.                                         break;
  59.                                 case -4:
  60.                                         if (numBuffer[numTop - 2] == 0)
  61.                                                 return (-2);
  62.                                         if (numBuffer[numTop - 1] % numBuffer[numTop - 2] > 0)
  63.                                                 return (-1);
  64.                                         temp = numBuffer[numTop - 1] / numBuffer[numTop - 2];
  65.                                         break;
  66.                         }
  67.                         numTop -= 1;                                                                                                                                                                                                                                                                                                                                                                               
  68.                         numBuffer[numTop - 1] = temp;
  69.                 }
  70.                 else
  71.                         numBuffer[numTop ++] = calc[i];
  72.         }
  73.        
  74.         temp = numBuffer[0];
  75.         if (temp < 0) return (-3);
  76.         if (temp < nmax)
  77.         {
  78.                 itemp = temp;
  79.                 if (nmask[itemp] == 0)
  80.                 {
  81.                         counter++;
  82.                         printf("%d: %d ", counter, itemp);
  83.                         for (i = 0; i <= 2 * n - 2; i++)
  84.                         {
  85.                                 if (calc[i] < 0)
  86.                                 {
  87.                                         switch (calc[i])
  88.                                         {
  89.                                                 case -1:
  90.                                                         printf ("+ ");
  91.                                                         break;
  92.                                                 case -2:
  93.                                                         printf ("- ");
  94.                                                         break;
  95.                                                 case -3:
  96.                                                         printf ("* ");
  97.                                                         break;
  98.                                                 case -4:
  99.                                                         printf ("/ ");
  100.                                                         break;
  101.                                         }
  102.                                 }
  103.                                 else
  104.                                         printf ("%d ", calc[i]);
  105.                         }
  106.                         printf ("\n");
  107.                        
  108.                         nmask[itemp] = 1;       
  109.                 }
  110.         }
  111.        
  112.         return (0);
  113. }

  114. int
  115. printOnly (void)
  116. {
  117.         int i;
  118.         for (i = 0; i <= 2 * n - 2; i++)
  119.         {
  120.                 if (calc[i] < 0)
  121.                 {
  122.                         switch (calc[i])
  123.                         {
  124.                                 case -1:
  125.                                         printf ("+ ");
  126.                                         break;
  127.                                 case -2:
  128.                                         printf ("- ");
  129.                                         break;
  130.                                 case -3:
  131.                                         printf ("* ");
  132.                                         break;
  133.                                 case -4:
  134.                                         printf ("/ ");
  135.                                         break;
  136.                         }
  137.                 }
  138.                 else
  139.                         printf ("%d ", calc[i]);
  140.         }
  141.         printf ("\n");
  142.         counter++;
  143. }

  144. void
  145. printBlank (void)
  146. {
  147.         counter++;
  148. }

  149. int
  150. top (int MaxNode)
  151. {
  152.         int i;
  153.         if (MaxNode >= 1)
  154.                 for (i = 0; i < 4; i++)
  155.         {
  156.                 calc[position++] = operator[i];
  157.                 if (i < 2)
  158.                         subNode (MaxNode - 1, 1);
  159.                 else
  160.                         subNode (MaxNode - 1, 0);
  161.                 position--;
  162.         }
  163. }

  164. void
  165. addmul (void)
  166. {
  167.         int i, j;
  168.         for (i = 1; i <= n - 1; i++)
  169.                 if (mask[i] == 0)
  170.         {
  171.                 mask[i] = 1;
  172.                 leaf--;
  173.                 calc[position++] = i;
  174.                 for (j = i + 1; j <= n; j++)
  175.                         if (mask[j] == 0)
  176.                 {
  177.                         calc[position++] = j;
  178.                         mask[j] = 1;
  179.                         leaf--;
  180.                         if (leaf == 0)
  181.                         {
  182.                                 // check();
  183.                                 print ();
  184.                         }
  185.                         mask[j] = 0;
  186.                         leaf++;
  187.                         position--;
  188.                 }
  189.                 leaf++;
  190.                 position--;
  191.                 mask[i] = 0;
  192.         }
  193. }

  194. void
  195. subdiv (void)
  196. {
  197.         int i, j;
  198.         for (i = 1; i <= n; i++)
  199.                 if (mask[i] == 0)
  200.         {
  201.                 mask[i] = 1;
  202.                 leaf--;
  203.                 calc[position++] = i;
  204.                 for (j = 1; j <= n; j++)
  205.                         if (mask[j] == 0)
  206.                 {
  207.                         calc[position++] = j;
  208.                         mask[j] = 1;
  209.                         leaf--;
  210.                         if (leaf == 0)
  211.                         {
  212.                                 // check();
  213.                                 print ();
  214.                         }
  215.                         mask[j] = 0;
  216.                         leaf++;
  217.                         position--;
  218.                 }
  219.                 leaf++;
  220.                 position--;
  221.                 mask[i] = 0;
  222.         }
  223. }

  224. void
  225. leftFill (int MaxNode)
  226. {
  227.         int i;
  228.         for (i = 1; i <= n; i++)
  229.                 if (mask[i] == 0)
  230.         {
  231.                 calc[position++] = i;
  232.                 leaf--;
  233.                 mask[i] = 1;
  234.                 top (MaxNode);
  235.                 position--;
  236.                 leaf++;
  237.                 mask[i] = 0;
  238.         }
  239. }

  240. void
  241. rightFill (int MaxNode)
  242. {
  243.         int i;
  244.         for (i = 1; i <= n; i++)
  245.                 if (mask[i] == 0)
  246.         {
  247.                 mask[i] = 1;
  248.                 calc[position + 2 * MaxNode + 1] = i;
  249.                 leaf--;
  250.                 top (MaxNode);
  251.                 leaf++;
  252.                 mask[i] = 0;
  253.         }
  254. }

  255. int
  256. subNode (int MaxNode, int exchange)
  257. {
  258.         int i, j;
  259.         if (MaxNode == 0)
  260.         {
  261.                 if (exchange == 1)
  262.                         addmul ();
  263.                 else
  264.                         subdiv ();
  265.         }
  266.        
  267.         if (MaxNode >= 1)
  268.         {
  269.                 //1\fill left
  270.                 leftFill (MaxNode);
  271.                 //2\fill right
  272.                 if (exchange == 0)
  273.                         rightFill (MaxNode);
  274.         }
  275.        
  276.         //3\top(left) top(right)
  277.         if (MaxNode >= 2)
  278.                 for (i = 1; i < MaxNode; i++)
  279.         {
  280.                 top (i);
  281.                 top (MaxNode - i);
  282.         }
  283. }

  284. int
  285. main (void)
  286. {
  287.         struct timeval start, end;
  288.         double timeuse;
  289.         printf ("Input n value:");
  290.         scanf ("%d", &n);
  291.         printf ("\n\n");
  292.         gettimeofday (&start, NULL);
  293.         init ();
  294.         top (n - 1);
  295.         printf ("\nTotal: %d\n", counter);
  296.         search();
  297.         gettimeofday (&end, NULL);
  298.         timeuse =
  299.                 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
  300.         timeuse /= 1000000;
  301.         printf ("\n\nUsed Time:%8.6f\n\n", timeuse);
  302.         return 0;
  303. }
复制代码
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 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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没找到解
你的解是?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-9-20 10:34 , Processed in 0.146077 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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