ホーム » 「再帰」タグがついた投稿

タグアーカイブ: 再帰

2019年10月
« 9月    
 12345
6789101112
13141516171819
20212223242526
2728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

リスト処理

リスト構造

リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。

struct List {
   int          data ;
   struct List* next ;
} ;
struct List* top ;

top = (struct List*)malloc( sizeof( struct List ) ) ;
top->data = 111 ;
top->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->data = 222 ;
top->next->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->next->data = 333 ;
top->next->next->next = NULL ; // 末尾データの目印

struct List*p ;
for( p = top ; p != NULL ; p = p->next ) {
   printf( "%d¥n" , p->data ) ;
}

補助関数

上記のプログラムでは、(struct…)malloc(sizeof(…))を何度も記載し、プログラムが分かりにくいので、以下に示す補助関数を使うと、シンプルに記載できる。

struct List* cons( int x , struct List* n ) {
   struct List* ans ;
   ans = (struct List*)malloc( sizeof( struct List ) ) ;
   if ( ans != NULL ) {
      ans->data = x ;
      ans->next = n ;
   }
   return ans ;
}
struct List* top ;
top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;

補助関数の名前の cons は、constructor の略であり、古くから使われている List Processor(LISP) というプログラム言語でのリスト(セル)を生成する関数が cons 。

LISPと関数型プログラミング言語

LISPの歴史は長く、最古のFORTRAN,COBOLに次ぐ3番目ぐらい。最初は、人工知能のプログラム開発のための関数型プログラミング言語として作られた。特徴として、データもプログラムもすべてリスト構造(S式)で表すことができ、プログラムは関数型に基づいて作られる。

関数型プログラミングは、Ruby や Python でも取り入れられている。関数型プログラミングは、処理を関数をベースに記述することで「副作用を最小限にすることができ」、極端な話をすればループも再帰呼出しで書けばいい…。

LISPの処理系は、最近では Scheme などが普通だが、プログラムエディタの Emacs は、内部処理が LISP で記述されている。

簡単なリスト処理の例

先に示したリスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。

// 全要素を表示する関数
void print( struct List* p ) {
   for( ; p != NULL ; p = p->next )
      printf( "%d " , p->data ) ;
   printf( "¥n" ) ;
}
// データ数を返す関数
int count( struct List* p ) {
   int c = 0 ;
   for( ; p != NULL ; p = p->next )
      c++ ;
   return c ;
}
void main() {
   struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ;
   print( top ) ;
   printf( "%d¥n" , count( top ) ) ; 
}

リスト処理を自分で考えて作成

以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。

// 全要素の合計
int sum( struct List* p ) {
   // sum( top ) → 888

}
// リストの最大値を返す
int max( struct List* p ) {
   // max( top ) → 444 (データ件数0の場合0を返す)

}
// リストの中から指定した値の場所を返す
int find( struct List* p , int key ) {
   // find( top , 444 ) = 1 (先頭0番目)
   // 見つからなかったら -1

}

再帰呼び出しでリスト処理

リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか?

// 全データを表示
void print( struct List* p ) {
   if ( p == NULL ) {
      printf( "¥n" ) ;
   } else {
      printf( "%d " , p->data ) ;
      print( p->next ) ; // 末尾再帰
   }
}
// データ数を返す関数
int count( struct List* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1 + count( p->next ) ; // 末尾再帰
}
// 全要素の合計
int sum( struct List* p ) {
   // sum( top ) → 888
   自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
   // max( top ) → 444 (データ件数0の場合0を返す)
   自分で考えよう
}
// リストの中から指定した値を探す。
int find( struct List* p , int key ) {
   // find( top , 444 ) = 1 
   // 見つかったら1 , 見つからなかったら 0
   自分で考えよう
}

理解度確認

上記プログラム中の sum() , max() , find() を再帰呼び出しをつかって記述せよ。

予備実験2 パズル問題

プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。

組み合わせ問題の基礎

簡単な問題として、「100未満の整数の値を3つ選び、その値を辺の長さとした場合、 直角三角形となるものをすべて表示する。」について考える。

一番簡単な方法は、以下となるであろう。

#include <stdio.h>
#include <math.h>
#include <time.h>

// 整数比の直角三角形の一覧を求める。
void integer_triangle( int n ) {
   for( int a = 1 ; a < n ; a++ ) {
      for( int b = 1 ; b < n ; b++ ) {
         // 一番ダサい方法
         for( int c = 1 ; c < n ; c++ ) {
            if ( a*a + b*b == c*c ) {
               printf( "%d %d %d\n" , a , b , c ) ;
            }
         }
      }
   }
}
int main() {
   integer_triangle( 100 ) ;
   return 0 ;
}

しかしこのプログラムの欠点としては、100×100×100回のループで無駄な処理が多い。

ループ回数を減らすだけなら、最も内側の処理を、計算で整数値か確認すればいい。

void integer_triangle( int n ) {
   for( int a = 1 ; a < n ; a++ ) {
      for( int b = 1 ; b < n ; b++ ) {
         // ココも改良できるよね?
         int d = a*a + b*b ;
         int c = (int)sqrt( d ) ;
         // 斜辺Cの整数値を求め、改めて確認する。
         if ( c*c == d ) {
            printf( "%d %d %d\n" , a , b , c ) ;
         }
      }
   }
}

(1) 計算誤差の問題を考えてみよう。

たとえば、3:4:5の直角三角形で、3*3+4*4 = 25 だが、sqrt(25)は実数で計算するから、 計算誤差で4.99999で求まったらどうなるだろうか?

1~100までの数値で、”int a = sqrt( (double)(i*i) ) ;” を計算してみて、 異なる値が求まることはあるか? 多少の計算誤差があっても正しく処理が行われるにはどうすればいいか、考えてみよう。

(2) 無駄な答えについて考えてみよう。

このプログラムの答えでは、簡単な整数比の答えの「整数倍の答え」も表示されてしまう。 たとえば、(3:4:5)の答えのほかに、(6:8:10)も表示される。 こういった答えを表示しないようにするにはどうすればよいか?

また、この2つのプログラムの処理時間を実際に比べてみる。

int main() {
   time_t start , end ;
   // time() 関数は、秒数しか求まらないので、
   // あえて処理を1000回繰り返し、数秒かかる処理にする。
   start = time( NULL ) ;
   for( int i = 0 ; i < 1000 ; i++ ) {
      // ただし、関数内のprintfをコメントアウトしておくこと
      integer_triangle( 100 ) ;
   }
   end = time( NULL ) ;
   printf( "%lf\n" , difftime( end , start ) ) ;
   return 0 ;
}

再帰プログラミング

組み合わせ問題では、forループの多重の入れ子で問題を解けない場合が多い。 (書けないことはないけど無駄なループで処理が遅くなるか、入れ子段数が可変にできない。)

こういった場合には、再帰プログラミングがよく利用される。 もっとも簡単な再帰の例として、階乗のプログラムを考える。 通常であれば、以下のような for ループで記述することになるだろう。

// 階乗の計算
int fact( int x )
{  // ループ
   int f = 1 ;
   for( int i = 2 ; i <= x ; i++ )
      f = f * i ;
   return f ;
}

再帰呼び出しでは、関数の処理の中に、自分自身の関数呼び出しが含まれる。 また、無限に自分自身を呼び出したら処理が止まらないので、 問題を一つ小さくして、これ以上小さくできないときは処理を止めるように記述する。

int fact( int x )
{  // 再帰呼び出し
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x - 1 ) ;
}

ここ以降は、指定長さを指定辺の組み合わせで作ると、Flood-fill の選択とする。

指定長を指定辺の組み合わせで作る

再帰を使った簡単なパズル問題として、以下のプログラムを作成したい。

配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
(例) 辺の長さ10を作るには、(5,4,1)とか(7,3)などが考えられる。
これは、ナップサック問題の基本問題で、容量の決まったナップサックに最大量入れる組合せを求めるのと同じである。

このプログラムを解くには…

10 を [4,5,2,1,3,7] で作るには...
 (0) 6=10-4 を [5,2,1,3,7]で作る。
 (1) 5=10-5 を [4,2,1,3,7]で作る。
 (2) 8=10-2 を [5,4,1,3,7]で作る。
 (3) 9=10-1 を [5,2,4,3,7]で作る。
 (4) 7=10-3 を [5,2,1,4,7]で作る。
 (5) 3=10-7 を [5,2,1,3,4]で作る。

そこで、ここまでの考えを、以下のようなプログラムで記述してみる。

// 指定されたデータを入れ替える。
void swap( int*a , int*b )
{  int x = *a ;
   *a = *b ;
   *b = x ;
}
void check( int array[] , int size , int len , int n )
{
   // array[] 配列
   // size    配列サイズ
   // len     作りたい長さ
   // n       使った個数
   for( int i = n ; i < size ; i++ ) {
      // i番目を先頭に...
      swap( &array[ n ] , &array[ i ] ) ;
      printf( "check( array , %d , %d , %d )\n" ,
              size , len - array[ n ] , n+1 ) ;
      // 最初のswapでの変更を元に戻す。
      swap( &array[ i ] , &array[ n ] ) ;
   }
}
int main() {
   int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
   check( a , 6 , 10 , 0 ) ;
}

(1) これを再帰呼び出しにしてみよう。どう書けばいい?

void check( int array[] , int size , int len , int n )
{
   // array[] 配列
   // size    配列サイズ
   // len     作りたい長さ
   // n       使った個数
   if ( len < 0 ) {
      // 指定した丁度の長さを作れなかった。
      ;
   } else if ( len == 0 ) {
      // 指定した長さを作れたので答えを表示。
      for( int i = 0 ; i < n ; i++ ) {
         printf( "%d " , array[ i ] ) ;
      }
      printf( "\n" ) ;
   } else {
      // 問題を一つ小さくして再帰。
      for( int i = n ; i < size ; i++ ) {
         swap( &array[ n ] , &array[ i ] ) ;
         printf( "check( array , %d , %d , %d )\n" ,
                 size , len - array[ n ] , n+1 ) ;
         check( array , size , len - array[ n ] , n + 1 ) ;
         swap( &array[ i ] , &array[ n ] ) ;
      }
   }
}

(2) 少ない組み合わせの方がポイントが高い場合には、プログラムをどう変更する?
(3) 答えが1つだけで良い場合は、プログラムをどう変更する?
(4) このプログラムでは、冗長な答えがあるか?ないか?検討せよ。
(5) 前設問の整数比直角三角形のプログラムで、冗長な答えを削除するプログラムを作成せよ。
# ただし、(2)〜(5)は、演習の実験の時間内でできる範囲とする。

Flood fill アルゴリズム

前の問題は、今年度のプログラミングコンテストの課題のパズルとは、方向性が違うので、今年度のプロコンの競技部門に近いパズルネタで演習。(Wikipedia Flood-fill参照)

以下の image のような2次元配列が与えられたら、指定座標(x,y)を中心に周囲を塗りつぶす処理を作成せよ。

include <stdio.h>

// *は壁 SPCは白 この領域の指定位置を#で塗りつぶす。                            
char image1[10][10] = { // (4,4)始点で塗りつぶし後
        "*********" ,   // ********* 
        "*   *   *" ,   // *   *###*
        "*   *   *" ,   // *   *###*
        "*  *    *" ,   // *  *####*
        "***   ***" ,   // ***###***
        "*    *  *" ,   // *####*  *
        "*   *   *" ,   // *###*   *
        "*   *   *" ,   // *###*   *
        "*********" ,   // *********
} ;

char image2[10][10] = { // 応用問題用の画像例
        "*********" ,   //  *   のような隙間は通り抜けられる
        "*   *   *" ,   // *    ようにするにはどうすればいい?
        "*  **   *" ,   //   **
        "* **    *" ,   //  **  これは通り抜けられない
        "***   ***" ,   // **
        "*    *  *" ,
        "*   *   *" ,
        "*   *   *" ,
        "*********" ,
} ;

// 盤面を表示                                                                   
void print_image( char image[10][10] ) {
  for( int y = 0 ; y < 9 ; y++ ) {
    for( int x = 0 ; x < 9 ; x++ ) {
      printf( "%c" , image[y][x] ) ;
    }
    printf( "\n" ) ;
  }
}

// 再帰呼び出しを使った flud_fill アルゴリズム                                  
void flood_fill( char image[10][10] , int x , int y , char fill ) {
  // 指定座標が空白なら
  if ( image[y][x] == ' ' ) {
    // その座標を埋める
    image[y][x] = fill ;
    //////////////////////////////////////
    // ここに周囲をflud_fillする処理を書く  //
    ////////////////////////////////////// 
  }
}

int main() {
  print_image( image1 ) ;
  flood_fill( image1 , 4 , 4 , '#' ) ;
  print_image( image1 ) ;
  return 0 ;
}

応用問題

Wikipediaのflood-fill のプログラムの説明のアルゴリズムでは、左図黒のような斜めに並んだブロックは、境界として通り抜けられないようにつくられている。

そこで、斜めに並んだブロックは通り抜けられるルールとした場合のプログラムを記述せよ。

JavaScriptでマージソート

配列のマージソートを、難しいテクニックを使わないスタンダードな書き方でのサンプル。

function merge_sort( a , start , end ) {
   if ( start + 1 == end ) {
      // a[start]の1件だけなので並び替える必用なし
   } else {
      // 真ん中
      var mid = Math.floor( (start + end) / 2 ) ;
      // 左半分を並べ替え
      merge_sort( a , start , mid ) ;
      // 右半分を並べ替え
      merge_sort( a , mid , end ) ;

      // 2つの山をマージする。
      var temp = new Array() ;          // マージ結果の一時的保存用
      var lt = start ;                  // 左の山の先頭
      var rt = mid ;                    // 右の山の先頭
      // ここがまだダサい。
      for( i = 0 ; i < end - start ; i++ ) {
         var w ;
         if ( lt >= mid ) {        // 左の山が空、右の山から取り出す
            w = a[ rt ] ;
            rt++ ;
         } else if ( rt >= end ) { // 右の山が空、左の山から取り出す
            w = a[ lt ] ;
            lt++ ;
         } else if ( a[lt] > a[rt] ) {  // 左の山から取り出す
            w = a[ lt ] ;
            lt++ ;
         } else {                       // 右の山から取り出す
            w = a[ rt ] ;
            rt++ ;
         }
         temp[ i ] = w ;
      }
      // マージした結果を、a[]のstart..endに戻す
      for( var i = 0 ; i < end - start ; i++ ) {
         a[ start + i ] = temp[ i ] ;
         console.log( "a["+(start+i)+"]="+a[start+i]) ;
      }
   }
}

array = new Array( 11 , 45 , 22 , 33 , 77 , 88 , 44 , 55 ) ;
merge_sort( array , 0 , array.length ) ;
for( var i = 0 ; i < array.length ; i++ )
   console.log( "a["+i+"]=" + array[i] ) ;

JavaScriptの再帰の例題

再帰呼び出しで分割統治法の考え方のプログラムをJavaScriptで書いたサンプル

単純に、配列の指定範囲の合計を求める関数を、再帰を用いて記述する。

<html>
<head>
</head>
<body>
 <p>
  このプログラムは、実行結果を console.log() で出力するので、
  Ctrl+Shift+I で、JavaScript の console を表示させてね。
 </p>
 <script type="text/javascript">
   // a : 配列
   // start : 合計を計算する範囲の戦闘
   // end : 合計を計算する範囲の最後+1
   // 配列の合計は、配列の先頭 + 残りの合計
   function array_sum( a , start , end ) {
     console.log( "array_sum:" + start + "," + end ) ;
     if ( start == end ) {
       console.log( "array_sum(" + start + "," + end + ")=0" ) ;
       return 0 ;
     } else {
       var ans = a[ start ] + array_sum( a , start + 1 , end ) ;
       console.log( "array_sum("+start+","+end+")="+ans ) ;
       return ans ;
     }
   }
   var array = new Array( 11 , 22 , 33 , 44 , 55 , 66 , 77 , 88 ) ;
   console.log( array_sum( array , 0 , array.length ) ) ;

   // 配列の合計は、データが1個ならその値。
   // そうでなければ、配列の前半の合計 + 配列の後半の合計
   function array_sum2( a , start , end ) {
     console.log( "array_sum2:" + start + "," + end ) ;
     if ( start + 1 == end ) {
       var ans = a[ start ] ;
       console.log( "array_sum2("+start+","+end+")="+ans ) ;
       return ans ;
     } else {
       var mid = Math.floor( ( start + end ) / 2 ) ;
       var ans = array_sum2( a , start , mid ) // 配列前半の合計を求める
               + array_sum2( a , mid , end ) ; // 配列後半の合計を求める
       console.log( "array_sum2("+start+","+end+")="+ans ) ;
       return ans ;
     }
   }
   console.log( array_sum2( array , 0 , array.length ) ) ;
  </script>
</body>
</html>