Previous ToC Next

2. C++言語入門 II

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

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

2.1. 配列

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] ;
と変数宣言で書くと、100個の整数型変数ができ、それぞれが data[0] から data[99] までといった風に、番号で指定して操作 できる。

これはもちろん Fortran で

        integer data(100)
と書くのとほとんど変わらないが、どうでもいいような違いがいくつかある。

括弧はまあなんでもいいが、添字が 0 からになるのは C/C++ の他の多くの言 語とは違った特異な点である。なお、 Fortran の場合は、例えば

      integer data(0:100)
といった具合に「最初と最後」を指定できるので、実は 1 から始めないとい けないというわけではない。しかし、 C/C++ の場合には必ず 0 から始まり、 それを変更する方法はない。

2.2. 多次元配列

宣言はFortran では

      integer data(100,100)
とか書いたが、C/C++ では

 int data[100][100];
と書く。使い方も同様に Fortran では data(i,j) のところを data[i][j] と書く。次元が増えても同様である。 Fortran では配列の次元 は 7 次元までとかいう制限があるが、 C/C++ では特に制限はない。

なお、他にも細かく違うところはある。実用上で大事なのは、メモリ上にデー タがしまわれる順番である。 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/C++ では引数としては渡せないので話が面倒になる。 もっとも、Cの最新の言語仕様ではこれが可能になっているが、現在のところ存在 するほとんどのプログラムはこの機能を使わないで書かれている。

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

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

2.3. ソート

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

   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 番目まで順にやっていく。

このプログラムを実行するには、まずデータファイルを別にエディタで作って おく。これは先頭にデータ数を書き、後は一行に一つ数字を書いておけばいい。このデータファイルの名前 を sample.dat、コンパイルしてできた実行ファイルの名前を simple\_sort とすれば、

  ./simple_sort < sample.dat 
 
とシェルウインドウで入力すれば結果が得られるはずである。

2.3.1. 注意

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

2.4. 練習

  1. ソートのプログラムを手続きを使う形に書き直してみよ。メ インプログラムは手続きを呼 ぶだけの形になるようにすること。

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

なお、あるプログラムの実行時間を計るには time コマンドが使える。

  time ./simple_sort < sample.dat
という風に入力すると、実行結果のあとにもう一行
  0.040u 0.080s 0:00.56 21.4% 0+135k 2+0io 21pf+0w
というような出力が出てくる。この最初の数字が秒単位の実行時間である。な お、実際にかかった時間はもっと長いことがあり得る。これは、ファイルの読 み書きの時間は正確には入らないこと、また何人かで1台の計算機を使ってい るとその分余計に時間がかかることによる。

2.5. 再帰

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

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

2.5.1. もっとも簡単な例

   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:}


上の例 は、階乗を計算するプログラムである。階乗は、下のように定義される:

本当は N が整数でないと定義されないし結果も整数だが、整数だとすぐにオーバーフロー してあまり大きな数の階乗は求められないのでプログラムでは double を使っている。

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
計算機の構造を考えると、こういうことができるというのは一見不思議ではあ る。つまり、関数 factrial の引数 n は同じものなのに、なぜ それが呼ばれるたびに違う値をとることが可能になるのであろうか?

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

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

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

2.6. 練習

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