โปรแกรม C พิมพ์เมทริกซ์สปิรัล n×n ใช้พื้นที่ O(1) เพิ่มเติม

โจทย์

กำหนดจำนวนเต็มบวก n สร้างเมทริกซ์ n×k แบบสปิรัล (spiral) ทิศทางเข็มนาฬิกา ใช้พื้นที่เพิ่มเติม O(1) เท่านั้น

ตัวอย่าง

Input: n = 3
Output:
18 16 14
4  2  12
6  8  10

รูปแบบ: เริ่มจากมุมขวาบน (18) หมุนเข็มนาฬิกา ลงซ้าย ลงล่าง ขวา บน...

สูตรคำนวณค่าโดยตรง (ไม่ต้องสร้างเมทริกซ์จริง)

หา layer x = min(i, j, n-1-i, n-1-j) ของเซลล์ (i,j)

• Upper-right half (i ≤ j): value = 2 × ((n-2x)² - (i-x) - (j-x))
• Lower-left half (i > j): value = 2 × ((n-2x-2)² + (i-x) + (j-x))

อัลกอริทึม

1. วนลูป i = 0 ถึง n-1, j = 0 ถึง n-1
2. คำนวณ x = min(i, j, n-1-i, n-1-j)
3. ถ้า i ≤ j ใช้สูตร upper-right, มิฉะนั้น lower-left
4. พิมพ์ค่าทีละเซลล์ ไม่ต้องเก็บเมทริกซ์ทั้งหมด

โค้ดภาษา C

#include <stdio.h>

int spiralmatrix(int n) {
    int i, j, a, b, x;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            a = (i < j ? i : j);
            b = ((n-1-i) < (n-1-j) ? (n-1-i) : (n-1-j));
            x = a < b ? a : b;  // layer
            
            if (i <= j)
                printf("%d\t", 2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)));
            else
                printf("%d\t", 2 * ((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)));
        }
        printf("\n");
    }
    return 0;
}

int main() {
    int n = 3;
    spiralmatrix(n);
    return 0;
}

ผลลัพธ์

18	16	14
4	2	12
6	8	10

ข้อดี: ใช้พื้นที่ O(1) ไม่ต้องจัดสรรเมทริกซ์ n×n คำนวณค่าแต่ละเซลล์โดยตรงจากสูตรคณิตศาสตร์