圖說演算法使用JavaScript(七)

全方位應用的陣列與串列演算法

5-1-1矩陣相加

請設計一程式來宣告3個二維陣列,來實作2個矩陣相加的過程,並顯示兩矩陣相加後的結果。

JS          matrix_add.js

var A = new Array();
var B = new Array();
var C = new Array();

for (let i=0; i<3; i++){
	A[i]=new Array();
	B[i]=new Array();
	C[i]=new Array();
}

A= [[1,3,5],[7,9,11],[13,15,17]];
B= [[9,8,7],[6,5,4],[3,2,1]];

N=3;
for (let i=0;i<3; i++){
	for (let j=0; j<3; j++){
		C[i][j]=A[i][j]+B[i][j];
	}
}
console.log("[矩陣A和矩陣B相加的結果]");
let str='';
for (let i=0; i<3; i++){
	for (let j=0; j<3; j++){
		str=str+C[i][j]+'\t';
	}
	str=str+'\n';
}
console.log(str);

PHP         matrix_add.php


$A_arr=array(array(1,3,5),array(7,9,11),array(13,15,17));
$B_arr=array(array(9,8,7),array(6,5,4),array(3,2,1));
$C_arr=array();
for ($i=0; $i<count($A_arr); $i++){
	 for($j=0; $j<count($A_arr);$j++){
	 	$C_arr[$i][$j] = $A_arr[$i][$j] + $B_arr[$i][$j];
	 }
}
print_r($C_arr);
echo "<br><hr><br>";
foreach ($C_arr as $item ){
     echo "[";
     $t=1;
     foreach ($item as $value){
      if($t<3)  echo $value.",";
      else echo $value; 
        $t++;
			}
     echo "]<br>";
}

函式說明


foreach ($arr as $yourstr){
echo $yourstr //$yourstr => $arr or $value
}

5-1-2矩陣相乘

如果談到兩個矩陣A與B的相乘,是有某些條件限制。首先必須符合A為一個m*n的矩陣,B為一個n*p的矩陣,對A*B之後的結果為一個m*p的矩陣C。

範例:
請設計一程式來實作下列兩個矩陣的相乘結果。

JS       matrix_multiply.js

const M=2;
const N=3;
const P=2;
A=[6,3,5,8,9,7];
B=[5,10,14,7,6,8];
C=[0,0,0,0];
if (M<=0 || N<=0 || P<=0) console.log('[錯誤:維數M,N,P必須大於0]');
for (let i=0; i<M; i++){
	for (let j=0; j<P; j++){
		let Temp=0;
	for (let k=0; k<N; k++) Temp = Temp +parseInt(A[i*N+k])*parseInt(B[k*P+j]);
			C[i*P+j] = Temp;
  }
}
console.log('[AxB的結果是]');
let str='';
for (i=0; i<M; i++){
	for (j=0; j<P; j++){
		str = str+C[i*P+j]+ '\t';
	}
	str = str+'\n';
}
console.log(str);

PHP            matrix_multiply.php

$a_arr = array(array(6,3,5),array(8,9,7));
$b_arr = array(array(5,10),array(14,7),array(6,8));

$a_m = count($a_arr);    //陣列 M列
$a_n = count($a_arr[0]); //陣列 N行

$b_n = count($b_arr);    //陣列 N列
$b_p = count($b_arr[0]); //陣列 P行

$c_arr = array();
if ($a_m <=0 || $a_n <=0 || $b_n<=0 || $b_p<=0 || $a_n!=$b_n){
  echo "條件錯誤";
}
    
//echo "a_m=".$a_m."; a_n=".$a_n."<br>";
//echo "b_n=".$b_n."; b_p=".$b_p."<br>";

for ($i=0 ; $i<$a_m; $i++){
    for ($j=0; $j<$b_p; $j++){
      $temp=0;
     for ($k=0 ; $k<$a_n; $k++){
         $temp = $temp + intval($a_arr[$i][$k])*intval($b_arr[$k][$j]);
         //echo $temp."<br>";
         $c_arr[$i][$j]=$temp;
      }
         //echo $temp."<br>";
   }
    //echo "--<br>";
}
print_r($c_arr);

5-1-3轉置矩陣
「轉置矩陣」At就是把原矩陣的行座標元素相互調換,假設At為A的轉置矩陣,則有At[j,i]=[i,j],如下圖所示:

範例

    請設計一程式來實作一4*4二微陣列的轉置矩陣。

JS          transpose.js

arrA=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]];
N=4;
arrB=[[],[],[],[]];
console.log('原設定的矩陣內容');
for (i=0; i<4; i++){
	str = '';
	for (j=0; j<4; j++){
		str= str+arrA[i][j]+'\t';
	}
	console.log(str);
}

for(i=0; i<4; i++){
	for(j=0; j<4; j++){
		arrB[i][j]=arrA[j][i];
	}
}
console.log('[轉置矩陣的內容為]');
for (i=0; i<4; i++){
	str = '';
	for (j=0; j<4; j++){
		str= str+arrB[i][j]+'\t';
	}
	console.log(str);
}

PHP          transpose.php

$a_arr = array(array(1,2,3,4),array(5,6,7,8),array(9,10,11,12),array(13,14,15,16));
$b_arr = array();

$arr_m = count($a_arr);
$arr_n = count($a_arr[0]);

echo "M-".$arr_m."N-".$arr_n."<br>";

for ($i=0; $i<$arr_m; $i++){
  for($j=0; $j<$arr_n; $j++){
      $b_arr[$i][$j]=$a_arr[$j][$i];
  }
}

foreach($a_arr as $item){
   foreach ($item as $value){
    echo $value."   ";
   }
   echo "<br>";
}

foreach($b_arr as $item){
   foreach ($item as $value){
    echo $value."   ";
   }
   echo "<br>";
}
5-1-4 稀疏矩陣
稀疏矩陣最簡單的定義就是一個矩陣中大部分的元素為0,即可稱為「稀疏矩陣」Sparse Matrix。例如下列的矩陣就是典型的稀疏矩陣。
當然如果直接使用傳統的二維陣列來儲存上圖的稀疏矩陣也是可以,但事實上許多元素都是0。這樣的做法在矩陣很大時的稀疏矩陣,就會十分浪費記憶體空間。而改進空間的方法就是利用三項式(3-tuple)的資料結構。我們把每一個非零項目以(i,j,item-value)來表示。更詳細的形容,就是假如一個稀疏矩陣有n個非零項目,那麼可以利用一個A(0:n,1:3)的二維陣列來表示。
其中A(0,1)代表此稀疏矩陣的列數,A(0,2)代表此稀疏矩陣的行數,而A(0,3)則是此稀疏矩陣非零項目的總數。另外每一個非零項目以(i,j,item-value)來表示。其中i為此非零項目所在的列數,j為此非零項目所在行數,item-value則此分零項的值。以上圖6*6稀疏矩陣為例,則可以以下表示:
A(0,1)=>表示此舉矩陣的列數。
A(0,2)=>表示此舉矩陣的行數。
A(0,3)=>表示此舉矩陣非零項目的總數。
這種利用3項式(3-tuple)資料結構來壓縮稀疏矩陣,可以減少記憶體不必要的浪費。

JS          sparse.js

var NONZERO=0;
temp=1;
Sparse=[[15,0,0,22,0,-15],[0,11,3,0,0,0],
        [0,0,0,-6,0,0],[0,0,0,0,0,0],
        [91,0,0,0,0,0],[0,0,28,0,0,0]];//宣告稀疏矩陣,稀疏矩陣的所有元素設為0
str='';
console.log('[稀疏矩陣的各個元素]');
for (i=0;i<6;i++) {
   for(j=0;j<6;j++){
      process.stdout.write(Sparse[i][j]+'\t');
      if (Sparse[i][j]!=0) NONZERO=NONZERO+1;
   }
   console.log();
}

Compress=new Array();   //宣告壓縮陣列
for (let i=0; i<NONZERO+1; i++) Compress[i]=[];

//開始壓縮稀疏矩陣
Compress[0][0]=6;
Compress[0][1]=6;
Compress[0][2]= NONZERO;

for (i=0; i<6; i++){
   for (j=0; j<6; j++){
      if (Sparse[i][j]!=0){
         Compress[temp][0]=i;
         Compress[temp][1]=j;
         Compress[temp][2]=Sparse[i][j];
         temp=temp+1;
      }
   }
}
console.log('[稀疏矩陣壓縮後的內容]');//印出壓縮矩陣
for (i=0; i<NONZERO+1;i++){
   for (j=0; j<3; j++){
      process.stdout.write(Compress[i][j]+'\t');
   }
   console.log();
}

PHP            sparse.php

$sparse=array(array(15,0,0,22,0,-15),array(0,11,3,0,0,0),
              array(0,0,0,-6,0,0),array(0,0,0,0,0,0,0),
              array(91,0,0,0,0,0),array(0,0,28,0,0,0));
$M = count($sparse);
$N = count($sparse[0]);
$nonzero=0;//計算沒有為零的數量
$temp=1;
$compress=array();

for ($i=0; $i<$N; $i++){
  for($j=0; $j<$N; $j++){
    if ($sparse[$i][$j]!=0)
      $nonzero=$nonzero+1;
  }
}
echo "原始陣列"."<br>";
foreach ($sparse as $key => $item) {
    foreach($item as $list => $value){
      echo $value."   ";
    }
      echo "<br>";
}

$compress[0][0]=$M;
$compress[0][1]=$N;
$compress[0][2]=$nonzero;

for($i=0; $i<$N; $i++){
  for($j=0; $j<$M; $j++){
    if ($sparse[$i][$j]!=0){
      $compress[$temp][0]=$i;
      $compress[$temp][1]=$j;
      $compress[$temp][2]=$sparse[$i][$j];
      $temp=$temp+1;
    }
  }
}
echo "壓縮後的陣列<br>";

foreach ($compress as $key => $item) {
    foreach($item as $list => $value){
      echo $value."   ";
    }
      echo "<br>";
}