帖子: 186
主題: 6
精華: 0
積分: 218
點名: 0
作業系統: win7
軟體版本: office 2007
閱讀權限: 20
性別: 男
註冊時間: 2012-11-12
最後登錄: 2014-4-15

1^# 跳轉到 » 倒序看帖

字體大小: tT

發表於 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函數，所以刻意挑這個例子)

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)

樓主熱帖

Bodhidharma

中學生 Rank: 2

帖子: 186
主題: 6
精華: 0
積分: 218
點名: 0
作業系統: win7
軟體版本: office 2007
閱讀權限: 20
性別: 男
註冊時間: 2012-11-12
最後登錄: 2014-4-15

2^#

發表於 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)

TOP

ML089

版主 Rank: 7 Rank: 7 Rank: 7

帖子: 2025
主題: 13
精華: 0
積分: 2053
點名: 0
作業系統: WIN7
軟體版本: Office2007
閱讀權限: 100
性別: 男
來自: 台北市
註冊時間: 2011-3-2
最後登錄: 2024-3-14

論壇榮譽勳章論壇贊助勳章熱烈參與勳章 2014馬年全勤獎章 2015羊年全勤獎章 2016猴年全勤獎章

3^#

發表於 2013-4-10 10:24 | 只看該作者

回復 2# Bodhidharma

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

{...} 表示需要用 CTRL+SHIFT+ENTER 三鍵輸入公式

TOP

Bodhidharma

中學生 Rank: 2

帖子: 186
主題: 6
精華: 0
積分: 218
點名: 0
作業系統: win7
軟體版本: office 2007
閱讀權限: 20
性別: 男
註冊時間: 2012-11-12
最後登錄: 2014-4-15

4^#

發表於 2013-4-10 19:05 | 只看該作者

回復 Bodhidharma

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

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

TOP

Hsieh

超級版主 Rank: 8 Rank: 8

帖子: 4901
主題: 44
精華: 24
積分: 4916
點名: 239
作業系統: Windows 7
軟體版本: Office 20xx
閱讀權限: 150
性別: 男
來自: 台北
註冊時間: 2010-4-30
最後登錄: 2024-11-4

2023年全勤獎章 2022虎年全勤獎章 2021牛年全勤獎章 2020鼠年全勤獎章 2019 豬年全勤獎章 2018 狗年全勤獎章 2017 雞年全勤獎章 2016猴年全勤獎章 2015羊年全勤獎章 2014馬年全勤獎章 2013蛇年全勤獎章 2012龍年全勤獎章論壇貢獻勳章熱心公益勳章 2011兔年全勤獎章

5^#

發表於 2013-4-10 19:23 | 只看該作者

回復 2# Bodhidharma

試試看動態範圍與遞增範圍加總陣列

maximum subarray.rar (7.79 KB)

學海無涯_不恥下問

TOP

ML089

版主 Rank: 7 Rank: 7 Rank: 7

帖子: 2025
主題: 13
精華: 0
積分: 2053
點名: 0
作業系統: WIN7
軟體版本: Office2007
閱讀權限: 100
性別: 男
來自: 台北市
註冊時間: 2011-3-2
最後登錄: 2024-3-14

論壇榮譽勳章論壇贊助勳章熱烈參與勳章 2014馬年全勤獎章 2015羊年全勤獎章 2016猴年全勤獎章

6^#

發表於 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())))))
三鍵輸入

{...} 表示需要用 CTRL+SHIFT+ENTER 三鍵輸入公式

TOP

Bodhidharma

中學生 Rank: 2

帖子: 186
主題: 6
精華: 0
積分: 218
點名: 0
作業系統: win7
軟體版本: office 2007
閱讀權限: 20
性別: 男
註冊時間: 2012-11-12
最後登錄: 2014-4-15

7^#

發表於 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),))))))))

TOP

Bodhidharma