数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 最小无法表达的正整数
1 ...789101112131415... 18下一页
返回列表 发新帖
楼主: mathe

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

[复制链接]
无心人
发表于 2008-10-2 10:32:02 | 显示全部楼层
失望了 刚去学校 才算到35万多个表达式 看来，越来越难出新的 冲突的概率在增大啊 所以估计至少需要10天甚至50天才能出结果 而这么多天不停电的概率太小了 这个程序很难保存当前状态以避免中断 暂时没停止 希望出现奇迹
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-10-2 10:34:06 | 显示全部楼层
我想至少如果实现了那个以文件存储且仅考虑加减乘的程序 应该能实现保存状态持续计算的 但似乎这个东西有点复杂哦 mathe能估算下对应10的文件存储需求么？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-10-2 15:33:33 | 显示全部楼层
2008-10-02 15:12 416 0202.dat 2008-10-02 15:12 1,248 0302.dat 2008-10-02 15:12 4,992 0303.dat 2008-10-02 15:12 2,496 0402.dat 2008-10-02 15:12 19,968 0403.dat 2008-10-02 15:12 119,808 0404.dat 2008-10-02 15:12 4,160 0502.dat 2008-10-02 15:12 49,920 0503.dat 2008-10-02 15:12 599,040 0504.dat 2008-10-02 15:12 3,194,880 0505.dat 2008-10-02 15:12 6,240 0602.dat 2008-10-02 15:12 99,840 0603.dat 2008-10-02 15:12 1,797,120 0604.dat 2008-10-02 15:12 19,169,280 0605.dat 2008-10-02 15:13 124,600,320 0606.dat 2008-10-02 15:13 8,736 0702.dat 2008-10-02 15:13 174,720 0703.dat 2008-10-02 15:13 4,193,280 0704.dat 2008-10-02 15:14 67,092,480 0705.dat 2008-10-02 15:15 872,202,240 0706.dat 携带所有信息的记录，每个长度104字节，0707的出现错误，怀疑是文件太大了，在3.4G大小后异常结束
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-10-2 15:39:51 | 显示全部楼层
暂时用Delphi语言写的
  1. program minn;
  3. {$APPTYPE CONSOLE}
  5. uses
  6. SysUtils, StrUtils, windows;
  8. var
  9. EndNum: integer = 0;
  10. AddNum: integer = -1;
  11. SubNum: integer = -2;
  12. MulNum: integer = -3;
  14. type
  15. sExpr = record
  16. mask: integer;
  17. result: integer; //可能为负数，只能计算到12
  18. Expr: array[0..23] of integer;
  19. end;
  21. var
  22. num: integer; //输入数字
  23. appPath: string;
  24. numStr: array[0..15] of string[2];
  25. mask: array[0..15] of integer;
  27. procedure Init;
  28. var
  29. i: integer;
  30. begin
  31. numStr[0] := '00';
  32. numStr[1] := '01';
  33. numStr[2] := '02';
  34. numStr[3] := '03';
  35. numStr[4] := '04';
  36. numStr[5] := '05';
  37. numStr[6] := '06';
  38. numStr[7] := '07';
  39. numStr[8] := '08';
  40. numStr[9] := '09';
  41. numStr[10] := '10';
  42. numStr[11] := '11';
  43. numStr[12] := '12';
  44. numStr[13] := '13';
  45. numStr[14] := '14';
  46. numStr[15] := '15';
  47. mask[0] := 1;
  48. for I := 1 to 15 do
  49. mask[i] := mask[i-1] shl 1;
  50. end;
  52. //两个都是单数字
  53. procedure processTwoStep;
  54. var
  55. sFile: File of sExpr;
  56. i, j, fs: integer;
  57. sSFile, prefix: string;
  58. sSExpr: sExpr;
  59. begin
  60. prefix := appPath + numStr[num];
  61. sSFile := prefix + '02.dat';
  62. AssignFile(sFile, sSFile);
  63. Reset(sFile);
  64. fs := FileSize(sFile);
  65. Seek(sFile, fs);
  66. for i := 1 to num - 1 do
  67. for j := i + 1 to num do
  68. begin
  69. sSExpr.mask := mask[i] or mask[j];
  70. sSExpr.result := i + j;
  71. ssExpr.Expr[0] := AddNum;
  72. sSExpr.Expr[1] := i;
  73. sSExpr.Expr[2] := j;
  74. ssExpr.Expr[3] := EndNum;
  75. Write(sFile, sSExpr);
  77. sSExpr.Expr[0] := SubNum;
  78. sSExpr.result := i - j;
  79. Write(sFile, sSExpr);
  81. sSExpr.Expr[0] := MulNum;
  82. sSExpr.result := i * j;
  83. Write(sFile, sSExpr);
  85. sSExpr.result := j - i;
  86. sSExpr.Expr[0] := SubNum;
  87. sSExpr.Expr[1] := j;
  88. sSExpr.Expr[2] := i;
  89. sSExpr.Expr[3] := EndNum;
  90. Write(sFile, sSExpr);
  91. end;
  93. Close(sFile);
  94. end;
  96. //有一个是单数字
  97. procedure processSingleStep(m: integer);
  98. var
  99. mFile, sFile: File of sExpr;
  100. n, i, fs: integer;
  101. sMFile, sSFile, prefix: string;
  102. sMExpr, sSExpr: sExpr;
  103. begin
  104. prefix := appPath + numStr[num];
  105. sMFile := prefix + numStr[m] + '.dat';
  106. sSFile := prefix + numStr[m + 1] + '.dat';
  107. AssignFile(mFile, sMFile);
  108. AssignFile(sFile, sSFile);
  109. Reset(sFile);
  110. fs := FileSize(sFile);
  111. Seek(sFile, fs);
  112. for n := 1 to num do
  113. begin
  114. reset(mFile);
  115. while not eof(mFile) do
  116. begin
  117. Read(mFile, sMExpr);
  118. if (mask[n] and sMExpr.mask = 0) then
  119. begin
  120. sSExpr.mask := mask[n] or sMExpr.mask;
  121. sSExpr.result := n + sMExpr.result;
  122. sSExpr.Expr[1] := n;
  123. for I := 0 to 2 * m - 2 do
  124. sSExpr.Expr[2 + i] := sMExpr.Expr[i];
  125. sSExpr.Expr[0] := AddNum;
  126. sSExpr.Expr[1 + 2 * m] := EndNum;
  127. Write(sFile, sSExpr);
  129. sSExpr.Expr[0] := SubNum;
  130. sSExpr.result := n - sMExpr.result;
  131. Write(sFile, sSExpr);
  133. sSExpr.Expr[0] := MulNum;
  134. sSExpr.result := n * sMExpr.result;
  135. Write(sFile, sSExpr);
  137. sSExpr.result := sMExpr.result - n;
  138. for I := 1 to 2 * m - 1 do
  139. sSExpr.Expr[i] := sMExpr.Expr[i - 1];
  140. sSExpr.Expr[2 * m] := n;
  141. sSExpr.Expr[0] := SubNum;
  142. Write(sFile, sSExpr);
  143. end;
  144. end;
  145. end;
  147. Close(mFile);
  148. Close(sFile);
  149. end;
  151. //两个都是序列表达式
  152. procedure processDoubleStep(n, m: integer);
  153. var
  154. nFile, mFile, sFile: File of sExpr;
  155. fs, i: integer;
  156. sNFile, sMFile, sSFile, prefix: string;
  157. sNExpr, sMExpr, sSExpr: sExpr;
  158. begin
  159. prefix := appPath + numStr[num];
  160. sNFile := prefix + numStr[n] + '.dat';
  161. sMFile := prefix + numStr[m] + '.dat';
  162. sSFile := prefix + numStr[n + m] + '.dat';
  163. AssignFile(nFile, sNFile);
  164. AssignFile(mFile, sMFile);
  165. reset(nFile);
  166. AssignFile(sFile, sSFile);
  167. reset(sFile);
  168. fs := FileSize(sFile);
  169. Seek(sFile, fs);
  170. while not eof(nFile) do
  171. begin
  172. Read(nFile, sNExpr);
  173. reset(mFile);
  174. while not eof(mFile) do
  175. begin
  176. Read(mFile, sMExpr);
  177. if (sNExpr.mask and smExpr.mask = 0) then
  178. begin
  179. sSExpr.mask := sNExpr.mask or sMExpr.mask;
  180. sSExpr.result := sNExpr.result + sMExpr.result;
  181. for I := 1 to 2 * n - 1 do
  182. sSExpr.Expr[i] := sNExpr.Expr[i - 1];
  183. for I := 0 to 2 * m - 2 do
  184. sSExpr.Expr[2 * n + i] := sMExpr.Expr[i];
  185. sSExpr.Expr[0] := AddNum;
  186. sSExpr.Expr[2 * n + 2 * m - 1] := EndNum;
  187. Write(sFile, sSExpr);
  189. sSExpr.Expr[0] := SubNum;
  190. sSExpr.result := sNExpr.result - sMExpr.result;
  191. Write(sFile, sSExpr);
  193. sSExpr.Expr[0] := MulNum;
  194. sSExpr.result := sNExpr.result * sMExpr.result;
  195. Write(sFile, sSExpr);
  197. sSExpr.result := sMExpr.result - sNExpr.result;
  198. for I := 1 to 2 * m - 1 do
  199. sSExpr.Expr[i] := sMExpr.Expr[i - 1];
  200. for I := 0 to 2 * n - 2 do
  201. sSExpr.Expr[2 * m + i] := sNExpr.Expr[i];
  202. sSExpr.Expr[0] := SubNum;
  203. Write(sFile, sSExpr);
  204. end;
  205. end;
  206. end;
  208. Close(nFile);
  209. Close(mFile);
  210. Close(sFile);
  211. end;
  213. procedure processStep(l: integer);
  214. var
  215. i: integer;
  216. sFile: File of sExpr;
  217. sSFile, prefix: string;
  218. begin
  219. prefix := appPath + numStr[num];
  220. sSFile := prefix + numStr[l] + '.dat';
  221. AssignFile(sFile, sSFile);
  222. rewrite(sFile);
  223. Close(sFile);
  225. if (l = 2) then
  226. processTwoStep;
  227. if (l >= 3) then
  228. processSingleStep(l - 1);
  229. if (l >= 4) then
  230. for i := 2 to l div 2 do
  231. processDoubleStep(i, l - i);
  232. end;
  234. var
  235. i: integer;
  236. begin
  237. { TODO -oUser -cConsole Main : Insert code here }
  238. appPath := ExtractFilePath(paramStr(0));
  239. writeln('请输入需要求出数据的num值: ');
  240. readln(num);
  241. Init;
  242. for i := 2 to num do
  243. processStep(i);
  244. end.
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2008-10-2 17:57:10 | 显示全部楼层
我倾向于只保存小文件.
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-10-2 19:51:14 | 显示全部楼层
你的意思是只保存数值，不保存表达式？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2008-10-2 21:14:57 | 显示全部楼层
这个自然,不然保存的信息太多了. 而如果对于一个数值,要计算对应的表达式,只要将匹配的数值逆向再计算一次就应该能够比较快速的找出表达式(可以用来检测程序运行的正确性),但是通常情况没有必要产生这些表达式
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

jiangbin00cn
发表于 2008-10-2 23:05:00 | 显示全部楼层
28 = (2 * 3 + 1) * 4 对n=4 (1+2)*3*4=36 ////////////////////////////////////////////////// 对任意的n(n>2)能够表达的最大整数为 (1+2)*3*4*...*n 如果能够证明，其能够连续表达出1~(1+2)*3*4*...*n的数 那么(1+2)*3*4*...*n+1 就是这个最小正整数
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

jiangbin00cn
发表于 2008-10-2 23:16:02 | 显示全部楼层
不过用1~n这n个数通过四则混合运算表达出来的正整数 最多只可能有 4的(n-1)次方的，在n较大的情况下是远小于 (1+2)*3*4*...*n的 所以，楼主的答案必在1~(1+2)*3*4*...*n之间 有难度
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

jiangbin00cn
发表于 2008-10-2 23:27:12 | 显示全部楼层
不过用1~n这n个数通过四则混合运算表达出来的正整数 最多只可能有 4的(n-1)次方的， ///////////////////////////////////// 这个结论不对，还要考虑括号的情况 那么最大可能有 （4的(n-1)次方）*(n-1)! >(1+2)*3*4*...*n （4的(n-1)次方）*(n-1)! ///////////////////////////////////////////////////// 对任意的n(n>2)能够表达的最大整数为 (1+2)*3*4*...*n 如果能够证明，其能够连续表达出1~(1+2)*3*4*...*n的数 那么(1+2)*3*4*...*n+1 就是这个最小正整数 这条路可能才是王道阿，考虑一下
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1 ...789101112131415... 18下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2025-2-21 03:15 , Processed in 0.033430 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

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