3 計算の表現と進行

ここでは，二つの整数の割り算を行い「商」と「あまり」を求める方法を3通りの方法で 説明している．これはプログラムの方法に密接に関わる．

3.1 手続き型

手続き型(procedual)の計算では，数多くの要素的計算を逐次的に処理する．たとえば， $a$を$b$で割った商とあまりは，次のように処理する．

• $a$から$b$を引けるだけ引いて，引いた回数を商，残りをあまりとする．

これをC言語で実装すると，リスト1のようになる．

   1 #include <stdio.h>
   2 
   3 int main(void)
   4 {
   5   int a, b;
   6   int r, q;
   7 
   8   a=44;      // a <- 44
   9   b=13;      // b <- 13
  10 
  11   r=a;       // r <- a
  12   q=0;       // q <- 0
  13 
  14   while(r >= b){
  15     r=r-b;
  16     q=q+1;
  17   }
  18 
  19   printf("quotient=%d\tremainder=%d\n", q, r);
  20 
  21   return 0;
  22 }

quotient=3      remainder=5

3.2 関数型

ある関数が別の関数を呼び出して計算の一部を実行させることにより処理を行う．その処 理は，教科書のp.107の下の方の通り．C言語のプログラム例をリスト 2に示す．

   1 #include <stdio.h>
   2 
   3 int q(int a, int b);        // プロトタイプ宣言
   4 int r(int a, int b);
   5 
   6 //=======================================================================
   7 // メイン関数
   8 //=======================================================================
   9 int main(void)
  10 {
  11   int a, b;
  12   int quot, remi;
  13 
  14   a=44;      // a <- 44
  15   b=13;      // b <- 13
  16 
  17   quot=q(a,b);
  18   remi=r(a,b);
  19 
  20   printf("quotient=%d\tremainder=%d\n", quot, remi);
  21 
  22   return 0;
  23 }
  24 
  25 
  26 //=======================================================================
  27 // 商を計算する関数
  28 //=======================================================================
  29 int q(int a, int b)
  30 {
  31 
  32   if(a<b){
  33     return 0;
  34   }else{
  35     return q(a-b, b)+1;
  36   }
  37 
  38 }
  39 
  40 //=======================================================================
  41 // あまりを計算する関数
  42 //=======================================================================
  43 int r(int a, int b)
  44 {
  45 
  46   if(a<b){
  47     return a;
  48   }else{
  49     return r(a-b, b);
  50   }
  51 
  52 }

quotient=3      remainder=5

3.3 宣言型

宣言型では関数型と同じように多くの計算要素によって計算が行われる．計算要素は，条 件，性質，事実を記述した形で示す．たとえば，$a$を$b$で割ったあまりは，教科書の例 のように示すことができる．

C言語では宣言型でプログラムすることはできない．教科書の例は，Prologの記述と思わ れる．

3.4 計算モデルとその間の関係

3.4.0.1 手続き型と非手続き型

• 関数型と宣言型をまとめて非手続き型(non-procedual)と呼ぶことがある．
• それぞれの型には計算処理の得手不得手がある．
• 通常のプログラミングでは，手続き型と非手続き型をあわせて使うことが多い．

3.4.0.2 他の計算モデル

• 書き換え型やネットワーク型，データフロー型などがある．
• 計算の性質を考える多恵の理論的なモデルがある．再帰的関数やチューリング機 械，ラムダ計算などである．

3.4.0.3 計算モデルのあいだの関係

計算記述の方法は，表現できる内容という意味で等価である．ここことを最大値を探索す る計算でしめす．

最大値を探索する問題は， 関数型では教科書p.111の下の方のように記述できる．それをC言語で表現すると，リスト 3のようになる．

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <time.h>
   4 
   5 #define N 30
   6 
   7 int max(int p, int a[]);
   8 void set_rand(int a[]);
   9 //==============================================================
  10 // main関数
  11 //==============================================================
  12 int main(void)
  13 {
  14   int a[N+1], max_int;
  15   
  16   set_rand(a);                    // a[]に乱数を設定
  17 
  18   max_int = max(N,a);             // 1〜Nの最大値探索
  19   printf("max=%d\n", max_int);    // 最大値を表示
  20 
  21   return 0;
  22 }
  23 
  24 //==============================================================
  25 // 最大値を探す再帰関数 教科書 p.105 p.111
  26 //==============================================================
  27 int max(int p, int a[])
  28 {
  29 
  30   if(p==1){
  31     return a[1];
  32   }else{
  33     if(a[p]>max(p-1, a)){
  34       return a[p];
  35     }else{
  36       return  max(p-1, a);
  37     }
  38   }
  39 
  40 }
  41 
  42 //==============================================================
  43 // 配列 a[i] に乱数を設定
  44 //==============================================================
  45 void set_rand(int a[])
  46 {
  47   int i;
  48   
  49   srand((unsigned int)time(NULL));      // 乱数の初期値設定
  50 
  51   for(i=1; i<N+1; i++){
  52     a[i]=rand();                        // 配列に乱数を代入
  53   }
  54 
  55 }

max=2100562050

この手続きを分解すると図1のようになる．関数型の処理の順序通りに， 手続き型で表すとリスト4のように記述できる．両者は全く同 じ計算を行っている．

全く同じ計算を行っているが，計算速度が大きく異なる場合がある．この場合だと，手続 き型のプログラムの方が圧倒的に早い．このように，計算に依存して，得手不得手がある．

図 1: 教科書 p.111 の最大値の問題を解く関数型の実行順序．

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <time.h>
   4 
   5 #define N 30
   6 
   7 void set_rand(int a[]);
   8 //==============================================================
   9 // main関数
  10 //==============================================================
  11 int main(void)
  12 {
  13   int i, a[N+1], max_int;
  14   
  15   set_rand(a);                    // a[]に乱数を設定
  16 
  17   max_int = a[1];
  18   for(i=2; i<N+1; i++){
  19     if(max_int < a[i]) max_int = a[i];
  20   }
  21 
  22   printf("max=%d\n", max_int);    // 最大値を表示
  23 
  24   return 0;
  25 }
  26 
  27 //==============================================================
  28 // 配列 a[i] に乱数を設定
  29 //==============================================================
  30 void set_rand(int a[])
  31 {
  32   int i;
  33   
  34   srand((unsigned int)time(NULL));      // 乱数の初期値設定
  35 
  36   for(i=1; i<N+1; i++){
  37     a[i]=rand();                        // 配列に乱数を代入
  38   }
  39 
  40 }

max=2100562050

ホームページ: Yamamoto's laboratory
著者: 山本昌志