最小无法表达的正整数 - 第11页 - 编程擂台 - 数学研发论坛

无心人 发表于 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-0215:12             416 0202.dat
2008-10-0215:12          1,248 0302.dat
2008-10-0215:12          4,992 0303.dat
2008-10-0215:12          2,496 0402.dat
2008-10-0215:12          19,968 0403.dat
2008-10-0215:12       119,808 0404.dat
2008-10-0215:12          4,160 0502.dat
2008-10-0215:12          49,920 0503.dat
2008-10-0215:12       599,040 0504.dat
2008-10-0215:12       3,194,880 0505.dat
2008-10-0215:12          6,240 0602.dat
2008-10-0215:12          99,840 0603.dat
2008-10-0215:12       1,797,120 0604.dat
2008-10-0215:12    19,169,280 0605.dat
2008-10-0215:13    124,600,320 0606.dat
2008-10-0215:13          8,736 0702.dat
2008-10-0215:13       174,720 0703.dat
2008-10-0215:13       4,193,280 0704.dat
2008-10-0215:14    67,092,480 0705.dat
2008-10-0215:15    872,202,240 0706.dat
携带所有信息的记录，每个长度104字节，0707的出现错误，怀疑是文件太大了，在3.4G大小后异常结束

无心人 发表于 2008-10-2 15:39:51

暂时用Delphi语言写的program minn;

{$APPTYPE CONSOLE}

uses
SysUtils, StrUtils, windows;

var
EndNum: integer = 0;
AddNum: integer = -1;
SubNum: integer = -2;
MulNum: integer = -3;

type
sExpr = record
mask: integer;
result: integer; //可能为负数，只能计算到12
Expr: array of integer;
end;

var
num: integer; //输入数字
appPath: string;
numStr: array of string;
mask: array of integer;

procedure Init;
var
i: integer;
begin
numStr := '00';
numStr := '01';
numStr := '02';
numStr := '03';
numStr := '04';
numStr := '05';
numStr := '06';
numStr := '07';
numStr := '08';
numStr := '09';
numStr := '10';
numStr := '11';
numStr := '12';
numStr := '13';
numStr := '14';
numStr := '15';
mask := 1;
for I := 1 to 15 do
mask := mask shl 1;
end;

//两个都是单数字
procedure processTwoStep;
var
sFile: File of sExpr;
i, j, fs: integer;
sSFile, prefix: string;
sSExpr: sExpr;
begin
prefix := appPath + numStr;
sSFile := prefix + '02.dat';
AssignFile(sFile, sSFile);
Reset(sFile);
fs := FileSize(sFile);
Seek(sFile, fs);
for i := 1 to num - 1 do
for j := i + 1 to num do
   begin
   sSExpr.mask := mask or mask;
   sSExpr.result := i + j;
   ssExpr.Expr := AddNum;
   sSExpr.Expr := i;
   sSExpr.Expr := j;
   ssExpr.Expr := EndNum;
   Write(sFile, sSExpr);

   sSExpr.Expr := SubNum;
   sSExpr.result := i - j;
   Write(sFile, sSExpr);

   sSExpr.Expr := MulNum;
   sSExpr.result := i * j;
   Write(sFile, sSExpr);

   sSExpr.result := j - i;
   sSExpr.Expr := SubNum;
   sSExpr.Expr := j;
   sSExpr.Expr := i;
   sSExpr.Expr := EndNum;
   Write(sFile, sSExpr);
   end;

Close(sFile);
end;

//有一个是单数字
procedure processSingleStep(m: integer);
var
mFile, sFile: File of sExpr;
n, i, fs: integer;
sMFile, sSFile, prefix: string;
sMExpr, sSExpr: sExpr;
begin
prefix := appPath + numStr;
sMFile := prefix + numStr + '.dat';
sSFile := prefix + numStr + '.dat';
AssignFile(mFile, sMFile);
AssignFile(sFile, sSFile);
Reset(sFile);
fs := FileSize(sFile);
Seek(sFile, fs);
for n := 1 to num do
begin
reset(mFile);
while not eof(mFile) do
begin
   Read(mFile, sMExpr);
   if (mask and sMExpr.mask = 0) then
   begin
   sSExpr.mask := mask or sMExpr.mask;
   sSExpr.result := n + sMExpr.result;
   sSExpr.Expr := n;
   for I := 0 to 2 * m - 2 do
      sSExpr.Expr := sMExpr.Expr;
   sSExpr.Expr := AddNum;
   sSExpr.Expr := EndNum;
   Write(sFile, sSExpr);

   sSExpr.Expr := SubNum;
   sSExpr.result := n - sMExpr.result;
   Write(sFile, sSExpr);

   sSExpr.Expr := MulNum;
   sSExpr.result := n * sMExpr.result;
   Write(sFile, sSExpr);

   sSExpr.result := sMExpr.result - n;
   for I := 1 to 2 * m - 1 do
      sSExpr.Expr := sMExpr.Expr;
   sSExpr.Expr := n;
   sSExpr.Expr := SubNum;
   Write(sFile, sSExpr);
   end;
end;
end;

Close(mFile);
Close(sFile);
end;

//两个都是序列表达式
procedure processDoubleStep(n, m: integer);
var
nFile, mFile, sFile: File of sExpr;
fs, i: integer;
sNFile, sMFile, sSFile, prefix: string;
sNExpr, sMExpr, sSExpr: sExpr;
begin
prefix := appPath + numStr;
sNFile := prefix + numStr + '.dat';
sMFile := prefix + numStr + '.dat';
sSFile := prefix + numStr + '.dat';
AssignFile(nFile, sNFile);
AssignFile(mFile, sMFile);
reset(nFile);
AssignFile(sFile, sSFile);
reset(sFile);
fs := FileSize(sFile);
Seek(sFile, fs);
while not eof(nFile) do
begin
Read(nFile, sNExpr);
reset(mFile);
while not eof(mFile) do
begin
   Read(mFile, sMExpr);
   if (sNExpr.mask and smExpr.mask = 0) then
   begin
   sSExpr.mask := sNExpr.mask or sMExpr.mask;
   sSExpr.result := sNExpr.result + sMExpr.result;
   for I := 1 to 2 * n - 1 do
      sSExpr.Expr := sNExpr.Expr;
   for I := 0 to 2 * m - 2 do
      sSExpr.Expr := sMExpr.Expr;
   sSExpr.Expr := AddNum;
   sSExpr.Expr := EndNum;
   Write(sFile, sSExpr);

   sSExpr.Expr := SubNum;
   sSExpr.result := sNExpr.result - sMExpr.result;
   Write(sFile, sSExpr);

   sSExpr.Expr := MulNum;
   sSExpr.result := sNExpr.result * sMExpr.result;
   Write(sFile, sSExpr);

   sSExpr.result := sMExpr.result - sNExpr.result;
   for I := 1 to 2 * m - 1 do
      sSExpr.Expr := sMExpr.Expr;
   for I := 0 to 2 * n - 2 do
      sSExpr.Expr := sNExpr.Expr;
   sSExpr.Expr := SubNum;
   Write(sFile, sSExpr);
   end;
end;
end;

Close(nFile);
Close(mFile);
Close(sFile);
end;

procedure processStep(l: integer);
var
i: integer;
sFile: File of sExpr;
sSFile, prefix: string;
begin
prefix := appPath + numStr;
sSFile := prefix + numStr + '.dat';
AssignFile(sFile, sSFile);
rewrite(sFile);
Close(sFile);

if (l = 2) then
processTwoStep;
if (l >= 3) then
processSingleStep(l - 1);
if (l >= 4) then
for i := 2 to l div 2 do
   processDoubleStep(i, l - i);
end;

var
i: integer;
begin
{ TODO -oUser -cConsole Main : Insert code here }
appPath := ExtractFilePath(paramStr(0));
writeln('请输入需要求出数据的num值: ');
readln(num);
Init;
for i := 2 to num do
processStep(i);
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 2 3 4 5 6 7 8 9 10 [11] 12 13 14 15 16 17 18

数学研发论坛's Archiver