uj5u.com熱心網友回復：
好像有點難度的樣子，難道只能窮舉一定范圍？你應該在數學論壇問問有沒有好的演算法，具體實作用什么語言不是大的問題。uj5u.com熱心網友回復：
嗯，謝謝啦，我去數學論壇請教請教uj5u.com熱心網友回復：
依據條件，只通用窮舉，這樣，搜索的時間有點長。特別是N>？ 時，更加如此.......uj5u.com熱心網友回復：
如果只是求出任何一組滿足條件的序列，且無額外要求（如不要求最大或最小序列之類）的話，應該可以編程實作的，下面是思路，歡迎拍磚。對于序列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 ;
uj5u.com熱心網友回復：
uj5u.com熱心網友回復：
順便說一下，利用上面的思路，可以很容易的證明對于任意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)的時間內求序列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/56591.html
標籤：語言基礎/算法/系統設計
上一篇：分組得到每個客戶的第二大值