配列

とりあえずは, 配列というのは添字つきの入れ物と思ってよい. (厳密には違う. いずれ詳しく説明する.) 他の言語では array と呼ばれるが, Asir では数学的なオブジェクト である vector, matrix を 単なる入れ物として用いて array の 代用品としている.

• 普通の変数

  名前のついた入れ物と思える. 変数が式の中に現れるとその中に入って いる値と置き換わる. また, 代入式の左辺に現れると, 右辺の値が その入れ物の中身になる (上書き).

• 配列

  入れ物が長さ Size 個だけつながったもの.

  A[0]

  A[1]

  $\ldots$

  A[Size-1]

  添字は 0 から始まる (要注意!) ので, 長さが Size なら A[0] から A[Size-1] までの入れ物があること になる.

1. 配列の作り方

   
   [0] A = newvect(5);   /* 長さ 5 の配列 (vector) を生成して A に代入 */
   [ 0 0 0 0 0 ]         /* 最初は 0 ベクトル */
   [1] B = newvect(3,[1,2,3]); /* 長さ 3 の配列を初期値指定して生成 */
   [ 1 2 3 ]            /* B[0] = 1, B[1] = 2, B[2] = 3 */
   

2. 配列の要素の取り出し

   
   [3] B[2];            /* B の添字 2 に対応する要素 */
   3
   [4] C = (B[0]+B[1]+B[2])/3;  /* 式の中に現れる配列要素アクセス */
   2
   [5] C;               /* C には 2 が入っている */
   2
   

3. 配列要素への代入

   
   [6] A[0] = -1;     /* A の先頭に -1 を代入 */
   -1
   [7] A;            /* A が配列なら, A の値は配列全体 */
   [ -1 0 0 0 0 ]
   

4. 配列の長さの取り出し

   
   [8] size(A);      /* 長さを取り出す組み込み関数 */
   [5]               /* リストを返す */
   [9] size(A)[0];   /* リストの先頭要素が長さ */
   5
   

配列についてまとめると,次のようになる.

• 配列は長さ固定の連続した入れ物.
• 長さ N の配列は newvect(N) で生成. 添字は 0 以上 N-1 以下.
• 各要素の書き換えは自由.

例 11.3   配列で与えられた任意個の入力の最大値を求める.

def max(A) {             /* A は配列を入力 */
    N = size(A)[0];      /* N = A の長さ */
    Max = A[0];          /* とりあえず,先頭要素を最大値とする */
    for (I = 1; I < N; I++ ) 
        if ( A[I] > Max )
            Max = A[I];     /* Max = max(A[0],...,A[I] */
    return Max;
}

for 文における添字の範囲に注意する. 1 から N までだから といって, for ( I = 1; I <= N-1; I++ ) とせず, for (I = 1; I < N; I++ ) とするのがスマートな書き方 である.

ここで定義した関数を呼び出す場合, 入力として適当な長さの配列 を用意する必要がある.

[10] A = newvect(7,[2,3,5,10,-1,8,7]);  /* 初期化して生成 */	
[ 2 3 5 10 -1 8 7 ]
[11] max(A);
10

演習 11.1   配列 A の要素の平均値を求める関数を書け.

関数の実行結果として配列を返すこともできる.

例 11.4   漸化式 $a_0=1$, $a_n = 3a_{n-1}+2 (n \ge 1)$ の第 0 項から第 N 項までを返す関数.

def a(N) {
    A = newvect(N+1);   /* 全部で N+1 項分必要 */
    A[0] = 1;           /* a_0 = 1 */
    for ( I = 1; I <= N; I++)
        A[I] = 3*A[I-1] + 2;     /* 漸化式そのまま */
    return A;           /* 配列全体を値として返す */
}

[1] a(10);
[1 5 17 53 ... ]

演習 11.2   自然数 N に対し 2 項係数 $_{\tt N}C_{\tt I}$ ( I = 0, $\ldots$, N) をまとめて返す関数を書け. (漸化式を使って効率よく動くものを書く.)

演習 11.3   配列 A, 自然数 K を入力として, 配列の要素の中で 大きい方から K 番目の要素の値を返す関数を書け.

• アルゴリズム

  考えられる方法を列挙すると

  • 配列に対して並べ替え (整列; sorting) をまず行い, インデックスが K の 要素を取り出す.

    sorting 方法にはいろいろあって, そのうちまとめて話すことになると思うが, とりあえず簡単に思い付く方法はあると思う.

  • 並べ替えは行うものの, 必要なところまでに留める.

    完全に大きさの順に並べる必要はない.

  • 配列のサイズが Sizeのとき, K と Size/2 の大小関係も 考慮する.

    一番小さいもの, を求められているときに, 大きい順に並べるのは効率悪すぎ.

  • 1 番大きいものから順に取り出して, 取り出したあとに印をつけておく. (数字でないものを入れるとか)
  他にもいろいろあると思う. 独創的なアイデアを歓迎する.

• やり方によっては, 入力として受け取った配列の中身を壊す ことも考えられるが, それはしていいことにする.