找出满足指定条件的任一序列

Question

依据条件，只通用穷举，这样，搜索的时间有点长。特别是N>？ 时，更加如此.......

Answer 1

如果只是求出任何一组满足条件的序列，且无额外要求（如不要求最大或最小序列之类）的话，应该可以编程实现的，下面是思路，欢迎拍砖。
对于序列W[i]={w1,w2,...,wN}，令di=wi-w1，
可组成差项列D[i]={d1,d2,...,dN}，（这里d1=0）
现在我们把原题用w1和di重新写一遍，成为：
对于正数N，查找正整数W1和整数序列0=d1<d2<d3<...<dN，使得序列
{w1,w1+d2,w1+d3,...,w1+dN}和矩阵（这里矩阵对角线上的元素可不用考虑，用NA表示它）
-----------------------------------------------------------------------------------
NA            , 2w1+2d1-w1-d2 , 2w1+2d1-w1-d3 , 2w1+2d1-w1-d4 , ... , 2w1+2d1-w1-dN
2w1+2d2-w1-d1 , NA            , 2w1+2d2-w1-d3 , 2w1+2d2-w1-d4 , ... , 2w1+2d2-w1-dN
2w1+2d3-w1-d1 , 2w1+2d3-w1-d2 , NA            , 2w1+2d3-w1-d4 , ... , 2w1+2d3-w1-dN
2w1+2d4-w1-d1 , 2w1+2d4-w1-d2 , 2w1+2d4-w1-d3 , NA            , ... , 2w1+2d4-w1-dN
...
2w1+2dN-w1-d1 , 2w1+2dN-w1-d2 , 2w1+2dN-w1-d3 , 2w1+2dN-w1-d4 , ... , NA
-----------------------------------------------------------------------------------
之间没有重合元素。
另外，根据wN<1.5w1，有w1+dN<1.5w1，即dN<0.5w1 或 w1>2dN。
现在从上面把w1全部减去（反正只要求出dN之后，给个>2dN的值做w1就可以满足条件了）
题目变形为
对于正整数N，查找整数序列0=d1<d2<d3<...<dN，使得序列
{d1,d2,d3,...,dN}和矩阵（这里矩阵对角线上的元素可不用考虑，用NA表示它）
-----------------------------------------------------------------------------------
NA     , 2d1-d2 , 2d1-d3 , 2d1-d4 , ... , 2d1-dN
2d2-d1 , NA     , 2d2-d3 , 2d2-d4 , ... , 2d2-dN
2d3-d1 , 2d3-d2 , NA     , 2d3-d4 , ... , 2d3-dN
2d4-d1 , 2d4-d2 , 2d4-d3 , NA     , ... , 2d4-dN
...
2dN-d1 , 2dN-d2 , 2dN-d3 , 2dN-d4 , ... , NA
-----------------------------------------------------------------------------------
中没有相同元素。也就是说
对于数组{d1,d2,d3,...,dN}而言，要求任何2di-dj不能出现在原来数组里面
这个可以画表格来找出其中的一组解
d, d*2
0,  0
1,  2
3,  6  (不能为2，因为2-2=0已经出现在d里面了，可以为3因为2-3=-1不在d里面)
4,  8  (6-4=2不在d里面，0-4,2-4均不在d里面)
9, 18  (6-5=1, 6-6=0, 8-7=1, 8-8=0都在d里面，因此取9)
10,20  (18-10=8不在d里面)
12,24  (18-11=7在d里面, 18-12=6, 20-12=8均不在d里面)
...
最后求出dN了之后，另w1=dN*2+1就可以推导出W序列的一组解了。这个思路，可以通过2重循环实现，时间复杂度差不多是O(N^3)，空间上需要2个数组（1个放d，一个放d*2，如果存储紧张的话也可以只用一个数组），空间复杂度为O(N)。type
    TIntArray = array of Integer;//check whether a value is allowed in array d
function isValidValue(value: Integer; d, d2: array of Integer; maxIndex: Integer): Boolean;
var
    i, j: Integer;
    v: Integer;
begin
    Result:= true;
    for i:= maxIndex downto 0 do
    begin
        if d2[i]<value then
            exit;
        v:= d2[i]-value;
        for j:= 0 to maxIndex do
        begin
            if d[j]=v then
            begin
                Result:= false;
                exit;
            end ;
        end ;
    end ;
end;//get sequence of w
function getSequence(N: Integer): TIntArray;
var
    d, d2: array of Integer;
    w1: Integer;
    i: Integer;
begin
    setLength(d, N);
    setLength(d2,N);
    d[0]:= 0;
    d2[0]:= d[0]*2;
    for i:= 1 to N-1 do
    begin
        d[i]:= d[i-1]+1;
        while not isValidValue(d[i], d, d2, i-1) do
        begin
            inc(d[i]);
        end;
        d2[i]:= d[i]*2;
    end ;
    setLength(Result, N);
    w1:= d2[N-1]+1;
    for i:= 0 to N-1 do
    begin
        Result[i]:= w1+d[i];
    end ;
    setLength(d,0);
    setLength(d2,0);
end ;

Answer 2

顺便说一下，利用上面的思路，可以很容易的证明对于任意N>1，都存至少1组符合条件的d序列，因此存在无穷多组解。
证明为方法为数学归纳法：假设当N=k时存在符合条件的d={0, d1, d2, ..., dk}，则当N=k+1时，序列{0, d1, d2, ..., dk, dk*2+1)必然满足条件 -- 因为很明显的, dk*2+1 - ds (s<=k)必然大于dk, 而其它任何元素ds*2必然<dk*2+1因此不可能发生重复。根据这个思路的话，如果不介意数字变得过大的话，直接令d[k]=d[k-1]*2+1可以在O(N)的时间内求序列。