螺旋數列問題

螺旋數列

問題描述:

螺旋矩陣是一個短陣,其中每個cell都填滿整數,且每個整數以螺旋的方式排列。下圖是一個size 為10的螺旋矩陣,數字從1開始往上為2往右為3,以順時針完成。

我們給一個數字p  ( 3 < p < 15 ) ,請你找出size 為p 的螺旋矩陣。接下來再給一個數字m  (0 < m <= p2),請你找出以數字m為中心的3*3矩陣。

Ex : m = 12  輸出

題目所給的m可能會有超出範圍的情形。Ex : m = 100時無法完整輸出矩陣,請輸出“No answer”

輸入說明 :

第一列有一個整數n,代表接下來有n組測試資料 (0 < n <= 5)。每筆測資輸入兩個正整數p ( 3 < p < 15 )、m,中間以一個空白隔開。

輸出說明:

每筆測資輸出一個3*3的矩陣,數字以一個空白隔開,每筆測資輸出間隔一行,最後必須有換行字元。

範例

===============================================

這題我個人的做法是先弄出一個p*p的動態二維陣列,假設p=10,那麼再來判斷p*p也就是100這數字是在最右下角還是左上角,如果p可以被2整除,那就是右下角,反之左上角

再來這題的核心就是如何弄出螺旋矩陣?如果我們把螺旋矩陣的值都填好,剩下的就是收尋m這簡單的工作,螺旋矩陣的方法有很多,我個人的做法如下:

px及py是用來旋轉用的,當p可以整除的時候代表p*p的位置是在右下角,我們可以弄一個迴圈跑賦值的動作

i其實是代表x,j是代表y

假設p=10,我們px=0,py=-1那為什麼要這樣做呢?各位有沒有發現螺旋矩陣有一個特性,當我們要依序往上走的時候只有y會遞減,x不變,走到底之後要開始依序往左走x遞減,y不變,往下走的時候y遞增,x不變,往右走的時候x遞增,y不變。

也就是一定如果x或y是遞增或遞減,那麼另一個x或y一定是不變

那我們從上圖的例題開始跑迴圈,當我們sum到了91之後就要開始轉向了,那麼該怎麼轉呢?在說一次螺旋矩陣的規則往上走的時候只有y會遞減,x不變,走到底之後要開始依序往左走x遞減,y不變,往下走的時候y遞增,x不變,往右走的時候x遞增,y不變。

所以要如何讓程式去判斷當sum到91的時候要往上走、往右走、往下走還是往左走?

這時候就可以用px跟py的值來判斷了,

px=py*1 當py是-1時,-1*1會變成-1,因此px就會開始往左遞減

py=temp*-1當px=0時,0乘任何數字都是0,因此py=0

利用這個方法,可以讓螺旋矩陣正確的轉向,不過還有一個地方要注意,利用

if( i < 0 || i >= p || j < 0 || j >= p )這個方法來判斷轉向會有一個問題,當數值到了65時,他還是會繼續的往右走,因而把本來是100的這個位置給蓋掉變成64,造成整個螺旋矩陣根本只在最外圍賦值,因此還要加上一個條件spriral[i][j]!=0

因此整個大綱大概如下,剩下就只剩題目要尋找的的m,相信各位可以自行完成

 

Leave a Reply

你的電子郵件位址並不會被公開。 必要欄位標記為 *