DS-quiz1-2016.pdf

may

1.Given two matrices Am,p and Bp,n, Write procedure(pseudo code) to perform matrix multiplication A* B
給定兩個矩陣 Am,p 和 Bp,n，編寫程式（偽代碼）執行矩陣乘法 A* B

2 Suppose  that an array A[1:4,0:3,2:4] is to be arranged in row-major order, beginning in the memory location 100,and each element of A[i,j] requires 2 units of storage .Identify the first memory location used for each of the following array elements.
(a )A[1,2,2];  (b)A[2,1,3]
假設數組 A[1:4,0:3,2:4] 以行優先順序排列，從內存位置 100 開始，A[i,j] 的每個元素需要 2 個存儲單元. 確定用於以下每個數組元素的第一個記憶體位置。
(a)A[1,2,2]； (b)A[2,1,3]

3.Write a procedure that uses a one-dimensional array A to store the following matrix.
寫一個程序，使用一維數組A來儲存以下矩陣。
a1,1  a1,2  ... a1,n
a2,1 a2,2  ... a2,n
...      ...     ...  ...
am,1 am,2 ... am,n

may

回復 1# may

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int a1, b1, a2, b2;
   
4. int main()
   
5. {
   
6.     cin>>a1>>b1;
   
7.     int arr1[a1][b1];
   
8.     for(int i=0; i<a1; i++)
   
9.         for(int j=0; j<b1; j++)
   
10.             cin>>arr1[i][j];
    
11.     cin>>a2>>b2;
    
12.     int arr2[a2][b2];
    
13.     for(int i=0; i<a2; i++)
    
14.         for(int j=0; j<b2; j++)
    
15.             cin>>arr2[i][j];
    
16.     if(b1!=a2)
    
17.     {
    
18.         cout<<"error"<<endl;
    
19.     }else
    
20.     {
    
21.         for(int i=0; i<a1; i++)
    
22.         {
    
23.             for(int j=0; j<b2; j++)
    
24.             {
    
25.                 int sum=0;
    
26.                 for(int k=0; k<b1; k++)
    
27.                     sum+=arr1[i][k]*arr2[k][j];
    
28.                 if(j!=0)
    
29.                     cout<<" ";
    
30.                 cout<<sum;
    
31.             }
    
32.             cout<<endl;
    
33.         }
    
34.     }
    
35.     return 0;
    
36. }

複製代碼

may

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main(void) {
   
5.     int arr1[3][4] = {{1, 2, 3, 4},
   
6.                               {5, 6, 7, 8},
   
7.                              {9, 10, 11, 12}};
   
8.     int arr2[12] = {0};
   
9.     int row, column, i;
   
10. 
    
11.     printf("原二維資料：\n");
    
12.     for(row = 0; row < 3; row++) {
    
13.         for(column = 0; column < 4; column++) {
    
14.             printf("%4d", arr1[row][column]);
    
15.         }
    
16.         printf("\n");
    
17.     }
    
18. 
    
19.     printf("\n以列為主：");
    
20.     for(row = 0; row < 3; row++) {
    
21.         for(column = 0; column < 4; column++) {
    
22.             i = column + row * 4;
    
23.             arr2[i] = arr1[row][column];
    
24.         }
    
25.     }
    
26.     for(i = 0; i < 12; i++)
    
27.         printf("%d ", arr2[i]);
    
28. 
    
29.     printf("\n以行為主：");
    
30.     for(row = 0; row < 3; row++) {
    
31.         for(column = 0; column < 4; column++) {
    
32.             i = row + column * 3;
    
33.             arr2[i] = arr1[row][column];
    
34.         }
    
35.     }
    
36.     for(i = 0; i < 12; i++)
    
37.         printf("%d ", arr2[i]);
    
38. 
    
39.     printf("\n");
    
40. 
    
41.     return 0;
    
42. }

複製代碼

may

若要按行優先順序計算每個陣列元素使用的第一個記憶體位置，可以使用下列公式：

記憶體位置 = 基址 + (Index1 * Size1 + Index2 * Size2 + Index3 * Size3) * 元素大小

這裡，對於陣列 A[1:4,0:3,2:4]：

Index1 的範圍為 1 到 4，因此 Size1 為 4。
Index2 的範圍是 0 到 3，因此 Size2 是 4。
Index3 的範圍是 2 到 4，因此 Size3 是 3。
元素大小為 2 個儲存單位。
現在，讓我們計算每個元素的記憶體位置：

A[1][0][2]：
索引 1 = 1、索引 2 = 0、索引 3 = 2
記憶體位置 = 100 + (1 * 4 + 0 * 4 + 2 * 3) * 2 = 100 + (4 + 0 + 6) * 2 = 100 + 10 * 2 = 100 + 20 = 120

A[1][0][3]：
索引 1 = 1、索引 2 = 0、索引 3 = 3
記憶體位置 = 100 + (1 * 4 + 0 * 4 + 3 * 3) * 2 = 100 + (4 + 0 + 9) * 2 = 100 + 13 * 2 = 100 + 26 = 126

A[1][1][2]：
索引 1 = 1、索引 2 = 1、索引 3 = 2
記憶體位置 = 100 + (1 * 4 + 1 * 4 + 2 * 3) * 2 = 100 + (4 + 4 + 6) * 2 = 100 + 14 * 2 = 100 + 28 = 128

A[1][1][3]：
索引 1 = 1、索引 2 = 1、索引 3 = 3
記憶體位置 = 100 + (1 * 4 + 1 * 4 + 3 * 3) * 2 = 100 + (4 + 4 + 9) * 2 = 100 + 17 * 2 = 100 + 34 = 134
這些是按行優先順序指定的數組元素的第一個記憶體位置

(a) A[1,2,2]：
索引1 = 1， 索引 2 = 2，索引 3 = 2
記憶體位置 = 100 + (1 * 4 + 2 * 4 + 2 * 3) * 2 = 100 + (4 + 8 + 6) * 2 = 100 + 36 * 2 = 100 + 72 = 172

(b) A[2,1,3]：
索引 1 = 2， 索引 2 = 1， 索引 3 = 3
記憶體位置 = 100 + (2 * 4 + 1 * 4 + 3 * 3) * 2 = 100 + (8 + 4 + 9) * 2 = 100 + 42 * 2 = 100 + 84 = 184