Javaで多項式計算

Table of Contents

1 クラス設計

ここでは,一変数多項式を表すクラスPolynomialを実装することにする.

1.1 メソッド

どのようなメソッドを提供するかを設計する.

  • new Polynomial()
    0 に等しい新しい多項式を生成する.
  • new Polynomial(List<Integer> as)
    リスト as を係数とする新しい多項式を生成する.
  • Polynomial mul(int b)
    定数 b を掛けた新しい多項式を求める.
  • Polynomial add(Polynomial p)
    多項式 p を加えた新しい多項式を求める.
  • Polynomial mul(Polynomial p)
    多項式 p を掛けた新しい多項式を求める.
  • String toString()
    多項式の文字列表現を返す.

定数倍のメソッド名が imul ではなく mul としている点に注意する. Javaでは引数の型が異なれば,同一のメソッド名を使用できる. これは,メソッドの オーバーローディング (多重定義,overloading)と呼ばれる.

1.2 シナリオ

利用のシナリオは以下の通りである.

Polynomial p, q, r;
p = new Polynomial(Arrays.asList(1, -1, 0, 2, -3));
System.out.println(p.mul(2));
p = new Polynomial(Arrays.asList(1, 2, 3));
q = new Polynomial(Arrays.asList(1, -2, 3, -4));
System.out.println(p.add(q));
p = new Polynomial(Arrays.asList(1, 2, 3));
q = new Polynomial(Arrays.asList(1, -2, 3));
System.out.println(p.mul(q));

実行結果としては,以下を想定している.

(2, -2, 0, 4, -6)
(2, 0, 6, -4)
(1, 0, 2, 0, 9)

2 インスタンス変数

係数を覚えておくために,以下のインスタンス変数を用いる.

1:  private List<Integer> as = null;

privateと宣言し,インスタンス変数 as が他クラスから参照できないようにしている.

3 コンストラクタ

コンストラクタは以下の2種類である.

1:  public Polynomial() {
2:    as = new ArrayList<Integer>();
3:  }
4:  
5:  public Polynomial(List<Integer> as) {
6:    this.as = as;
7:  }

this.as は,インスタンス変数の as を表す.

4 定数倍

多項式を定数倍した新しい多項式を求めるメソッド mul は以下のように定義できる.

1:  public Polynomial mul(int b) {
2:    Polynomial r = new Polynomial();
3:    for (int a : as) {
4:      r.as.add(b * a);
5:    }
6:    return r;
7:  }

5 加算

二つの多項式の和になっている新しい多項式を求めるメソッド add を作成する.

 1:  public Polynomial add(Polynomial p) {
 2:    Polynomial r = new Polynomial();
 3:    for (int i = 0; i < as.size() || i < p.as.size(); i++) {
 4:      int a = 0;
 5:      if (i < as.size())
 6:        a += as.get(i);
 7:      if (i < p.as.size())
 8:        a += p.as.get(i);
 9:      r.as.add(a);
10:    }
11:    return r;
12:  }

6 乗算

二つの多項式の積になっている新しい多項式を求めるメソッド mul を作成する.

そのために,まず xn 倍した多項式を求めるメソッド xmul(n) を作成する.

1:  public Polynomial xmul(int n) {
2:    List<Integer> bs = new ArrayList<Integer>(as);
3:    for (int i = 0; i < n; i++)
4:      bs.add(0, 0);
5:    return new Polynomial(bs);
6:  }

new ArrayList で新しいリスト bs を生成し,その先頭に n 個の 0 を追加している.

xmul を用いると mul は以下のように定義できる.

1:  public Polynomial mul(Polynomial p) {
2:    Polynomial r = new Polynomial();
3:    for (int i = 0; i < as.size(); i++) {
4:      Polynomial q = p.mul(as.get(i));
5:      r = r.add(q.xmul(i));
6:    }
7:    return r;
8:  }

7 プログラム全体

プログラム全体は,以下のようになる.

 1:  import java.util.List;
 2:  import java.util.ArrayList;
 3:  import java.util.Arrays;
 4:  
 5:  public class Polynomial {
 6:    private List<Integer> as = null;
 7:  
 8:    public Polynomial() {
 9:      as = new ArrayList<Integer>();
10:    }
11:  
12:    public Polynomial(List<Integer> as) {
13:      this.as = as;
14:    }
15:  
16:    public Polynomial add(Polynomial p) {
17:      Polynomial r = new Polynomial();
18:      for (int i = 0; i < as.size() || i < p.as.size(); i++) {
19:        int a = 0;
20:        if (i < as.size())
21:          a += as.get(i);
22:        if (i < p.as.size())
23:          a += p.as.get(i);
24:        r.as.add(a);
25:      }
26:      return r;
27:    }
28:  
29:    public Polynomial xmul(int n) {
30:      List<Integer> bs = new ArrayList<Integer>(as);
31:      for (int i = 0; i < n; i++)
32:        bs.add(0, 0);
33:      return new Polynomial(bs);
34:    }
35:  
36:    public Polynomial mul(int b) {
37:      Polynomial r = new Polynomial();
38:      for (int a : as) {
39:        r.as.add(b * a);
40:      }
41:      return r;
42:    }
43:  
44:    public Polynomial mul(Polynomial p) {
45:      Polynomial r = new Polynomial();
46:      for (int i = 0; i < as.size(); i++) {
47:        Polynomial q = p.mul(as.get(i));
48:        r = r.add(q.xmul(i));
49:      }
50:      return r;
51:    }
52:  
53:    public String toString() {
54:      String s = "";
55:      String delim = "";
56:      for (int a : as) {
57:        s += delim + a;
58:        delim = ", ";
59:      }
60:      return "(" + s + ")";
61:    }
62:  
63:    public static void main(String[] args) {
64:      Polynomial p, q, r;
65:      p = new Polynomial(Arrays.asList(1, -1, 0, 2, -3));
66:      System.out.println(p.mul(2));
67:      p = new Polynomial(Arrays.asList(1, 2, 3));
68:      q = new Polynomial(Arrays.asList(1, -2, 3, -4));
69:      System.out.println(p.add(q));
70:      p = new Polynomial(Arrays.asList(1, 2, 3));
71:      q = new Polynomial(Arrays.asList(1, -2, 3));
72:      System.out.println(p.mul(q));
73:    }
74:  }

実行結果は,以下のようになる.

(2, -2, 0, 4, -6)
(2, 0, 6, -4)
(1, 0, 2, 0, 9)

8 関数型言語風の記述

以下は,MyListクラスを作成し,Lispと同様にプログラムした例である.

 1:  import java.util.List;
 2:  import java.util.ArrayList;
 3:  import java.util.Arrays;
 4:  
 5:  public class MyList {
 6:    private List<Integer> as;
 7:  
 8:    public MyList() {
 9:      as = new ArrayList<Integer>();
10:    }
11:  
12:    public MyList(List<Integer> as) {
13:      this.as = new ArrayList<Integer>(as);
14:    }
15:  
16:    public boolean isEmpty() {
17:      return as.isEmpty();
18:    }
19:  
20:    public int head() {
21:      return as.get(0);
22:    }
23:  
24:    public MyList tail() {
25:      return new MyList(as.subList(1, as.size()));
26:    }
27:  
28:    public MyList cons(int a) {
29:      List<Integer> as1 = new ArrayList<Integer>(as);
30:      as1.add(0, a);
31:      return new MyList(as1);
32:    }
33:  
34:    public MyList mul(int b) {
35:      if (isEmpty())
36:        return this;
37:      return tail().mul(b).cons(b * head());
38:    }
39:  
40:    public MyList add(MyList ys) {
41:      if (isEmpty())
42:        return ys;
43:      else if (ys.isEmpty())
44:        return this;
45:      return tail().add(ys.tail()).cons(head() + ys.head());
46:    }
47:  
48:    public MyList mul(MyList ys) {
49:      if (isEmpty())
50:        return this;
51:      return ys.mul(head()).add(tail().mul(ys).cons(0));
52:    }
53:  
54:    public String toString() {
55:      String s = "";
56:      String delim = "";
57:      for (int a : as) {
58:        s += delim + a;
59:        delim = ", ";
60:      }
61:      return "(" + s + ")";
62:    }
63:  
64:    public static void main(String[] args) {
65:      MyList p, q, r;
66:      p = new MyList(Arrays.asList(1, -1, 0, 2, -3));
67:      System.out.println(p.mul(2));
68:      p = new MyList(Arrays.asList(1, 2, 3));
69:      q = new MyList(Arrays.asList(1, -2, 3, -4));
70:      System.out.println(p.add(q));
71:      p = new MyList(Arrays.asList(1, 2, 3));
72:      q = new MyList(Arrays.asList(1, -2, 3));
73:      System.out.println(p.mul(q));
74:    }
75:  }

9 練習問題

  1. 二つの多項式の差を求める述語 diff を作成せよ.
  2. 多項式と整数bが与えられた時, 多項式が単項式 x-b で割り切れるかどうか調べる述語 divisible を作成せよ.
  3. 多項式を微分した新しい多項式を求める述語 deriv を作成せよ.

Date: 2017-09-29 21:45:37 JST

Author: 田村直之

Validate XHTML 1.0