Programming Practice

一個 n´n 的帶狀矩陣 (banded matrix) 包含下角和上三角帶狀區,帶寬 (bandwidth) r 的下三角帶狀區即是緊鄰正對角線 (diagonal) 之下的 r 條斜線的元素,帶寬為 s 的上三角帶狀區即是緊鄰正對角線 (diagonal) 之上的 s 條斜線的元素。一個 n´n 的帶狀矩陣只有下三角帶狀區、上三角帶狀區、和正對角線可以有非零的元素,其他的元素皆為零。例如,下列是一個 下三角帶寬為 2,上三角帶寬為 3 的 8´8 矩陣:

A 是一個 n´n 的帶狀矩陣且其下三角和上三角帶寬分別為 rasa,則當 -ra£j-i£sa 時,元素 ai,j 可能是一個非零的元素;其他元素皆為零。若 AB 都是 n´n 的帶狀矩陣,且矩陣 A 的下三角和上三角帶寬分別為 rasa,矩陣 B 的下三角和上三角帶寬分別為 rbsb,則 C=AB 的結果也是一個 n´n 的帶狀矩陣,其下三角和上三角帶寬分別為 ra+rbsa+sb。矩陣 C 的元素可用下列的公式表示:

寫一個 C 語言的程式以執行以下的步驟:

  1. 宣告 AB、和 C  為 100´100 的二維陣列,AABB、和 CC 為二維陣列的指標

  2. 輸入正整數 n 的值 (小於或等於 100);

  3. 輸入帶寬 rasa、rbsb (小於 n 的正整數);

  4. 使用 malloc() 產生 AABB、和 CC 陣列元素的記憶體空間

  5. 使用副程式 rand() 隨機產生矩陣 A B 非零元素的值 (假設AB 元素的值在 1 和 100 之間);同時將 矩陣 A B  複製到矩陣 AA BB

  6. 計算矩陣 CCC 元素的值, C=A´B  CC=AA´BB  (注意:矩陣乘法的程式碼中, AABB、和 CC 陣列元素的索引需要調整)

  7. 每個計算步驟需檢查 CCC 的值是否相同;

  8. 輸出矩陣 AAA、B、BB、C、和 CC (只輸出非零的元素)

  9. 使用 free() 釋放 AABB、和 CC 陣列元素的記憶體空間。

以下為程式執行範例:

Enter matrix size n: 8

Enter the lower bandwidth of matrix A, ra:
2

Enter the upper bandwidth of matrix A, sa:
2

Enter the lower bandwidth of matrix B, rb:
1

Enter the upper bandwidth of matrix B, sb:
1

Matrix A:
     53   45   22
     19   72   56   35
     79   89   91   93    2
          30   79   94   59   94
               53   93   34   15   32
                    36   68   86   96   79
                         90   87   44   54
                              83   70   27

Matrix AA:
     53   45   22
     19   72   56   35
     79   89   91   93    2
          30   79   94   59   94
               53   93   34   15   32
                    36   68   86   96   79
                         90   87   44   54
                              83   70   27

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Matrix B:
     35   18
     81   91   96
          31   98   40
               62   21    7
                    48   14   32
                         65    3   22
                              60   18   97
                                   31    9

Matrix BB:
     35   18
     81   91   96
          31   98   40
               62   21    7
                    48   14   32
                         65    3   22
                              60   18   97
                                   31    9

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Matrix C:
     5500    5731    6476     880
     6497    8630   14570    2975     245
     9974   12342   23228    5689     679      64
     2430    5179   16450    7966    7594    2170    2068
             1643   10960    5705    2102    3053     906    3104
                     2232    4020    6794    8194    6069   10023
                             4320    6915    5781    4380    4754
                                     5395    4449    3923    7033

Matrix CC:
     5500    5731    6476     880
     6497    8630   14570    2975     245
     9974   12342   23228    5689     679      64
     2430    5179   16450    7966    7594    2170    2068
             1643   10960    5705    2102    3053     906    3104
                     2232    4020    6794    8194    6069   10023
                             4320    6915    5781    4380    4754
                                     5395    4449    3923    7033

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

**** The banded matrix mutliplication with dynamic array is correct.