提出期限　~2003年11月10日
      学籍番号　035735k
      学部学科　工学部情報工学科
      氏名　　　仲松　義嗣 

      問題：アルゴリズムの性能を比較するプログラムを作成し考察せよ。
      一般的な問題に対する強力なアルゴリズムは普通存在しない。
      ここでも具体的な問題に対するアルゴリズムを評価することを目標とした。

1. 問題の定式化

   ここでは整数係数
   an,an-1,...,a1,a0を持つxの
   n次多項式(polynomial in x of degree n)
     f(x)=anxn+an-1xn-1+...+a1x+a0
   があるときに、ある一つの値x=x0においてこのf(x)がとる値
   f(x0)を計算することとした。
   以下では、
     f(x)=4x3+5x2+3x+7
   に対して、x0=2としてf(2)の計算を具体例として用いることにします。
   つまり、n=3で、a3=4,a2=5,a1=3,a0=7とします。
   

2. 処理手順（アルゴリズム）の決定

   
   初等的計算法
   具体例のとき、
   x0=2に対して、4x03と5x02と3x0をそれぞれ以下のように、
   予め計算して記憶しておく。
     S3=a3x03=4x03=4*(2*2*2)=32
     S2=a2x02=5x02=5*(2*2)=20
     S1=a1x0=30=3*(2)=6
   その後で、f(2)を
     f(2)=S3+S2+S1+a0=(32)+(20)+(6)+(7)=65
   と計算する。
   ホーナー法
   ホーナー法では、具体例のとき、
     f(x)=a3x3+a2x2+a1x+a0
         =((a3x+a2)x+a1)+a0
         =((4x+5)x+3)x+7
   と表現できる。そこで、まず、
     4x0+5=4*2+5=13
   と計算する。次に、4x0+5の値13が計算ずみであることを利用して
     (4x0+5)x+3=(13)*2+3=29
   と計算し、さらに、(4x0+5)x0+3の値29が計算ずみであることを利用して、
     ((4x0)x0+3)+7=(29)*2+7=65
   と計算すればf(2)が得られる。
   
   乗算・加算の回数と変数の個数の比較
   
   初等的計算法
   S3,S2,S1の計算ではそれぞれ、乗算が3回、2回、1回です。
   また、f(2)の計算では、加算が3回です。
   したがって、乗算が6回、加算が3回で合わせて9回実行されています。
   また、S3,S2,S1とf(x0)は計算結果を保存しておくために使われた変数です。
   よって、４個の変数が使われています。
   ホーナー法
   一つの()内で乗算と加算が共に1回ずつであるから、全部で、6回実行されている。
   次に、使用する変数の個数を考えてみる。
   まず、a3=4を変数Sに蓄えておく。そして、
     Sx0+a2=(4)x0+5=4*2+5=13
   を計算し、この値13を再びSに蓄える。
   この時、それまでSに蓄えられていた値a3=4は消去されるが、a3は以後の計算では使わないので不都合は生じない。
   同様に、
     Sx0+a1=(13)x0+3=13*2+3=29
   として計算された値29を再度Sに蓄える。さらに、
     Sx0+a0=(29)x0+7=29*2+7=65
   としてf(2)が得られることができる。
   したがって、使用される変数は1個である。
   比較結果
   　　　初等的計算法　　ホーナー法
   乗算　　　６回　　　　　３回　
   加算　　　３回　　　　　３回
   変数　　　４個　　　　　１個
   
   
   
   

3. プログラムの作成

   File name: rep3a.java
   01: import java.lang.Math;
   02:
   03: class rep3a {
   04:     public static void main(String[] args){
   05:         int a[] = new int[4];
   06:         for(int i = 0; i <= 3; i++)
   07:             a[3-i] = Integer.parseInt(args[i]);
   08:
   09:         double S[] = new double[3];
   10:         for(int j = 0; j <= 2; j++)
   11:             S[2-j] = a[3-j]*Math.pow(2,3-j);
   12:
   13:         System.out.println(S[2]+S[1]+S[0]+a[0]);
   14:     }
   15: }
   
   File name: rep3b.java
   01: class rep3b {
   02:     public static void main(String[] args) {
   03:         int x = 2;
   04:
   05:         int a[] = new int[4];
   06:         for(int i = 0; i <= 3; i++)
   07:             a[3-i] = Integer.parseInt(args[i]);
   08:
   09:         int k = a[3];
   10:         for(int j = 2; j >= 0; j--)
   11:             k = k*x+a[j];
   12:
   13:         System.out.println(k);
   14:     }
   15: }
   

4. プログラムの実行結果

   j03035% javac rep3a.java                         
   j03035% java rep3a 4 5 3 7
   65.0
   
   
   j03035% javac rep3b.java
   j03035% java rep3b 4 5 3 7
   65
   

5. プログラムの考察

   File name: rep3a.java

   01:完全限定名 java.lang.Math をインポートしています。
   05:int 型で要素数４の配列を生成
      int a[];
      a = new int[4];
      とすることもできます。
   07:引数(args[i])の文字列を int 型に変換して、配列 a[3-i] に代入しています。
   09:double 型で要素数３の配列を生成
   11:第N引数 * 2のN乗(a[3-j]*Math.pow(2,3-j))を配列 S[2-j] に代入しています。
   13: S[2]+S[1]+S[0]+a[0] の結果を出力します。
   

   File name: rep3b.java

   03:int 型の変数 x に 2 を代入しています。
   05:int 型で要素数４の配列を生成
   07:引数(args[i])の文字列を int 型に変換して、配列 a[3-i] に代入しています。
   09:int 型に変換された第１引数(a[3])を int 型の変数 k に代入しています。
   11:第１引数(k=a[3]) * x(=2) + 第２引数(a[2])を k に代入しています。
   13:k の結果を出力します。
   

   
   
6. 感想

   今回のレポートはかなり的が外れている気がします。
   でも、一応制御文は使っています（for文だけだけど、、、）。
   次回はもう少しまともなレポートにしたいです。
   

7. 参考文献・URL
   • データ構造と基本アルゴリズム　　　　　共立出版株式会社