almost 3 years ago

0 緣起

接下來這幾篇,筆者想要提出來與大家一起討論的,是一系列經典的「遞迴結構問題」。遞迴與自相似性質、分而治之與二分搜尋法等等其實都有某種程度的關聯。擁有了遞迴腦袋,把問題與子問題分離清楚,解題寫 code 的時候就會輕鬆許多。這一系列預計包含摺紙條問題、河內塔問題、Gray Code 問題等。

讓我們先從摺紙條問題開始吧!

註:我們把「摺紙問題」(Origami)留給計算幾何的時候使用吧!我們把今天要討論的問題定義為「摺紙條問題」(Paper Folding)

1 經典的紙條結構

最經典的問題莫過於 UVa 177 - Paper Folding 了吧!把一張紙條,向左對摺、再向左對摺、再對摺…總共 次,然後全部展開,把每一個角都折成 90 度以後,我們查看側面會得到一個形狀。請你把這個形狀以純文字的方式繪製出來,並在最後一列之後加上一個 ^ 符號表示結尾。

紙條序列(Paper Folding Sequence)

我們發現,每一次打開一個褶痕,就會轉 90 度。由於我們永遠向同一邊折,所以這個褶痕打開的時候也都會是往同一邊,我們不妨假設就通通都往左邊吧!

於是我們沿著其中一端,記錄下紙條前進的順序依次是「左轉 」還是「右轉 」:

在轉折點的前後,其實整個紙條的形狀會是完全相同的(只是向左轉了九十度把紙條打開)。所以我們可以得知,整個摺紙序列正中間是一個「左轉 」,然後,序列的後半段,就相當於逆著方向從原來的紙條末端走回開頭,即:原本左轉變成右轉、右轉變成左轉、而且序列的順序是反過來的:

因此我們可以得到遞迴關係:

想知道更多的話可以參考維基百科 Regular Paperfolding Sequence

有了「紙條序列」的定義之後,我們就可以發現:只要將摺紙序列產生出來,再依照這個序列把整條紙帶的方法畫再一個 2D array 上面,就可以解決 UVa 177 的題目了。

2 紙條與搜索範圍

我們來考慮以下的題目 PA2011 Round 4 - Plotter。題目簡述如下:考慮路徑序列 ,產生方式為:一開始 ,然後每一次把原有的序列「撐開」:若原本長度為 序列為 ,那麼新的序列會變成 然後我們把問號的地方依序交錯填入 ,得到

拜特阿瑟(波蘭OI界的靈魂人物,永遠住在拜特蘭 Byteland 的拜特阿瑟 Byteasar,總是能夠想出各種漂亮的程式題目)決定用路徑序列 畫出一條 拜特曲線:在座標平面上從 點出發,一開始往 方向前進,每一步都跨了 單位長的距離,接著根據路徑序列的順序依序左轉、或右轉,然後走完整條路。

現在給你 個座標,對於每一個座標 ,請你回答拜特阿瑟畫出來的曲線上的哪些步會恰好踏到這個座標點上?(;座標範圍

觀察

我們可以按照定義寫出前幾個序列,沒想到竟然跟摺紙序列一模一樣!──是不太意外啦,畢竟都放在同一篇文章了(笑)從這個序列的定義方式,有別於每一次展開一個褶痕,我們可以找出另一種構造紙條序列的方法,如下圖所示:

題解

當然,題解跟上面這個觀察其實沒有太大的關係,主要的觀察還是紙條序列可以用最早的方法產生出來。因此我們可以採用倍增法,維護 這個摺紙序列畫出來以後的可能踏到的座標範圍 ,如果 這個點落在 後半段,那我們把後半段紙條視為「原本紙條的逆序」計算出該點相對於這半部紙條的位置,再遞迴下去找實際的步數。

由於座標範圍只有 ,因此稍作觀察以後(為什麼!)可以得出其實我們只要考慮 就可以了的結論。

參考程式碼

請參考 https://gist.github.com/19b4985ee001b6fc90ba

延伸練習

PA2011 Round 5 - Trails:這題比前一題更複雜一點點,但是方法應該是類似的。歡迎大家一起討論怎麼實作會更理想與簡潔!

第三種定義

在上面的練習題中,作者對於紙條序列給出了第三個直接的定義:若 可以被表示成 的形式,其中 都是整數,那麼整個序列第 個位置便是 否則就是 。有趣吧!

3 後記

那個…如果圖片有奇怪的小錯誤就請大家自由忽略吧!真的很不好意思 ( ̄▽ ̄#)﹏﹏

← 分而治之法(五):L形鋪磚問題 分而治之法(七):河內塔問題 →
 
comments powered by Disqus