本章では、後の話で必要になる最低限の C++ の知識ということで、配列と再帰 処理について簡単にまとめる。

本来、 C++ らしい（C や Fortran ではできないような）プログラムスタイル の根幹をなすのは、「クラス」と「テンプレート」であるが、 また後で触れることにしたい。

Fortran でも C/C++ でも、数値計算をする上で基本になるデータ構造は多く の場合に配列である。

   1:// calculate_sum
   2:#include <iostream>
   3:using namespace std;
   4:
   5:int main()
   6:{
   7:    int  n ;
   8:    int  data[100];
   9:    int  i,sum;
  10:    cout << "How many numbers you want to input?";
  11:    cin >> n;
  12:    for (i=0;i<n;i++) cin >>data[i];
  13:    sum = 0;
  14:    for (i=0;i<n;i++){
  15:        sum += data[i];
  16:        cout << "data[" << i <<"]=" << data[i] << " sum=" << sum << endl;
  17:    }
  18:}

  int  data[100] ;

これはもちろん Fortran で

        integer data(100)

• 括弧が丸括弧ではなくて角括弧である。
• 添字が 1 からではなく 0 から始まる。

      integer data(0:100)

宣言はFortran では

      integer data(100,100)

 int data[100][100];

なお、他にも細かく違うところはある。実用上で大事なのは、メモリ上にデー タがしまわれる順番である。 1 次元配列ではもちろん配列要素が順にメモリ 上におかれるが、2次元配列では 2 つの可能性がある。つまり、最初の要素 data(1,1) あるいは data[0][0] の次に来るのがなにか？であ る。 Fortran では data(2,1) が来るが、C/C++ではdata[0][1] が来る。この違いは、いろいろな場面で意識する必要がある。

なお、このC の言語仕様で定義された普通の配列に関する限り、 C/C++ の多 次元配列には Fortran のそれに比べた大きな欠点がある。 それは、関数の引数として配列を渡す時に、大きさを変数として渡すことがで きないということである。つまり、 Fortran では

      subroutine sub1(a, n, nn)
      integer n, nn
      real*8 a(nn,nn)
      .....

もっとも、これはあくまでも汎用のライブラリを準備し、しかもそれをソース プログラムとしてではなくあらかじめコンパイルしたいわゆるバイナリライブ ラリとして準備する時にだけ問題になることではある。従って、自分でプログ ラムを書く場合にはあまり問題にはならない。

コンパイルしたライブラリを作るにはいろいろな方法がある。 C++ では、ユー ザーが新しいデータ型を定義することができるので、自分で定義してしまえば Fortran の配列よりももっと便利に使えるものができる。また、既に人が作っ た便利なものがいろいろあるので、高度なことをするにはそういったものの利 用を考えるベきである。

配列を使う例だが、 計算天文学とはいえ、数値計算ばかりでも芸がないので、ここではちょっと違 うこともやってみよう。

   1:// sort.C
   2:  
   3:#include <iostream>
   4:using namespace std;
   5:  
   6:int main()
   7:{
   8:    int n;
   9:    double data[100];
  10:    int   i,j;
  11:    cin >> n;
  12:    for (i=0;i<n;i++)cin >> data[i];
  13:    cout << "Input data\n";
  14:    for (i=0;i<n;i++) cout << data[i]<<endl;
  15:    for (i=0;i<n-1;i++){
  16:        for (j=i+1;j<n;j++){
  17:            if (data[i] > data[j]){
  18:                double  work;
  19:                work = data[i];
  20:                data[i] = data[j];
  21:                data[j]= work;
  22:            }
  23:        }
  24:    }
  25:    cout << "Sorted data\n";
  26:    for (i=0;i<n;i++) cout << data[i] << endl;
  27:    return 0;
  28:}

1. まず、一番小さい数を先頭に持ってくる。そのために、配列の2番 目の要素から最後の要素までを順に見て、それが先頭の値よりも小さければ2 つを入れ換える。
2. これで先頭にもっとも小さい数が来た。次に、2番目の位置に残りの 数の中で最小のものを持ってくる。これには、配列の3番 目の要素から最後の要素までを順に見て、それが2番目の値よりも小さければ2 つを入れ換える。
3. 以下、同様に、 N-1 番目まで順にやっていく。

  ./simple_sort < sample.dat 
 

コンパイルして作るプログラムの名前には sort は使わな いこと。これは、この名前の別のプログラムがあらかじめ準備されていて、そ ちらが実行されてしまうからである。もちろん、 ./sort と指定すれば 自分で作ったものが実行されるが、いずれにしても混乱する可能性がある。

1. ソートのプログラムを手続きを使う形に書き直してみよ。メ インプログラムは手続きを呼 ぶだけの形になるようにすること。
   1. ソートのプログラムについて、データの数を非常に大きくした時、 実行時間がどうなるかを測定せよ。配列宣言の数字を大き くするのを忘れないこと。また理論上どうなるはずか考えてみよ。

  time ./simple_sort < sample.dat

  0.040u 0.080s 0:00.56 21.4% 0+135k 2+0io 21pf+0w

配列に関しては C++ は Fortran に比べて必ずしも良くなっているとはいい難 い、というか正直いって退化しているが、プログラムの構造という観点からは いくつか Fortran にはない有用な特色を持つ。その一つがここで述べる再帰 である。なお、最近の多くの Fortran コンパイラでは、言語仕様では再帰を サポートしていなくても実際には仕様が拡張されていて再帰が使える。また、 F90 は言語仕様として再帰をサポートする。

再帰とは、手続きが「自分自身を呼び出す」ことである。これは、プログラミ ングの理論的な扱いという観点からも、また、実用上からも非常に重要な考え 方である。簡単な例から考えてみよう。

   1:// factorial
   2:#include <iostream>
   3:using namespace std;
   4:  
   5:double factorial(int n)
   6:{
   7:    if (n <1){
   8:return 1.0;
   9:    }else{
  10:return  n*factorial(n-1);
  11:    }
  12:}
  13:  
  14:int main()
  15:{
  16:    int n;
  17:    cout << "Enter n:";
  18:    cin >> n;
  19:    cout <<"N = " << n << "   N! = " << factorial(n) <<endl;
  20:    return 0;
  21:}

CやPascalのような「近代的」プログラミング言語では、この定義に従って素直にプログ ラムを書くことができる。上の例では、まさに、 n が 1 なら 1 を返 し、それ以外では n*factrial(n-1)を返すというのが、 factrial(n)の中身になっている。

例えば factrial(5) を計算させるとすると、実際の計算は、以下のよ うな手順で進む。

  actrial(5)
  →5*factrial(4)
  →5*(4*factrial(3))
  →5*(4*(3*factrial(2)))
  →5*(4*(3*(2*factrial(1))))
  →5*(4*(3*(2*1)))
  →5*(4*(3*2))
  →5*(4*6)
  →5*24
  →120

再帰処理を許さない言語の場合、関数の引数や関数中で宣言された変数には 「固定したアドレス」が与えられる。このために、関数が自分自身を呼ぶと、 引数の値や変数の値が書き変わってしまいなんだかわからない動作をすること になる。

これに対し、 C/C++ などの再帰処理を許す言語では、関数の引数や関数中で 宣言された変数は固定されたアドレスを持っているわけではなく、関数が呼ば れる度に新しいメモリ領域が割り当てられる。これは別に難しいことではなく て、ある連続したアドレス領域（通常スタック、、、書類を積み上げた山、、、 と呼ばれる）をあらかじめ確保しておいて、サブルーチンが呼ばれればそこに 新しく場所をとり、サブルーチンから抜ける時に使っていた場所を返すだけで ある。

ただこれだけのことで、「関数が自分自身を呼ぶ」というなんだか怪しげなこ とが実現できるわけである。

1. 階乗を計算する関数を、再帰を使わない形に書き直してみよ。
2. フィボナッチ数列 $F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1$を再 帰、再帰でないものの両方を使って書け。
3. 上のフィボナッチ数列について、n を大きくしていった時に計算の手間が どのように増えるかを、再帰の場合とそうでない場合のそれぞれについ て考察せよ。

   Previous

   ToC

   Next