[發問] offset與定義名稱

Bodhidharma

最近在研究定義名稱的原理
因此使用最大子序列(maximum subarray)來作為測試
(參考：http://emn178.pixnet.net/blog/post/88907691)
想要用excel公式來實現Kadane's演算法：
(這個用程式寫很簡單，直接用excel公式就變得超複雜，不過我主要是為了研究定義名稱與offset函數，所以刻意挑這個例子)

下載 (103.71 KB)

2013-4-10 02:00

A欄為input_array，欲計算該array的最大子序列
B欄為模擬Kadane's 演算法

問題1：B欄使用定義名稱tolast就可以正常運作，但是如果不用定義名稱，像G欄tolast的部分就會出錯，想請教差別在哪？
問題2：B欄中有使用offset函數來動態抓取資料，在這種情況下，假設我希望將之變成定義名稱，然後不使用任何輔助欄就能達到D1的效果，想請教要怎麼寫？(最好是A欄的input_array也可以動態取得範圍，不管長度為何都能適用)

maximum subarray.rar (6.94 KB)

下載次數: 7

2013-4-10 02:05

Bodhidharma

回復 1# Bodhidharma

B1換一種寫法：
=SUM(OFFSET($A$1,IFERROR(INDEX(MATCH(2,1/(OFFSET($B$1,,,ROW()-1,)<0)),),0),,ROW()-IFERROR(INDEX(MATCH(2,1/(OFFSET($B$1,,,ROW()-1,)<0)),),0),))
用index(match(2,1/tolast<0),)取代{LARGE(IF(tolast<0,ROW(tolast),""),1)}的陣列公式 (note:奇怪我當初幹麻不用max要用large...)
這樣子的話，不過用tolast或(OFFSET($B$1,,,ROW()-1,)都可以了
所以看起來是陣列公式的問題？ 不過還是搞不懂是什麼原理…

不過即使這樣改，我還是不知道如何將這種DP的東西寫成一個式子(D1)

ML089

回復 2# Bodhidharma


    B1可用下式替代
=SUBTOTAL(9,OFFSET(A$1,,,ROW()))

Bodhidharma

回復  Bodhidharma


    B1可用下式替代
=SUBTOTAL(9,OFFSET(A$1,,,ROW()))
ML089 發表於 2013-4-10 10:24

啊，這樣會有什麼差別嗎？

Hsieh

回復 2# Bodhidharma

試試看動態範圍與遞增範圍加總陣列
    maximum subarray.rar (7.79 KB)

下載次數: 8

2013-4-10 19:22

ML089

啊，這樣會有什麼差別嗎？
Bodhidharma 發表於 2013-4-10 19:05

    那公式是模擬你原先的 B1公式

下式是模擬 超版 的 B1公式
=MAX(SUBTOTAL(9,OFFSET(A$1,ROW()-1,,-ROW(INDIRECT("1:"&ROW())))))
三鍵輸入

Bodhidharma

回復 6# ML089

=MAX(SUBTOTAL(9,OFFSET(A$1,ROW()-1,,-ROW(INDIRECT("1:"&ROW())))))
基本上是http://emn178.pixnet.net/blog/post/88907691中的「改良式暴力法」
也就是第一列回傳A1中最大的
第二列回傳{A1:A2,A2}最大的
第三列回傳{A1:A3,A2:A3,A3}最大的
第n列回傳{A1:An,A2:An,...An-1:An}中最大的
然後再取這n列最大的，即是「最大子序列」

這雖然不是Kadane's演算法，但是結果會一樣
(而且因為excel沒有辦法直接設變數，所以我用很詭異的方式模擬的Kadane's演算法，因此時間複雜度也不會比較好)

我的(原文中第二個)問題是：如何不使用這個補助列，直接得出最大子序列？
把你的公式中的row()改成row(offset($A$A,,,counta(A:A),))，也不對…
=MAX(MAX(SUBTOTAL(9,OFFSET(A$1,ROW(offset($A$A,,,counta(A:A),))-1,,-ROW(INDIRECT("1:"&ROW(offset($A$A,,,counta(A:A),))))))))

Bodhidharma

回復 5# Hsieh

這個只處理到A1:{A2,A3...An}中最大的子序列
沒有處理A2:{A3,A4...An},A3:{A4,A5,...An}...的最大子序列

ML089

回復  ML089

=MAX(SUBTOTAL(9,OFFSET(A$1,ROW()-1,,-ROW(INDIRECT("1:"&ROW())))))
基本上是http://em ...
Bodhidharma 發表於 2013-4-10 23:34

公式有8圈的限制，太多判斷不利於公式發展，暴力法是陣列公式最常用的方法
Kadane's演算法我還沒有時間看，等到周未有時間再來研究