C语言输出特殊N*N蛇形矩阵?

问题描述

问 题

图是要求的输出范例
程序要求输入一个大于等于5的奇数n
然后输出一个和示例图类似的特殊蛇形矩阵 中心是0然后向外展开
要求是不能用数组和stdio.h以外的lib
已经想了整整一下午了 完全没有任何思路.
求大神帮帮忙想一下思路,不用写代码,帮忙想想思路就行.

解决方案

P.S. 若覺得我的答案不佳或是有誤還請不吝指教, 光是給負分無法讓答案精進, 謝謝

改寫了代碼, 不使用數組

---

思路:

最大的關鍵是找出規則, 首先我們來算出 n 階蛇行矩陣要使用多少的 digit (from 0-9):

我們觀察規則:

(示意圖) 5 階蛇行矩陣需要使用 5+4+4+2+2 個數字

       5
     ----->

     65432
  ^  ----1  |
2 |  210-0  | 4
  |  3---9  |
     45678  |
            v
    <----
       4

• 5*5 矩陣共填入 5+4+4+2+2 個數字

  • 5: first row 右行

  • 4: last col 下行

  • 4: last row 左行

  • 2: first col 上行

  • 2: third row 右行

• 7*7 矩陣共填入 7+6+6+4+4+2+2 個數字

• ...

導出:

total
    = n + 2*(n-1-2*0) + 2*(n-1-2*1) + ... 2*(n-1-2*((n-1)/2-1))
      (中間的級數運算就省略)
    = (n^2+2n-1)/2 個數字

比如說我們得出 5 階矩陣要填入 17 個數字, 那 0, 0 位置要填入的值為第 16 個數字(從 0 開始算):

65432109876543210
^               ^
第 16 個數字     第 0 個數字

16%10 = 6

所以說 n 階矩陣的第 c 個數字的值為:

c%10

有了上述認知之後, 我們來討論如何找出矩陣中 i, j 位置的元素是第幾個要填入的值, 方法很簡單, 我們試著從頭開始繞行, 等到繞行到該位置時去檢查這是輪到第幾個應填入的數字

模擬繞行的過程可以簡單表示為:

• 首先算出應填入數字數量 C, 我們繞行時會從第 C-1 個數字開始填

1. 從 first row 開始向右行走 n 個位置, 每個位置分別對應前 n 個應填入的數字 (c = C-1 ~ c = C-1-n)

   1. 如果中間有經過位置 i, j 則確認位置 i, j 應填入第 c 個數字, 值為 c%10 <stop>

   2. 如果沒有則需要向右轉開始下行, 設定方向 direction 為 'down', 調整步數 move 為 n-1 <前往 2>

2. 朝 direction 方向前進 move 步, 同時要持續計算, 維持每個位置對應的數字

   1. 如果中間有經過位置 i, j 則確認位置 i, j 應填入第 c 個數字, 值為 c%10 <stop>

   2. 如果沒有則需要向右轉, 根據現有方向設定 direction, 調整步數 move

      1. 如果是第一次走 move 步, 則維持現有步數 <重複 2>

      2. 如果是第二次走 move 步, 則調整步數 move 為 move-2 <前往 2>

3. 如果走到最後發現沒有被走到, 則表示該位置應填入 "-" <stop>

當我們能夠模擬繞行找出每個位置應填入的值之後, 就可以用兩層迴圈遍歷矩陣中所有位置同時印出個位置的值

代碼:

def turn_right(direction):
    if direction=='right':
        direction = 'down'
    elif direction=='down':
        direction = 'left'
    elif direction=='left':
        direction = 'up'
    elif direction=='up':
        direction = 'right'
    return direction
    
def goahead(direction, row, col):
    if direction=='right':
        col += 1
    elif direction=='down':
        row += 1
    elif direction=='left':
        col -= 1
    elif direction=='up':
        row -= 1
    return row, col
        
def compute_position(n, i, j):
    """
    Given  size: n, row index: i, col index: j
    Return element: digit 0-9 or char "-"
    """
    c = (n**2+2*n-1)//2
    row = 0
    col = -1
    move = n
    is_first_row = True
    direction = 'right'
    while move >= 2:
        for _i1 in range(1 if is_first_row else 2):
            for _i2 in range(move):
                c -= 1
                row, col = goahead(direction, row, col)
                if row==i and col==j:
                    return (c%10)
            direction = turn_right(direction)
        move = move - (1 if is_first_row else 2)
        is_first_row = False
    return '-'
    
def decimal_spiral(n):
    for i in range(n):
        for j in range(n):
            print(compute_position(n, i, j), end='')
        print()
        
decimal_spiral(7)

輸出:

876543210
--------9
8765432-8
9-----1-7
0-210-0-6
1-3---9-5
2-45678-4
3-------3
456789012

---

我回答過的問題: Python-QA

这篇关于C语言输出特殊N*N蛇形矩阵?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！