給定一串實數序列,就是有n個實數.正負不一定.n>=1.
這n個實數為X1,X2,X3,...,Xn.
設計一個演算法來找一段連續的數字.(位於這n個實數中.)
Xi,Xi+1,...,Xj
這段連續的實數在所有可能性中必須是加起來的和為最大.
而這段數字的長度j-i+1必須小於L
L定義為一個整數,1<=L<=n
設計出來的演算法必須在nL的時間內完成....
could someone help me?
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.115.232.66
> -------------------------------------------------------------------------- <
作者: hiei81 (風。起的時候) 看板: puzzle
標題: Re: 可否幫我想想這問題...
時間: Fri Nov 23 02:22:55 2001
※ 引述《dophine (^^)》之銘言：
: 給定一串實數序列,就是有n個實數.正負不一定.n>=1.
: 這n個實數為X1,X2,X3,...,Xn.
: 設計一個演算法來找一段連續的數字.(位於這n個實數中.)
: Xi,Xi+1,...,Xj
: 這段連續的實數在所有可能性中必須是加起來的和為最大.
: 而這段數字的長度j-i+1必須小於L
: L定義為一個整數,1<=L<=n
: 設計出來的演算法必須在nL的時間內完成....
: could someone help me?
有一個簡單的做法，
建立一陣列Yi=X1+X2+...+Xi
那麼連續的實數和，如Xi+...+Xj = Yj-Y(i-1)
用個迴圈跑就是了...以下為C++ code
max=x[1];
y[0]=0;
y[1]=x[1]; //初始化
for(i=2;i<=n;i++)
y[i]=y[i-1]+x[i]; //計算y[i]
for(i=1;i<=n-L+1;i++)
for(j=i;j<i+L;j++) //比較出最大的和
if(max<y[j]-y[i-1])
max=y[j]-y[i-1];
return max; // max即為所求
時間複雜度: 兩層迴圈,i跑至多n個,j跑L個, 故會在nL時間內完成...
此外，有更快的方法，可以在O(n)的時間內跑出來。
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.18.71
> -------------------------------------------------------------------------- <
作者: dophine (^^) 看板: puzzle
標題: Re: 可否幫我想想這問題...
時間: Fri Nov 23 11:42:40 2001
不不不...這段連續的實數長度不一定是L
可能L-1,L-2...會讓實數和更大....
所以要考慮所有可能性.
妳的演算法似乎只有考慮L的長度.
不過還是謝謝你
※ 引述《hiei81 (風。起的時候)》之銘言：
: ※ 引述《dophine (^^)》之銘言：
: : 給定一串實數序列,就是有n個實數.正負不一定.n>=1.
: : 這n個實數為X1,X2,X3,...,Xn.
: : 設計一個演算法來找一段連續的數字.(位於這n個實數中.)
: : Xi,Xi+1,...,Xj
: : 這段連續的實數在所有可能性中必須是加起來的和為最大.
: : 而這段數字的長度j-i+1必須小於L
: : L定義為一個整數,1<=L<=n
: : 設計出來的演算法必須在nL的時間內完成....
: : could someone help me?
: 有一個簡單的做法，
: 建立一陣列Yi=X1+X2+...+Xi
: 那麼連續的實數和，如Xi+...+Xj = Yj-Y(i-1)
: 用個迴圈跑就是了...以下為C++ code
: max=x[1];
: y[0]=0;
: y[1]=x[1]; //初始化
: for(i=2;i<=n;i++)
: y[i]=y[i-1]+x[i]; //計算y[i]
: for(i=1;i<=n-L+1;i++)
: for(j=i;j<i+L;j++) //比較出最大的和
: if(max<y[j]-y[i-1])
: max=y[j]-y[i-1];
: return max; // max即為所求
: 時間複雜度: 兩層迴圈,i跑至多n個,j跑L個, 故會在nL時間內完成...
: 此外，有更快的方法，可以在O(n)的時間內跑出來。
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.115.232.66
> -------------------------------------------------------------------------- <
作者: eieio (披小姐亂七八糟) 看板: puzzle
標題: Re: 可否幫我想想這問題...
時間: Fri Nov 23 14:25:58 2001
※ 引述《hiei81 (風。起的時候)》之銘言：
: ※ 引述《dophine (^^)》之銘言：
: : 給定一串實數序列,就是有n個實數.正負不一定.n>=1.
: : 這n個實數為X1,X2,X3,...,Xn.
: : 設計一個演算法來找一段連續的數字.(位於這n個實數中.)
: : Xi,Xi+1,...,Xj
: : 這段連續的實數在所有可能性中必須是加起來的和為最大.
: : 而這段數字的長度j-i+1必須小於L
: : L定義為一個整數,1<=L<=n
: : 設計出來的演算法必須在nL的時間內完成....
: : could someone help me?
: 有一個簡單的做法，
: 建立一陣列Yi=X1+X2+...+Xi
: 那麼連續的實數和，如Xi+...+Xj = Yj-Y(i-1)
: 用個迴圈跑就是了...以下為C++ code
: max=x[1];
: y[0]=0;
: y[1]=x[1]; //初始化
: for(i=2;i<=n;i++)
: y[i]=y[i-1]+x[i]; //計算y[i]
: for(i=1;i<=n-L+1;i++)
^^^^^^^^ 是不是 i <= n ??
: for(j=i;j<i+L;j++) //比較出最大的和
^^^^^ (j<i+L) && (j<=n)
: if(max<y[j]-y[i-1])
: max=y[j]-y[i-1];
: return max; // max即為所求
好像是這樣吧，不然給 -1, -1, -1, -1, -1, -1, 100
n=7, L=3 大概就會算成 max = 98 了（應該是 100） ^^
--
引用橋牌狂人 eieio 的名言：
7NT 是束叫
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.30.122