#50: 解題報告:影分身之術


810848 (路過)

School : 一中
ID : 96
IP address : [162.158.119.113]
Last Login :
2021-04-17 17:30:36
c034. ix.影分身之術$(Multiply)$ -- 臺中一中電腦資訊研習社 | From: [162.158.119.227] | Post Date : 2021-01-08 18:32

經典的遞迴題呢~這種很漂亮的東西叫做「碎形」,很酷吧?

 

總之,這種會上下左右增長的東西從上到下、左到右挺不容易的,最好的方法就是我們先做一個二維陣列S,然後先算好哪個位置有人,就把S的那個位置=1,否則=0,最後雙層for迴圈輸出即可。

 

現在有一些問題,我們來一一解決:

1. S大小要設多少?

你可以發現每次分身都會往左/上跟往右/下複製一次,陣型大小就變成3倍,所以可見S的大小就是邊長$ 3^{n} $ 的方陣。

 

2. 怎麼算呢?

好問題!(X

想像我們有一個函式$ f(x,y,i) $可以幫我們在S中畫出以$ (x,y) $為左上角,分身過i次的陣型。

那我們要怎麼借助這個函式完成我們的f呢?

其實你可以發現答案很明顯:你如果仔細看一下分裂i次後陣型的模樣,應該會長這樣。

   (空地)    (分裂i-1次)     (空地)

(分裂i-1次) (分裂i-1次) (分裂i-1次)

   (空地)    (分裂i-1次)     (空地)

 

而這九個區域的大小應該恰為 $3^{i-1}$

所以你只要繪製(呼叫函式):$ f(x,y+3^{i-1},i-1) , f(x+3^{i-1},y,i-1) , f(x+3^{i-1},y+3^{i-1},i-1) , f(x+2*3^{i-1},y+3^{i-1},i-1) , f(x+3^{i-1},y+2*3^{i-1},i-1) $

就可以繪製出$ f(x,y,i) $囉~思考一下吧

而當i = 0時,把S(x,y) = 1即可(終止條件)

所以在主函式中呼叫f(0,0,n)即可完成繪製。

 

3.等等...為甚麼有點怪怪的?寫不出來?

如果是使用C++的同學,可能會遇到不少困難,因為C++不讓你把二維陣列當參數,除非你把他的維度設成常數。

所以這裡可使用一個技巧:我們直接開一個足夠大的陣列,放到全域變數中,因為是全域變數所以不用設成參數也可以修改他。而大小要多大呢?N = 0~6,所以 1000*1000應該綽綽有餘。

但是記得輸出還是輸出左上角的$ 3^{n} $方陣就好了。

 

 

本題稍微有點麻煩,卻挺有趣的吧~

 
ZeroJudge Forum