2011年1月28日金曜日

[C/C++] 2次元配列

一般にm x n行列の各要素はaij(1<= i <= m, 1 <= j <= n)と表します.
要素aijには2つの添字i, jがありますが,このように添字が2つある配列を2次元配列といいます.
例えば,2行3列(2 x 3)行列をdouble型の2次元配列として宣言したい場合は以下のようにします.

  double a[2][3] ;

こうすると,6個の要素がa[0][0],a[0][1],a[0][2],a[1][0],a[1][1],a[1][2]の順番に連続してメモリ上に配置され,これらを要素とする2次元配列aが利用できます.

a[0][0]
a[0][1]
a[0][2]
a[1][0]
a[1][1]
a[1][2]

1次元配列と同様,注意が必要なのは,宣言にある数字[2][3]は行,列,それぞれの要素の個数で,添字は0から始まるということです.また,配列を定義する際の[ ]で囲まれた要素数は自然数の定数でなければなりません.
なお,行列を配列として扱う場合,マクロ*を使って,以下のようにしておくとROWとCOLUMNの数字を変えるだけで様々な大きさの行列を扱うことができるので便利です.


配列の要素数は自然数の定数でなければならないと書きましたが,かといって

  int ROW=3COLUMN=4
  ...
  double a[ROW][COLUMN] ;

などとすることはできません.
というのは,上記のような場合,ROWとCOLUNは変数として扱われ,定数としては扱われないためです.

以下に,各要素をキーボード入力して,その値を出力するプログラム例を示します.

#include <stdio.h>
#define ROW   3   //Number of rows
#define COLUMN 4   //Number of column

int main(void)
{
  double a[ROW][COLUMN] ;
  int i, j ;
  printf("Input each element of matrix of row %d and column %d. \n", ROW, COLUMN) ;
  for ( i = 0 ; i < ROW ; i++)
  {
    //The row number of the array is 0 to ROW-1
    printf("Input the element of row %d --->", i+1) ;
    //The row number of the array is 1 to ROW
    for (j = 0 ; j < COLUMN ; j++)
    {
      scanf("%lf", &a[i][j]) ;
    }
  }
  printf("The value of each element is as follows. \n") ;
  for ( i = 0 ; i < ROW ; i++)
  {
    for (j = 0 ; j < COLUMN ; j++)
    {
      //The column number of the array is 0 to COLUMN-1
      printf("a[%d][%d] = %lf \t", i+1, j+1, a[i][j]) ;
      //The column number of the array is 1 to COLUMN-1
    }
    printf("\n");
  }
  return 0;

}

プログラムのコンパイル,実行結果は以下のようになります.
Input each element of matrix of row 3 and column 4. 
Input the element of row 1 --->1 2 3 4 
Input the element of row 2 --->5 6 7 8 
Input the element of row 3 --->9 10 11 12 
The value of each element is as follows. 
a[1][1] = 1.000000 a[1][2] = 2.000000 a[1][3] = 3.000000 a[1][4] = 4.000000 
a[2][1] = 5.000000 a[2][2] = 6.000000 a[2][3] = 7.000000 a[2][4] = 8.000000 
a[3][1] = 9.000000 a[3][2] = 10.000000 a[3][3] = 11.000000 a[3][4] = 12.000000 

1次元配列と同様に,2次元配列でも,以下のように要素をカンマで区切って並べたものを波括弧でくくることで配列を初期化することが可能です.

  int a[2][3] = {{1, 2, 3}, {4, 5, 6}}

このように書くと,それぞれ,a[0][0]=1,a[0][1]=2,a[0][2]=3,a[1][0]=4,a[1][1]=5,a[1][2]=6となります.この書き方は1次元配列のときと同様,配列の宣言時にのみ使用できます.

続いて,2つの行列の和を求めるプログラム例です.
行列A=(aij)と行列B=(bij)の和の各要素は(aij + bij)で表されるので,単純に各要素の和を計算するプログラムになります.

#include <stdio.h>

#define ROW     3
#define COLUMN  4

int main(void)
{
  double a[ROW][COLUMN] = {{1.0, 2.0, 3.0, 4.0}, {5.0, 6.0, 7.0, 8.0}, {9.0, 10.0, 11.0, 12.0}};
  double b[ROW][COLUMN] = {{1.1, 2.2, 3.3, 4.4}, {5.5, 6.6, 7.7, 8.8}, {10.1, 11.1, 12.2, 13.3}};
  double c[ROW][COLUMN] ; int i, j;

  printf("The sum of matrix A and matrix B is: \n");
  for ( i = 0 ; i < ROW ; i++)
  {
    for ( j = 0 ; j < COLUMN ; j++)
    {
      c[i][j] = a[i][j] + b[i][j] ;
      printf("%8.3f", c[i][j]) ;
    }
    printf("\n");
  }
  return 0;
}

上記のプログラムをコンパイル,実行すると以下のようになります.
The sum of matrix A and matrix B is: 
   2.100   4.200   6.300   8.400
  10.500  12.600  14.700  16.800
  19.100  21.100  23.200  25.300

2次元配列への値の代入は1次元配列と同様,要求ごとに行う必要があります.

* マクロとは,プログラム中の文字列をあらかじめ定義した規則にしたがって置換する機能のことです.マクロは,#defineというプリプロセッサ指令により定義します.

2011年1月27日木曜日

[C/C++] ソーティング

1次元配列を利用したプログラムの代表的なものにソーティング(sorting)があります.
ソーティングとは,データを大きい順(降順),小さい順(昇順)に並べ替えることを言います.ソーティングのアルゴリズムには色々なものがありますが,以下ではバブルソート(bubble sort)について記載します.
バブルソートでは,昇順にデータを並べ替える場合,隣り合ったデータどうしを比較して前の値が後の値より大きければ値を交換して次のデータに移るという操作を繰り返します.

例として21, 9, 23, 5, 7 と並んでいる数字を昇順に並び替えることを考えます.
まずは,1回目の比較を行います.
1. 21 と9 を比較して(下図1 行目),21 の方が大きいので順番を並べ替える(下図2 行目).
2. 並べ替えられた21 と23 を比較して(下図3 行目),21 の方が小さいので並べ替えは行わない(下図4 行目).
3. 23 と5 を比較して(下図5 行目),23 の方が大きいので順番を並べ替える(下図6 行目).
4. 並べ替えられた7 と23 を比較して(下図7 行目)7の方が小さいので並べ替えは行わない(下図7 行目).
21
9
23
5
7
9
21
23
5
7
9
21
23
5
7
9
21
23
5
7
9
21
23
5
7
9
21
5
23
7
9
21
5
7
23
9
21
5
7
23

続いて,2回目の比較を行います.
1. 9 と21 を比較して(下図1 行目),9 の方が小さいので順番を並べ替えは行わない(下図2 行目).
2. 21 と5 を比較して(下図3 行目),21の方が大きいので順番を並べ替える(下図4 行目).
3. 並べ替えられた21 と7 を比較して(下図5 行目),21 の方が大きいので順番を並べ替える(下図6 行目).
4. 並べ替えられた21 と23 を比較して(下図7 行目),21 の方が小さいので並べ替えは行わない(下図8 行目).
9
21
5
7
23
9
21
5
7
23
9
21
5
7
23
9
5
21
7
23
9
5
21
7
23
9
5
7
21
23
9
5
7
21
23
9
5
7
21
23

さらに,3回目の比較を行います.
1. 9 と5 を比較して(下図1 行目),9 の方が大きいので順番を並べ替える(下図2 行目).
2. 並べ替えられた9 と7 を比較して(下図3 行目),9 の方が大きいので順番を並べ替える(下図4行目).
9
5
7
21
23
5
9
7
21
23
5
9
7
21
23
5
7
9
21
23

3回目の比較が終了した段階でデータの交換はなくなり,並べ替えが完了です.

ちなみに,上記の例のように昇順の場合,気泡が上に上がっていくようにして値の小さい数が先頭に移動していくのでこの方法はバブルソートと呼ばれます.

この手順をプログラムにしていくことを考えます.
まず,隣り合う2つの値を比較して,後ろの方の値が小さければ2つの値を交換するには以下のようにします.
if( a[i] > a[i+1])
{
    tmp = a[i] ;
    a[i] = a[i+1] ;
    a[i+1] = a[i+1] ;

}
ここで,2つの数を交換するときには,一時的な変数"temp"を用意する必要があります.もし,2つの値を交換しようとして
    a[i] = a[i+1] ;
    a[i+1] = a[i] ;
とすると,a[i]とa[i+1]の値が同じになってしまいます(より正確には最初にa[i+1]に格納されていた数と同じになる).
また,プログラムを終了させるには,2つの数の交換が起こったかどうかを知る必要がでてきます.そのためには,以下のように交換が起こった時にはそのことを記録する変数を用意します.

上記の例では,変数 flag を用意して,2つの数の交換がなければ flag=0,交換があれば flag=1 となるようにしています.このようにある動作が行われたかどうかを確かめる(プログラム中の動作確認)ために使用される変数のことをフラグ変数といいます.

以下に,バブルソートのプログラム例を示します.
#include <stdio.h>

#define N 5 //Number of elements

int main(void)
{
  int a[N]={21, 9, 23, 5, 7} ;  //Preparing the data
  int i, tmp, flag ;

  do
  {
    flag = 0 ;         //As initial setting, there is no exchange of numbers
    for( i = 0 ; i < N-1 ; i++ )
    {
      if( a[i] > a[i+1] )
      {
        tmp = a[i] ;   //Exchange of values
        a[i] = a[i+1] ;
        a[i+1] = tmp ;
        flag = 1 ;     //Flag is set if there is exchange of values
      }
    }
  }while( flag == 1 ); //Continue as long as there are two numbers of exchanges.

  for ( i = 0 ; i < N ; i++)
  {
    printf("%d    ", a[i]) ; //Output the result
  }
  printf("\n");

  return 0;

}

上記のプログラムをコンパイル,実行すると以下のようになります.
5    7    9    21    23