Board logo

標題: [發問] offset與定義名稱 [打印本頁]
作者: Bodhidharma    時間: 2013-4-10 02:07     標題: offset與定義名稱

本帖最後由 Bodhidharma 於 2013-4-10 02:08 編輯

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

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

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

[attach]14606[/attach]
作者: Bodhidharma    時間: 2013-4-10 03:24

本帖最後由 Bodhidharma 於 2013-4-10 03:27 編輯

回復 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    時間: 2013-4-10 10:24

回復 2# Bodhidharma


    B1可用下式替代
=SUBTOTAL(9,OFFSET(A$1,,,ROW()))
作者: Bodhidharma    時間: 2013-4-10 19:05

回復  Bodhidharma


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


啊，這樣會有什麼差別嗎？
作者: Hsieh    時間: 2013-4-10 19:23

回復 2# Bodhidharma

試試看動態範圍與遞增範圍加總陣列
    [attach]14621[/attach]
作者: ML089    時間: 2013-4-10 19:40

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



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

下式是模擬 超版 的 B1公式
=MAX(SUBTOTAL(9,OFFSET(A$1,ROW()-1,,-ROW(INDIRECT("1:"&ROW())))))
三鍵輸入
作者: Bodhidharma    時間: 2013-4-10 23:34

回復 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    時間: 2013-4-10 23:37

回復 5# Hsieh

這個只處理到A1:{A2,A3...An}中最大的子序列
沒有處理A2:{A3,A4...An},A3:{A4,A5,...An}...的最大子序列
作者: ML089    時間: 2013-4-11 00:36

回復  ML089

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


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



歡迎光臨 麻辣家族討論版版 (http://forum.twbts.com/)