高分解决大难题!(200)

1+(1+(-1))=1
1+(1+(-1))+(1+0)=2
1+(1+(-1))+(1+0)+(1+1)=4
1+(1+(-1))+(1+0)+(1+1)+(1+2)=7
..
int j=1;
for(int i=-1;i<35;i++){
j=j+(1+i);
print(j);
}
哈阿，不用3小时把！？(631)

heifei老兄，题目都没有搞清楚就开始做了，哈哈！~
这个题目计算量的确太大了，抱歉，我也没有什么好的办法！关注中……

这个问题不难，运算时间小于1秒，如下
unit Unit1;interfaceuses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;
type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
    Flags:Array [1..1000000] of Boolean;//标志数组，记录差值是否被占用
    Results:Array [1..36] of integer;  //结果数组
    function GetFirstFree:integer;     //求出标志数组中第一个空缺
    function GetNextFree(Cur:integer):integer;//求标志数组中下一个空缺
    function CanUse(index,val:integer):Boolean; //判断结果数组中加入一个新的值是否合法
    procedure  AddNewVal(index,val:integer); //在结果数组中加入一个新的值
  end;var
  Form1: TForm1;implementation{$R *.dfm}procedure TForm1.FormCreate(Sender: TObject);
var
  i:Integer;
begin
  for i:=1 to 1000000 do
   Flags[i]:=False;
end;function TForm1.GetFirstFree: integer;
var
  i:integer;
begin
  for i:=1 to 1000000 do
    if not Flags[i] then
    begin
     Result:=i;
     exit;
    end;
  result:=0;
end;function TForm1.GetNextFree(Cur: integer): integer;
var
  i:integer;
begin
  for i:=Cur+1 to 1000000 do
    if not Flags[i] then
    begin
     Result:=i;
     exit;
    end;
  result:=0;
end;procedure TForm1.Button1Click(Sender: TObject);
var
  i,j,nextvalue:integer;
begin
  Results[1]:=1;
  i:=1;
  for i:=2 to 36 do
  begin
    j:=GetFirstFree;
    while not CanUse(i,Results[i-1]+j) do
      j:=GetNextFree(j);
    AddNewVal(i,Results[i-1]+j);
  end;
  for i:=1 to 36 do
  Memo1.Lines.Add(inttostr(Results[i]));
end;function TForm1.CanUse(index, val: integer): Boolean;
var
  i:integer;
begin
  for i:=1 to index-1 do
   if Flags[val-Results[i]] then
   begin
     result:=false;
     exit;
   end;
  result:=true;
end;procedure TForm1.AddNewVal(index, val: integer);
var
  i:integer;
begin
  for i:=1 to index-1 do
   Flags[val-Results[i]]:=true;
  Results[index]:=val;
end;end.

to Cipherliu(孤鹰)
老兄,你的算法好像不是最优的!
我要求第36个数最小!!!!!!
谢谢关注

fuyifan() 说的对阿.
这种算法的问题要比整天折腾那些控件有意思多了.
那位有高招阿???????

to winglion(铁石)
很不错的设想!
但是,有一点就是,最优值的时候并不能保证差值是个连续的序列.
如:个数为10时,最优解应该是
1 2 7 11 24 27 35 42 54 56 并不满足你的推断
还有5:
1 2 5 10 12

我来试一试如何？
var
  i:integer;
  Test;array[0..35] of integer;
begin
  Test[0]:=1;
  for i:=1 to 35 do
    test[i]:=Test[i-1]+i;
end;

to a12345(唯微)
谢谢关注,不过您好像没有看清题目要求求一递增整数序列,共36个数,第一个数为1,后面数逐渐增大
任意(是任意***)两个整数的差(大整数减去小整数)均不相同
如:1 2 4 8 .....
求所有情况中第36个数(也就是最大数)最小时的解,即输出这36个数求最小解!!!!

phy(我希望我是高手，却怎么学都是菜鸟。) 何出此言啊?

n(n-1)/2+1 (n:1..36)
第36个数为631
第10个数为46
第5个数为11

to wrsy(wuren)
这种思路有问题,你可以试试,5,怎么才能为11,看看此时前四个数是多少?

其实是数学问题，假设有N个数，那么要满足条件则差序列应为
1,2,3...C（N，2），现在设N取值为X那么X-1应等于C（N，2）
所以X=C（N，2）+1，当N等于36时X=631。我觉得电脑是人类
思维的延伸，没必要每件事都要靠电脑。

： openlab(nick) 谢谢参与
不过,最优解并不能保证
差序列为
1,2,3...C（N，2），

同意 winglion(铁石)兄。
最优解时，序列的通项为 n*(n-1)/2+1，即不管n为多少时， n*(n-1)/2+1为该序列的最小的第n项。To del_c_sharp(头大中......) ：
个数为10时,最优解应该是
1 2 4 7 11 16 22 29 37 46 heifei()也能保证这一点，只是for(int i=-1;i<35;i++)大概应改为
for(int i=-1;i<34;i++)

to chao_jian()
1 2 4 7 11 16 22 29 37 46 并不满组条件
7-4 = 3 = 4-1有两个差相同！
请再看看题目，要求是任意两个
谢谢参与

to chao_jian()，你也没有注意题目中要求任意两个整数的差均不相同！

： unionsoftzboy(unionsoftzboy)
你先把思路说说吧

如果差序列不连续那么一定不是最优解，n个数一共有c(n,2)种差值，
要求每个差值均不相同且保证第n个数最小，那么只有差序列连续的时候
才能达到。就像n=4时1，3，6，7差序列为（7-6），（3-1），（6-3），
（7-3），（6-1），（7-1）而1，2，4，8的差序列为1，2，3，4，6，7，
‘5’被‘7’取代了，而‘7’只能是由最大值减最小值产生就导致了第四
个数为‘8’。

to openlab(nick)
关键是给定长度n后
你并不一定能产生连续差序列
比如 n=5
我算出的最优解为
1 2 5 10 12
差
1 2 3 4 5 7 8 9 10 11 没有6你能给出一个长度为5 的差连续序列吗?

5个数的时候最大数是12。
1 2 5 10 12。
1 3 8 9 12。
1 3 8 11 12。
1 4 5 10 12。
穷举来算恐怕很难。这个问题还可以换种说法。
求这样一个含有k个数的数列，满足下面条件：
1、任何相邻两个数的和 M 不再此数列中,并且数列仅有这一组相邻数之和等于 M。
2、满足条件1且数列的和最小。2、

上面的说法有误，不正确。向大家道歉！第一条应该改为：
任何相邻N个数的和 Total 不再此数列中,并且数列不再存在这样连续的 M 个数：这M个数之和为 Total。

unit Unit1;interfaceuses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;type
  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;var
  Form1: TForm1;
        //思路：把任意两数的差存在一个叫‘h‘的数组里,结果存在一个叫Result的数组里
        //每次我都取h中最大的数（当前最后一个数）和Result中最大的数项加得后一个Result数组中的结果-
        //既下一个结果，并保证Result数组中任意两数的差不同。
        //如果h数组中的的数是1,2,3...连续的，那么求出的Result必定最小
        //因为 h数组中只用到最大的数，so，只需用一个integer来存
        iTemp,iMaxUsed:integer;
        Result:array [1..36] of integer;implementation{$R *.DFM}procedure TForm1.Button1Click(Sender: TObject);
begin
        Result[1]:=1;
        Result[2]:=2;
        iMaxUsed:=1;
        for iTemp:=3 to 36 do
        begin
                 iMaxUsed:=Result[iTemp-1]-1+iMaxUsed;
                 Result[iTemp]:=Result[iTemp-1]+iMaxUsed;        end;
        ShowMessage(IntToStr(Result[36]));end;end.

to ggyy_csdn(开心)x谢谢参与.不过你的想法已经有人说过了,你看看以前的
有问题的!

unionsoftzboy(unionsoftzboy)的解法有问题，从第九个开始出现了重复的差值
31-2=60-31=29
我按照他的思路，解出来的结果有问题
越往下差值相同的越多，算法有问题，正确的解法，正在进行中！

afei78223(阿飞)是的,那个算法的确有点问题

得到的结果和 Cipherliu(孤鹰) ( ) 一样，呵呵！好象的确不是最优解啊！

1, 3, 4, 7, 11, 18, 31, 51, 82,
133, 215, 348, 563, 913, .......
用费波那切数列试验一下
A1 = 1
A2 = 3
An = A[n-1] + A[n-2]

各位大侠，关于我的想法，很简单：
36个数，要求任意两数差值不同，则差值之和为1+2+3+...+35,
设Num[n]=Num[n-1]+SubNum[m];
其中SubNum[m]始终是从未出现过的最小差值
最终结果为：1318
希望和各位大侠共同探讨，运行时间0.X秒

对应于一个n,可能的结果有很多种（所求的最小值唯一，但对应的数列不是唯一的）
如
5的时候是12
1 3 8 11 12  符合要求的解12

1 4 5 10 12  符合要求的解12

1 2 5 10 12  符合要求的解12

1 3 8 9 12  符合要求的解126的时候是18

1 6 8 14 17 18  符合要求的解18

1 3 8 14 17 18  符合要求的解18

1 5 7 10 17 18  符合要求的解18

1 4 6 10 17 18  符合要求的解18 1 2 5 11 16 18  符合要求的解18

1 2 9 13 15 18  符合要求的解18

1 2 9 12 14 18  符合要求的解18

1 2 5 11 13 18  符合要求的解18

7的时候是26
1 3 8 16 22 25 26  符合要求的解26

1 3 6 15 19 25 26  符合要求的解26

1 3 7 10 15 25 26  符合要求的解26

1 5 10 16 23 24 26  符合要求的解26

1 2 8 12 21 24 26  符合要求的解26

1 2 12 17 20 24 26  符合要求的解26

1 4 5 13 19 24 26  符合要求的解26

1 2 5 11 19 24 26  符合要求的解26

1 3 8 14 22 23 26  符合要求的解26

1 3 4 11 17 22 26  符合要求的解26 8的时候是35
1 3 13 20 26 31 34 35  符合要求的解35

1 2 5 10 16 23 33 35  符合要求的解35
  .................................
  .................................所以不能使用递推的方法来计算，因为知道了n，没办法推算n+1的结果,用穷举的方法太慢了！

to unionsoftzboy(unionsoftzboy):
31-2=60-31

I spend a lot of time on this problem,but just know what you said.
Yes,it's really interesting! Pay attention on it!

to del_c_sharp(头大中......)
你确定第36个数小于1500的一定存在吗？

楼主说算法不难，但我觉得目前还没有一个算法能保证得到符合要求的第36个数是最小的。因为我们看 mist(浮尘) 这个例子：
5个数的时候最小数是12。
1 2 5 10 12。
1 3 8 9 12。
1 4 5 10 12。
......
但我们如果考虑4个数时最小数就是7（1 3 6 7）
但我们如果考虑3个数时最小数就是4（1 3 4）结论：36个符合要求的序列中前35个数和只考虑35个数得到的序列不一定相同。

楼主说算法不难，但我觉得到目前为止还没有一个正确的算法。看 mist(浮尘) 的列举的：
5个数的时候最小数是12。
1 2 5 10 12。
1 3 8 9 12。
1 4 5 10 12。
...
如果只考虑4个数时最小数就是7（1 3 6 7）
如果只考虑3个数时最小数就是4（1 2 4）结论：36个符合要求的序列（第36个数最小）中前35个数与只考虑35个数得到第序列不一定相同，即不能简单的从前往后取数，而需要整体考虑这36个数。

一大堆人在这里算。 -.-!答案是667function GetMinResult(Start,Num,Step:integer):integer ;
var
    TempValue:integer;
    i:integer;
begin
    Result:=Start;
    TempValue := Num;
    while TempValue >=1  do
    begin
        inc(Result,TempValue);
        dec(TempValue,Step);
    end;
end;1
37
72
106
139
171
202
232
261
289
316
342
367
391
414
436
457
477
496
514
531
547
562
576
589
601
612
622
631
639
646
652
657
661
664
666
667

唉呀，出错了，多了1，这才是对的。答案是631function GetMinResult(Start,Num,Step:integer):integer ;
var
    TempValue:integer;
    i:integer;
begin
    Result:=Start;
    TempValue := Num-1;
    while TempValue >=1  do
    begin
        inc(Result,TempValue);
        dec(TempValue,Step);
    end;
end;1
36
70
103
135
166
196
225
253
280
306
331
355
378
400
421
441
460
478
495
511
526
540
553
565
576
586
595
603
610
616
621
625
628
630
631

to DepYuka() ( )
631-628=628-625=3
631-625=616-610=6
630-625=621-616=5
.................
这种方法肯定不行，你不能保证任意两个数的差不相等

我把自己的代码付上:
unit Unit1;interfaceuses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    Edit1: TEdit;
    Edit2: TEdit;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;var
  Form1: TForm1;
  intv:array[1..8000] of integer;
  d:array[1..36] of integer;implementation{$R *.dfm}function intv_ok(vl,j:integer):boolean;
var
i,m,c:integer;begin
   c:=(j-2)*(j-1) div 2;
   result:=true;
   if j>=3 then
     begin
        for i:=1 to c  do
          for m:=1 to j-1 do
            if vl-d[m]=intv[i] then
                               begin
                                 result:=false;
                                 exit;
                               end;
     end;
end;procedure intv_ins(vl,j:integer);
var
i,c1,c2:integer;
begin
  c1:=(j-2)*(j-1) div 2+1 ;
  c2:=(j-2)*(j-1) div 2+j-1;
  for i:=c1 to c2  do
    intv[i]:=vl-d[i-(j-2)*(j-1) div 2];
end;
procedure TForm1.Button1Click(Sender: TObject);
var
  rs:array[1..36] of integer;
  i,j,vl,max36:integer;
  back:boolean;
  c:integer;
  l:longint;
begin
  l:=GetTickCount ;
  c:=strtoint(edit1.Text);
  max36:=3000;
  for i:=1 to 36 do
  begin
    d[i]:=1;
    intv[i]:=0;
  end;
  intv[1]:=1;
  j:=2;
  repeat
    vl:=d[j];
    back:=false;
    while ((vl<=d[j-1])or( not intv_ok(vl,j))) do
      begin
        vl:=vl+1;
        if vl>max36 then
                     begin                       j:=j-1;
                       d[j]:=d[j]+1;                       back:=true;
                       break;
                     end;
      end;    if not back then                   if vl>max36 then
                     begin                       j:=j-1;
                       d[j]:=d[j]+1;                     end
                   else
                   begin
                    d[j]:=vl;
                    intv_ins(vl,j);
                    j:=j+1;
                    if j=c+1 then
                              begin
                               if d[c]<max36 then
                                   begin
                                     for i:=1 to c do
                                       rs[i]:=d[i];
                                     max36:=d[c];
                                     if max36<strtoint(edit2.Text) then j:=2;
                                       memo1.Clear ;
                                     for i:=1 to c do
                                     memo1.Lines.Add(inttostr(rs[i]));
                                     memo1.Lines.SaveToFile('data.txt');
                                     Application.ProcessMessages ;
                                   end;
                               j:=j-2;
                               d[j]:=d[j]+1;                              end
                    else d[j]:=d[j-1]+1;
                  end;
  until (j<2) ;
  memo1.Clear ;
for i:=1 to c do
memo1.Lines.Add(inttostr(rs[i]));
showmessage(inttostr(GetTickCount-l));
end;end.

我同意openlab(nick) 的意见。
其实我们考察下列命题：
    有两个整数序列A(A1,A2,A3 ... A(n)) 和 B(B1,B2,... B(n-1))，A1 = 1
            满足A(i+1) = A(i)+B(i)  其中 i = 1,2,3, .... n-1,
            且B(i)<>B(j), B(i)>0    i,j = 1,2,3 ... n-1

            求取A(n)的Min最优解。

    当n=36时，命题成为楼上兄弟[ del_c_sharp (头大中......)]的题目。

    其实这个命题求不难，由于A1 = 1，
    A(n) = B(n-1)+A(n-1)
         = B(n-1)+B(n-2)+A(n-2)
         = B(n-1)+B(n-2)+B(n-3)+ ... +B2+B1+A1
    于是，求A(n)的Min解，变成了求  B1+B2+ ... +B(n-1)的最小值的解。
    由于B(i)<>B(j)，B(i)>0，显然，B1+B2+ ...+ B(n-1)的最小值的解是 1+2+...+(n-1)
    于是A(n)= 1+ 1+ 2 + ... + (n-1)

下面有下段程序，用笨办法来实现一种序列，最优解序列有多种，这只是其中最简单的一种：unit .........implementation
const
    nBound:integer = 36;var
    nA,nB:array[0..35] of integer; //nA 存放序列的数，nB存放差值
    i:integer;
procedure TForm1.Button1Click(Sender: TObject);
var
   i,j:integer;
   s1,s2:string;
begin
    nB[0] := 1;
    s1 := IntToStr(nA[0])+', ';
    for i:= 1  to nBound-1 do begin
        nA[i] := nA[i-1];
        j := 0;
        if i>1 then
            nB[i-1] := nB[i-2];
        while (j<i-1) do begin   //检查有没有相同的差值
            if (nB[j]= nB[i-1]) then Inc(nB[i-1]);
            inc(j);
        end;
        nA[i] := nA[i-1]+ nB[i-1];
        s1 := s1+ IntToStr(nA[i]);
        if i<(nBound-1) then
            s2 := s2+ IntToStr(nB[i-1]);
        if i <> (nBound-1) then
        begin
            s1 := s1+', ';
            if i<(nBound-2) then
                s2 := s2+', ';
        end;
    end;
    Memo1.Lines.Add('');
    Memo1.Lines.Add('数据序列是：');
    Memo1.Lines.Add(s1);
    Memo1.Lines.Add('差是：');
    Memo1.Lines.add(s2);
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
    Memo1.Lines.Clear;
end;initialization
    for i := 0 to nBound-1 do
    begin
        nA[i] :=0; nB[i] := -1;
    end;
    nA[0] := 1;
end.
结果是：
数据序列是：
1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631
差是：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,35

zyc(zir)
谢谢参与,不过你还是没有看清题目,我已经说了好多次.
任意两个数的差均不同1,2,4,7,.....4-1=3=7-4

to sharonyym(跑起来！！！)，生气会伤身体，不要生气，只要加油！:)

调试易

高分解决大难题!(200)

解决方案 »