圖說演算法使用JavaScript(八)

5-2陣列與多項式

多項式是數學中相當重要的表現方式，通常如果使用電腦來處理多項式的各種相關運算，可以將多項式以陣列Arrray或鏈結串列Linked List來儲存。本節中，我們還是集中討論多項式以陣列結構表示的相關應用。

5-2-1多項式陣列表示法

這個稱為P(x)為一n次多項式，而一個多項式使用陣列結構儲存在電腦中，可以使用兩種模式。

1.使用一個n+2長度的一維陣列存放，陣列的第一個位置儲存最大的指數n，其他位置依照指數n遞減，依序儲存相對應的係數：

使用這種方法的優點就是在電腦中運用時，對於多項式的各種運算(如加法與乘法)較為方便設計。不過如果多項式的係數為多半為零，就顯得太浪費空間了。

2.只儲存多項式中非零項目。如果有m項非零項目，則使用2m+1長的陣列來儲存每一個非零項目的係數及指數，但陣列的第一個元素則為此多項式非零項的個數。

這種方法的優點是可以節省不必要的記憶空間浪費，但缺點則是在多項式各種多項式演算法設計時，會較為複雜許多。

JS            poly_add.js

ITEMS=6;
var PrintPoly=(Poly,items)=>{
  MaxExp=Poly[0];
  for (i=1; i<Poly[0]+2;i++){
    MaxExp=MaxExp-1;
    if (Poly[i]!=0){
      if(MaxExp+1!=0)
        process.stdout.write(Poly[i]+'X^'+(MaxExp+1)+' ');
      else
        process.stdout.write(' '+Poly[i]);
      if (MaxExp>=0)
        process.stdout.write('+');
    }
  }
}
var PolySum=(Poly1,Poly2)=>{
  result=[];
  result[0]=Poly1[0];
  for(i=1;i<Poly1[0]+2;i++){
    result[i]=Poly1[i]+Poly2[i]; //等冪的係數相加
  }
  PrintPoly(result,ITEMS);
}

PolyA=[4,3,7,0,6,2]; //用方法一，降冪方式敘述：3X^4+7X^3+6X+2
PolyB=[4,1,5,2,0,9]; //用降冪方式敘述：X^4+5X^3+2X^2+9
process.stdout.write('多項式A=> ');
PrintPoly(PolyA,ITEMS);
console.log();
process.stdout.write('多項式B=> ');
PrintPoly(PolyB,ITEMS);
console.log();
process.stdout.write('A+B => ');
PolySum(PolyA,PolyB);

PHP           poly_add.php

$ploy_a=array(4,3,7,0,6,2);
$ploy_b=array(4,1,5,2,0,9);

function get_poly ($arr){
  $len=count($arr);
  $maxexp=$arr[0];
  $re_poly="";

  for ($i=1; $i<$arr[0]+2; $i++){
    
    if ($len !=($arr[0]+2)){
      return "多項式格式錯誤";
      break; //檢驗長度
    }
    
    $maxexp=$maxexp-1;
    if ($arr[$i]!=0){
      if(($maxexp+1)!=0)
        $re_poly=$re_poly.$arr[$i]."X^".($maxexp+1)." "; //字串加法
      else 
        $re_poly=$re_poly." ".$arr[$i];
      
      if($maxexp>=0)
        $re_poly=$re_poly."+";
    }
  }

  return $re_poly; 
  //echo $len."-".$maxexp."<br>";
}

function poly_add($arr_a,$arr_b){
   $result=array();
   $result[0]=$arr_a[0];

   for ($i=1; $i<$arr_a[0]+2; $i++){
   
    if ($arr_a[0] !=$arr_b[0]){
      return "多項式長度錯誤";
      break; //兩個是否不同
    }
    
    $result[$i]=$arr_a[$i]+$arr_b[$i];
   }
   return $result;
}

$get_poly_a = get_poly($ploy_a);
$get_poly_b = get_poly($ploy_b);
$get_poly_add = get_poly(poly_add($ploy_a,$ploy_b));

echo $get_poly_a."<br>";
echo $get_poly_b."<br>";
echo $get_poly_add."<br>";

沒有思考到，級數不一樣時的加法。

如：X^5 + 4X^3 +1   跟 X^4 + 5X^3 + 12X + 5