創造工学演習の予備実験 part 2 として、Flood Fill , 8queen にチャレンジしてみる。

Flood fill アルゴリズム

前の問題は、今年度のプログラミングコンテストの課題のパズルとは、方向性が違うので、今年度のプロコンの競技部門にちょっとだけ近い2次元フィールドのパズルネタで演習。(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 ) {
  // image: 塗りつぶす画像
  // x,y:   塗りつぶす場所
  // 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 ;
}

import java.util.*;

public class Main {
    public static String[] image1 = {
        "*********" ,   // ********* 
        "*   *   *" ,   // *   *###*
        "*   *   *" ,   // *   *###*
        "*  *    *" ,   // *  *####*
        "***   ***" ,   // ***###***
        "*    *  *" ,   // *####*  *
        "*   *   *" ,   // *###*   *
        "*   *   *" ,   // *###*   *
        "*********" ,   // *********
    } ;
    // 文字配列を文字の2次元配列に変更
    public static char[][] map_from_string( String[] image ) {
        char[][] map = new char[ image.length ][ image[0].length() ] ;
        for( int i = 0 ; i < image.length ; i++ ) {
            for( int j = 0 ; j < image[ i ].length() ; j++ ) {
                map[ i ][ j ] = image[ i ].charAt( j ) ;
            }
        }
        return map ;
    }
    // 2次元配列を出力
    public static void print_image( char[][] map ) {
        for( int i = 0 ; i < map.length ; i++ ) {
            for( int j = 0 ; j < map[i].length ; j++ ) {
                System.out.print( map[ i ][ j ] ) ;
            }
            System.out.println() ;
        }
    }
    // 塗りつぶし処理
    public static void flood_fill( char[][] map , int x , int y , char c ) {
        if ( map[x][y] == ' ' ) {

            // 指定された場所に埋める文字を代入
            map[x][y] = c ;

            ////////////////////////////////////////////
            // ここに周囲を flood_fill する処理を書く //
            ////////////////////////////////////////////
        }
    }
    public static void main(String[] args) throws Exception {
        char[][] map = map_from_string( image1 ) ;
        print_image( map ) ;
        flood_fill( map , 4 , 4 , '#' ) ;
        print_image( map ) ;
    }
}

• Flood Fill Java版(Paiza.io)

応用問題

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

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

レポート提出

レポートでは、指定長を辺の組み合わせで作るテーマか、Flood-fill のテーマのいずれかにて、以下の内容をまとめてレポートとして提出すること。

• • レポートの説明(自分の選んだテーマと自分なりの説明)
  • プログラムリスト
  • 動作確認の結果

N Queen

パズル問題の定番の8 Queen を考えてみる。

8 Queen とは、8×8のチェスの盤面に、8つの Queen をお互いに取られないように配置するパズル。

import java.util.*;

public class Main {
    public final static int size = 4 ;
    public static int[] board = new int[ size ] ;
    
    // できあがった盤面を表示する補助関数
    public static void print_board( int[] board ) {
        for( int i = 0 ; i < size ; i++ ) {
            for( int j = 0 ; j < board[ i ] ; j++ )
                System.out.print( "+ " ) ;
            System.out.print( "Q " ) ;
            for( int j = board[ i ] + 1 ; j < size ; j++ )
                System.out.print( "+ " ) ;
            System.out.println() ;
        }
        System.out.println() ;
    }
    
    // n_queen本体
    //   4 queen の boad 配列
    //   [ 1 3 0 2 ]
    //     + + Q +
    //     Q + + +
    //     + + + Q
    //     + Q + +
    public static void n_queen( int[] board , int n , int i ) {
        // nは盤面の大きさ
        // i列目のj行目に置く(i=2)
        // [ 1 3 j ? ]
        //   0 1 2 3
        // 0 + + + +
        // 1 Q + + +
        // 2 + +[Q]+ j=2
        // 3 + Q + +
        if ( i == n ) {
            // 右端まですべて埋まったら答えとして表示
            print_board( board ) ;
        } else {
            // j行目に置くのを試す
            for( int j = 0 ; j < size ; j++ ) {
                // 同じ行に置かれたものが無いか探す
                boolean flag = true ;
                for( int k = 0 ; k < i && flag ; k++ ) {
                    if ( board[ k ] == j )
                        flag = false ; // 同じ行にすでに置かれている
                }
                if ( flag ) {   // 同じ行が使われていなければ
                    // 斜め左上に向かってぶつかるQueenを探す
                    for( int u = j - 1 , h = i - 1 ; u >= 0 && h >= 0 && flag ; u-- , h-- ) {
                       if ( board[ h ] == u )
                            flag = false ;
                    }
                    // 斜め左下に向かってぶつかるQueenを探す
                    for( int d = j + 1 , h = i - 1 ; d < size && h >= 0 && flag ; d++ , h-- ) {
                        if ( board[ h ] == d )
                            flag = false ;
                    }
                    if ( flag ) {
                        // 左横、左斜め上、左斜め下にぶつかるQueenが無かったら、再帰
                        board[ i ] = j ;
                        n_queen( board , n , i + 1 ) ;
                    }
                }
            } 
        }
    }
    public static void main(String[] args) throws Exception {
        n_queen( board , size , 0 ) ;
        print_board( board ) ;
        
    }
}

• N Queen(Paiza.io)

プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。また、課題部門や自由部門であっても、複数の条件の組み合わせの中から最良のものを選ぶといった処理も求められる。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。

組み合わせ問題の基礎

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

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

#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 c = sqrt( (double)(i*i) ) ;” を計算してみて、 異なる値が求まることはあるか？ 多少の計算誤差があっても正しく処理が行われるにはどうすればいいか、考えてみよう。

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

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

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

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

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 課題の選択とする。

指定長を指定辺の組み合わせで作る(テーマ1)

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

配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
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 を [4|5,2,1,3,7]で作る。
　(1) 5=10-5 を [5|4,2,1,3,7]で作る。
　(2) 8=10-2 を [2|5,4,1,3,7]で作る。
　(3) 9=10-1 を [1|5,2,4,3,7]で作る。
　(4) 7=10-3 を [3|5,2,1,4,7]で作る。
　(5) 3=10-7 を [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) 答えが１つだけで良い場合は、プログラムをどう変更する？
(4) このプログラムでは、冗長な答えがあるか？ないか？検討せよ。
(5) 前設問の整数比直角三角形のプログラムで、冗長な答えを削除するプログラムを作成せよ。

# レポートでは、(2),(3),(4)を検討した結果を実験すること。(5)までチャレンジした人は(2),(3),(4)の説明は簡単に記載するだけで良い。

プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。また、課題部門や自由部門であっても、複数の条件の組み合わせの中から最良のものを選ぶといった処理も求められる。最近の学生さんは複雑な組み合わせ問題がでてくると、すぐに訳も分からず「機械学習！」とか言い出す人も多いけど、基本中の基本をきちんと理解しましょう。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。

組み合わせ問題の基礎

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

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

#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 ;
}

import java.util.*;

public class Main {
    static 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 ) {
                        System.out.println( "a="+a+",b="+b+",c="+c ) ;
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        // 整数比の直角三角形の一覧を求める。
        integer_triangle( 100 ) ;
    }
}

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

4EIの情報構造論で説明するネタだけど、こういうアルゴリズムは、O(N³) のアルゴリズムという。

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

O(N²) のアルゴリズム

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 ) ;
         }
      }
   }
}

static 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)Math.sqrt( d ) ;
         // 斜辺Cの整数値を求め、改めて確認する。
         if ( c*c == d ) {
            System.out.println( "a="+a+",b="+b+",c="+c ) ;
         }
      }
   }
}

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

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

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

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

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

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

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

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

import java.util.* ;
import java.lang.System ;

public class Main {
    static void integer_triangle( int n ) {
        :
        // System.out.println( "a="+a+",b="+b+",c="+c ) ; // 関数内のprintfをコメントアウトしておくこと
        :
    }
    public static void main(String[] args) throws Exception {
        // 整数比の直角三角形の一覧を求める。
        long start = System.currentTimeMillis() ;
        for( int i = 0 ; i < 1000 ; i++ ) {
            integer_triangle( 100 ) ;
        }
        long end = System.currentTimeMillis() ;
        System.out.println( "time = " + end - start ) ;
    }
}

再帰プログラミング

組み合わせ問題では、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 課題の選択とする。

指定長を指定辺の組み合わせで作る(テーマ1)

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

配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
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 を [4|5,2,1,3,7]で作る。
　(1) 5=10-5 を [5|4,2,1,3,7]で作る。
　(2) 8=10-2 を [2|5,4,1,3,7]で作る。
　(3) 9=10-1 を [1|5,2,4,3,7]で作る。
　(4) 7=10-3 を [3|5,2,1,4,7]で作る。
　(5) 3=10-7 を [7|5,2,1,3,4]で作る。

そこで、ここまでの考えを、以下のようなプログラムで記述してみる。
# まだ再起呼び出しにはしていない。

// 指定されたデータを入れ替える。
void swap( int*a , int*b )
{  int x = *a ;
   *a = *b ;
   *b = x ;
}
// 配列のn番目以降を使って len の長さを作る再帰関数
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 ) ;
}

import java.util.*;

public class Main {
    // 配列のa番目とb番目を入れ替え
    static void swap( int array[] , int a , int b ) {
        int tmp = array[ a ] ;
        array[ a ] = array[ b ] ;
        array[ b ] = tmp ;
    }
    // 配列のn番目以降を使ってlenの長さを作る再帰関数
    static void check( int array[] , int len , int n ) {
        for( int i = n ; i < array.length ; i++ ) {
            swap( array , n , i ) ;
            for( int j = 0 ; j < array.length ; j++ )
                System.out.print( array[ j ] + "," ) ;
            System.out.println() ;
            System.out.println( "check( array , " + (len - array[ n ]) + " , " + (n+1) + " ) ;" ) ;
            // check( array , len - array[ n ] , n + 1 ) ;
            swap( array , n , i ) ;
        }
    }
    public static void main(String[] args) throws Exception {
        // 指定した長さを配列の組み合わせで作る。
        int array[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
        check( array , 10 , 0 ) ;
    }
}

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

// C言語版
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 ] ) ;
      }
   }
}

// Java版
static void check( int array[] , int len , int n ) {
    if ( len < 0 ) {
        // 指定した長さは作れなかった
        ;
    } else if ( len == 0 ) {
        for( int i = 0 ; i < n ; i++ )
            System.out.print( array[ i ] + "," ) ;
        System.out.println() ;
    } else {
        for( int i = n ; i < array.length ; i++ ) {
            swap( array , n , i ) ;
            //for( int j = 0 ; j < array.length ; j++ )
            //    System.out.print( array[ j ] + "," ) ;
            // System.out.println() ;
            // System.out.println( "check( array , " + (len - array[ n ]) + " , " + (n+1) + " ) ;" ) ;
            check( array , len - array[ n ] , n + 1 ) ;
            swap( array , n , i ) ;
        }
    }
}

(2) 少ない組み合わせの方がポイントが高い場合には、プログラムをどう変更する？
(3) 答えが１つだけで良い場合は、プログラムをどう変更する？
(4) このプログラムでは、冗長な答えがあるか？ないか？検討せよ。
(5) 前設問の整数比直角三角形のプログラムで、冗長な答えを削除するプログラムを作成せよ。

# レポートでは、(2),(3),(4)を検討した結果を実験すること。(5)までチャレンジした人は(2),(3),(4)の説明は簡単に記載するだけで良い。

別解

この問題の解き方には、もっとシンプルな書き方がある。2進数の各bitを、j番目の長さを使うか使わないかを表すこととする。

例えば、j=1番目,3番目を使うというのを、00013011)₂=5で表すこととする。すべての長さを使うのであれば、161514131211)₂=63 で表す。この2進数を1から63まで変化させれば、すべての組み合わせを試すことになる。

#include <stdio.h>

#define sizeofarray(A) (sizeof(A)/sizeof(A[0]))

int obj_len = 10 ;
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;

int main() {
  int l_max = 1 << sizeofarray( a ) ;
  for( int i = 1 ; i < l_max ; i++ ) {
    // i は a[j]を使うか使わないかを表す2進数                                   
    // i = 5 の場合                                                             
    // 5 = 0,0,0,1,0,1                                                          
    // a[] 7,3,1,2,5,4                                                          
    //           ^   ^ = 長さは6                                                
    int sum = 0 ;
    for( int j = 0 ; j < sizeofarray( a ) ; j++ ) {
      // iの2進数の各bitに対応する長さを加算                                    
      if ( (i & (1 << j)) != 0 )
        sum += a[ j ] ;
    }
    // 目的の長さを作れたので答えを表示                                         
    if ( sum == obj_len ) {
      printf( "0x%x : " , i ) ;
      for( int j = 0 ; j < sizeofarray( a ) ; j++ ) {
        if ( (i & (1 << j)) != 0 ) {
          printf( "%d " , a[ j ] ) ;
        }
      }
      printf( "\n" ) ;
    }
  }
  return 0 ;
}

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // 整数比の直角三角形の一覧を求める。
        int array[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
        int obj_len = 10 ;
        int l_max = 1 << array.length ;
        for( int i = 1 ; i < l_max ; i++ ) {
            int sum = 0 ;
            for( int j = 0 ; j < array.length ; j++ ) {
                if ( (i & (1 << j)) != 0 )
                    sum += array[ j ] ;
            }
            if ( sum == obj_len ) {
                System.out.println( Integer.toBinaryString( i ) ) ;
                for( int j = 0 ; j < array.length ; j++ ) {
                    if ( (i & (1 << j)) != 0 ) {
                        System.out.print( array[ j ] + "," ) ;
                    }
                }
                System.out.println() ;
            }
        }
    }
}

このプログラムは再帰呼び出しを含まないので、プログラムの挙動も解りやすい。しかし、j番目を使うか使わないのか…という2つの状態しかない組み合わせ問題でしか使えない。R3年度の競技部門のパズルように、絵のピースの↑,→,↓,←,回転右,回転左という6状態の場合は、使えない。

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 ) {
  // image: 塗りつぶす画像
  // x,y:   塗りつぶす場所
  // 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 ;
}

import java.util.*;

public class Main {
    // 文字列の要素を2次元配列に格納
    static void set_char2_string( char dest[][] , String src[] ) {
        for( int i = 0 ; i < src.length ; i++ ) {
            dest[ i ] = new char[ src[ i ].length() ] ;
            for( int j = 0 ; j < src[ i ].length() ; j++ )
                dest[ i ][ j ] = src[ i ].charAt( j ) ;
        }
    }
    // 2次元配列を出力
    static void print_image( char image[][] ) {
        for( int i = 0 ; i < image.length ; i++ ) {
            for( int j = 0 ; j < image[ i ].length ; j++ )
                System.out.print( image[ i ][ j ] ) ;
            System.out.println() ;
        }
    }
    // flood_fill
    static void flood_fill( char image[][] , int x , int y , char fill ) {
        if ( image[y][x] == ' ' ) {
            image[y][x] = fill ;
            // ここを考える
        }
    }
    public static void main(String[] args) throws Exception {
        // Your code here!
        String imageS1[] = {
            "*********" ,
            "*   *   *" ,
            "*   *   *" ,
            "*  *    *" ,
            "***   ***" ,
            "*    *  *" ,
            "*   *   *" ,
            "*   *   *" ,
            "*********" ,
        } ;
        char[][] image1 = new char[ imageS1.length ][] ;
        set_char2_string( image1 , imageS1 ) ;
        String imageS2[] = {
            "*********" ,
            "*   *   *" ,
            "*  **   *" ,
            "* **    *" ,
            "***   ***" ,
            "*    *  *" ,
            "*   *   *" ,
            "*   *   *" ,
            "*********" ,
        } ;
        char[][] image2 = new char[ imageS2.length ][] ;
        set_char2_string( image2 , imageS2 ) ;
        
        // flood_fill 実行
        print_image( image1 ) ;
        flood_fill( image1 , 4 , 4 , '#' ) ;
        print_image( image1 ) ;
    }
}

応用問題

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

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

レポート提出

レポートでは、指定長を辺の組み合わせで作るテーマか、Flood-fill のテーマのいずれかにて、以下の内容をまとめてレポートとして提出すること。

• • レポートの説明(自分の選んだテーマと自分なりの説明)
  • プログラムリスト
  • 動作確認の結果

インターネットを活用したプログラムを作成する場合、データを保存管理するためのデータベースと、データベースのデータを処理するためのプログラム言語が必要となってくる。今回の予備実験では、そのためにリレーショナルデータベースと、Webの動的なプログラム言語である PHP について説明する。

リレーショナル・データベース

データベースは、データを保存し、矛盾が発生しない様に管理してくれるシステムであり、インターネットで活用されている。

データを確実に保存し、矛盾なく扱うためには、本来複雑なプログラムが必要となる。この中で、データを表形式のテーブルを組み合わせて管理するシステムはリレーショナルデータベースと呼ばれる。リレーショナルデータベースでは、データの問い合わせなどの処理が簡単にできるように、SQL と呼ばれる言語を使って処理を行う。

大量のデータをインターネットの中で利用するためには、ネットワークを経由してデータの問い合わせが求められ、有名なデータベースシステムには、Oracle, MySQL などがある。今回の実験では、ネットワーク機能は持たないが簡単な手続きで使うことができる SQLite を使って説明する。

また、今回の予備実験では時間も限られることから、複数の表を組み合わせた SQL の処理については割愛する。

SQLの基本

リレーショナルデータベースでは、データの基本は表形式データであり、1つの表に相当するデータはテーブルと呼ぶ。

以下の様な名前・住所・年齢のデータがあったとすると、1人前のデータをレコードと呼び、name, addr, age といった属性はカラムと呼ぶ。

name	addr	age
t-saitoh	越前市	55	←レコード
sakamoto	福井市	50
murata	福井市	35
	↑カラム

データの型には、文字列型(char型,varchar型,text型)や、数値型(integer型,decimal型,real型)などがあり、create table 文にてカラムの型を定義する。

create table テーブルを作る

データベースの表を使う最初には、create table 文を実行する。C言語での struct 文をイメージすると解り易いかもしれないが、データはデータベースの中に永続的に保存されるので、システムを動かす最初に一度実行するだけで良い。

上記のような名前・住所・年齢のデータ構造であれば、次の様な create table 文を使う。

create table テーブル名 (
    カラム名1  型1 ,
    カラム名2  型2 
    ) ;
-- 例 --
create table PERSON (        -- テーブル名：PERSON
    name  varchar( 20 ) ,    -- 名前
    addr  varchar( 20 ) ,    -- 住所
    age   integer ,          -- 年齢
    primary key( name )      -- name はデータ検索のキーであり重複は許されない
    ) ;

これと同じ様な処理をC言語で書くのであれば、以下の様な構造体宣言と同じであろう。

struct PERSON {
    char name[ 20 ] ;    // 名前
    char addr[ 20 ] ;    // 住所
    int  age ;           // 年齢
} ;

drop table テーブルを消す

データベースは永続的に保存されるので、テーブル全体のデータが不要であれば、drop table 命令で、テーブル全体を消す。

drop table テーブル名 ;
-- 例 --
drop table PERSON ;

insert into レコードを追加

データベースに１レコードを保存するには、insert文を用いる。

insert into テーブル名 ( カラム名... ) values( 値... ) ;
-- 例 --
insert into PERSON ( name ,       addr ,    age )
            values ( 't-saitoh' , '越前市' , 55  ) ;
insert into PERSON ( name ,       addr ,    age )
            values ( 'sakamoto' , '福井市' , 50  ) ;
insert into PERSON ( name ,       addr ,    age )
            values ( 'murata' ,   '福井市' , 35  ) ;

delete レコードを消す

データベースのレコードを消すには、delete 文を用いる。条件を満たす複数のデータをまとめて消すことができる。

delete from テーブル名 where 条件 ;
-- 例 --
-- 40歳未満のデータを全て消す。 murata,福井市,35 が消える。
delete from PERSON
       where age < 40 ;

update レコードを更新

データベースのレコードを修正するには、update 文を用いる。条件を満たす複数のデータをまとめて修正することもできる。

update テーブル名 set カラム = 値 where 条件 ;
-- 例 --
-- 住所が越前市のレコードの年齢を 0 にする。
update PERSON set age = 0
       where addr == '越前市' ;

select データを探す

データベースの内容を参照するための命令が select 文。where を記載することで、特定の条件のデータだけを選択したり、特定のカラムだけを抽出することができる。

select カラム名 from テーブル名 where 条件 ;
-- 例 --
-- PERSON の全データを出力
select * from PERSON ;

-- PERSON の住所が福井市だけを選別し、名前と住所を抽出
select name,addr from PERSON
       where addr = '福井市' ;

-- PERSON の年齢の最高値を出力 (集約関数)
select max(age) from PERSON
       where addr = '福井市' ;

-- PERSON の年齢条件を満たす人数を数える (集約関数)
select count(name) from PERSON
       where age >= 50 ;

動的なプログラム言語とPHP

本来、Webサーバが作られた頃は、論文や研究用のデータを公開する物であったが、扱うデータが増えるにつれ、特定の論文や研究データの一覧を表示したり探したりという処理が求められた。こういった処理のためにWebページのアクセスを受けた時に処理を実行する CGI という機能があったが、これを発展させてできたプログラム言語が PHP である。

PHPでは、ページを表示するための HTML の中に <?php … ?> のといった開始タグ・終了タグの中に、ブラウザから送られてきたデータに合わせて、処理を行うPHPの命令を記述し、データを(一般的にはHTML形式で)表示することができる。基本文法は C 言語に似ているが、様々なデータを扱うために変数にはどのような型でも保存できるようになっている。

ブラウザからデータを送るためのform文

ブラウザで入力欄を作ったり選択肢を表示し、その結果を送るための HTML は、入力フォーム(form)と呼ぶ。

<form method="get" action="処理ページ" >

  <input type="text" name="変数名" />

  <input type="radio" name="変数名" value="値" />
  <input type="checkbox" name="変数名" value="値" />

  <textarea cols="横文字数" rows="行数"></textarea>

  <select name="変数名">
    <option value="値1">表示1</option>
    <option value="値2">表示2</option>
  </select>
  <input type="submit" value="実行ボタンに表示する内容" />
</form>

formでは、入力する項目に変数名の名前を付け、action=”” で示したページにデータを送る。

PHPのプログラムの基本

PHPのプログラムは、外見は一般的に HTML ファイルであり、途中で <?php のタグからは、?> までの範囲が、PHP で処理が行われる。PHP のプログラムで print が実行されると、その場所に print 内容が書かれているような HTML ファイルが生成され、ブラウザで表示される。

PHP の中で変数は、$ で始まり、型宣言は基本的に不要である。

文字データを連結する場合は、“.” 演算子を使う。ダブルクオテーション”…”で囲まれた文字列の中の $名前 の部分は、変数名として扱われ、変数名の内容に置き換えられる。

HTMLのform文の action 属性で示された php であれば、PHPの中で送られてきた値を $_GET[‘変数名’] (method=”get”の場合)、 $_POST[‘変数名’] (method=”post”の場合)、または $_REQUEST[‘変数名’] (method=”get” or “post”) で参照できる。

((( sample.php )))
<html>
   <head>
      <title>sample.php</title>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   </head>
   <body>
      <form action="sample.php" method="POST">
         <input name="A" type="text" />     <!-- 変数 $A -->
         ＋
         <input name="B" type="text" />     <!-- 変数 $B -->
         ＝
         <?php 
            ini_set( 'error_reporting' , E_WARNING ) ;
            if ( $_REQUEST[ "A" ] != "" && $_REQUEST[ "B" ] != "" ) {
               print $_REQUEST[ "A" ] + $_REQUEST[ "B" ] ;
            } else {
               print "<INPUT TYPE=submit>" ;
            }
         ?>
      </form>
   </body>
</html>

PHPでデータベースを扱う

SQLのデータベースを、プログラム言語の中で扱う場合は、その記述も色々である。PHPでは以下の様にSQLを扱う。

((( survey-init.php )))
<html>
   <head>
      <title>survey_init.php</title>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   </head>
   <body>
      <?php
         // デバッグ用にエラー警告を表示する
         ini_set( 'error_reporting' , E_WARNING ) ;
         // データベースに接続する
         $data_dir = "../public_data" ;
         $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ;
         // データベースを初期化する
         $init_sql = "drop table if exists Survey ;"
                   . "create table Survey ("
                   . "  uid  varchar( 20 ) ,"
                   . "  item varchar( 10 )"
                   . ") ;"
                   . "insert into Survey ( uid , item ) values ( 't-saitoh' , '猫'        ) ;"
                   . "insert into Survey ( uid , item ) values ( 'tomoko' ,   'ケーキ'     ) ;"
                   . "insert into Survey ( uid , item ) values ( 'mitsuki' ,  'ボードゲーム' ) ;"
                   ;
         if ( $dbh->exec( $init_sql ) < 0 ) {
            print "Error: $init_sql" ;
         }
         // データベースの表形式を読み出し、表形式で出力する。
         print "<table border='1'>\n" ;
         print "<tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ;
         $select_sql = "select uid,item from Survey ;" ;
         foreach( $dbh->query( $select_sql ) as list( $uid , $item ) ) {
            print "<tr><td>$uid</td><td>$item</td></tr>\n" ;
         }
         print "<table>\n" ;

         // データベースの単一データを取り出す
         $count_sql = "select count(item) from Survey where item = 'ケーキ' ;" ;
         print $dbh->query( $count_sql )->fetchColumn() ;
      ?>
   </body>
</html>

PHPの主要なSQL関数(PDO)

$dbh = new PDO(…) ;	データベースに接続するハンドラを取得。
$dbh->exec( “create…” ) ;	データベースでSQLを実行。
$dbh->query( “select…” ) ;	データベースに問い合わせ。「1レコードに対応した配列」が全データだけ繰り返す、2次元配列を返す。
$dbh->query( “…” )->fetchColumn()	結果が１つだけの問い合わせ。集約関数の結果を参照する場合に用いる。

練習問題(1)

• 上記の survey-init.php の select 文の部分を編集し、色々なデータ検索を試してみよ。

入力フォームのデータをデータベースに書き込む

((( survey-vote.php )))
<?php
    // エラー警告を表示                                                                                                     
    ini_set( 'error_reporting' , E_WARNING ) ;

    // form から送られてきた変数を保存                                                                                      
    $uid  = $_REQUEST[ "uid" ] ;
    $item = $_REQUEST[ "item" ] ;

    // データベースに接続する                                                                                               
    $data_dir = "../public_data" ;
    $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ;

    // データベースに項目を追加する                                                                                         
    if ( $uid != "" && $item != "" ) {
        $insert_sql = sprintf( "insert into Survey( uid , item ) values ( %s , %s ) ;" ,
                               $dbh->quote( $uid ) , $dbh->quote( $item ) ) ;
        $dbh->exec( $insert_sql ) ;

        // reload処理で追記しないためページを強制的に再表示させる                                                           
        header( "Location: survey-vote.php" ) ;
    }
?>
<html>
  <head>
    <title>survey_vote.php</title>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  </head>
  <body>
    <form method="get" action="survey-vote.php">
       名前：   <input type="text" name="uid" />
       好きな物：<input type="text" name="item" />
       <input type="submit" value="投票" />
    </form>
    <?php
      // データベースの表形式を読み出し、表形式で出力する。                                                                   
      print "<table border='1'>\n" ;
      print "  <tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ;

      $select_sql = "select uid,item from Survey ;" ;
      foreach( $dbh->query( $select_sql ) as list( $t_uid , $t_item ) ) {
          print "  <tr><td>$t_uid</td><td>$t_item</td></tr>\n" ;
      }
      print "</table>\n" ;
    ?>
  </body>
</html>

練習問題(2)

• 上記の survey-vote.php のプログラムを編集し色々な入力方法・出力方法を試してみよ。
  • 例えば、入力の item 選択に select や ラジオボタン フォームを使う。
  • 例えば、出力結果で、item の投票結果を、棒グラフで出力する。

プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。また、課題部門や自由部門であっても、複数の条件の組み合わせの中から最良のものを選ぶといった処理も求められる。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。

組み合わせ問題の基礎

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

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

#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回のループで無駄な処理が多い。

4EIの情報構造論で説明するネタだけど、こういうアルゴリズムは、O(N³) のアルゴリズムという。

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

O(N²) のアルゴリズム

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 c = sqrt( (double)(i*i) ) ;” を計算してみて、 異なる値が求まることはあるか？ 多少の計算誤差があっても正しく処理が行われるにはどうすればいいか、考えてみよう。

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

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

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

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

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 課題の選択とする。

指定長を指定辺の組み合わせで作る(テーマ1)

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

配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
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 を [4|5,2,1,3,7]で作る。
　(1) 5=10-5 を [5|4,2,1,3,7]で作る。
　(2) 8=10-2 を [2|5,4,1,3,7]で作る。
　(3) 9=10-1 を [1|5,2,4,3,7]で作る。
　(4) 7=10-3 を [3|5,2,1,4,7]で作る。
　(5) 3=10-7 を [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) 答えが１つだけで良い場合は、プログラムをどう変更する？
(4) このプログラムでは、冗長な答えがあるか？ないか？検討せよ。
(5) 前設問の整数比直角三角形のプログラムで、冗長な答えを削除するプログラムを作成せよ。

# レポートでは、(2),(3),(4)を検討した結果を実験すること。(5)までチャレンジした人は(2),(3),(4)の説明は簡単に記載するだけで良い。

別解

この問題の解き方には、もっとシンプルな書き方がある。2進数の各bitを、j番目の長さを使うか使わないかを表すこととする。

例えば、j=1番目,3番目を使うというのを、00013011)₂=5で表すこととする。すべての長さを使うのであれば、161514131211)₂=63 で表す。この2進数を1から63まで変化させれば、すべての組み合わせを試すことになる。

#include <stdio.h>

#define sizeofarray(A) (sizeof(A)/sizeof(A[0]))

int obj_len = 10 ;
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;

int main() {
  int l_max = 1 << sizeofarray( a ) ;
  for( int i = 1 ; i < l_max ; i++ ) {
    // i は a[j]を使うか使わないかを表す2進数                                   
    // i = 5 の場合                                                             
    // 5 = 0,0,0,1,0,1                                                          
    // a[] 7,3,1,2,5,4                                                          
    //           ^   ^ = 長さは6                                                
    int sum = 0 ;
    for( int j = 0 ; j < sizeofarray( a ) ; j++ ) {
      // iの2進数の各bitに対応する長さを加算                                    
      if ( (i & (1 << j)) != 0 )
        sum += a[ j ] ;
    }
    // 目的の長さを作れたので答えを表示                                         
    if ( sum == obj_len ) {
      printf( "0x%x : " , i ) ;
      for( int j = 0 ; j < sizeofarray( a ) ; j++ ) {
        if ( (i & (1 << j)) != 0 ) {
          printf( "%d " , a[ j ] ) ;
        }
      }
      printf( "\n" ) ;
    }
  }
  return 0 ;
}

このプログラムは再帰呼び出しを含まないので、プログラムの挙動も解りやすい。しかし、j番目を使うか使わないのか…という2つの状態しかない組み合わせ問題でしか使えない。R3年度の競技部門のパズルように、絵のピースの↑,→,↓,←,回転右,回転左という6状態の場合は、使えない。

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 ) {
  // image: 塗りつぶす画像
  // x,y:   塗りつぶす場所
  // 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 のプログラムの説明のアルゴリズムでは、左図黒のような斜めに並んだブロックは、境界として通り抜けられないようにつくられている。

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

レポート提出

レポートでは、指定長を辺の組み合わせで作るテーマか、Flood-fill のテーマのいずれかにて、以下の内容をまとめてレポートとして提出すること。

• • レポートの説明(自分の選んだテーマと自分なりの説明)
  • プログラムリスト
  • 動作確認の結果

インターネットを活用したプログラムを作成する場合、データを保存管理するためのデータベースと、データベースのデータを処理するためのプログラム言語が必要となってくる。今回の予備実験では、そのためにリレーショナルデータベースと、Webの動的なプログラム言語である PHP について説明する。

リレーショナル・データベース

データベースは、データを保存し、矛盾が発生しない様に管理してくれるシステムであり、インターネットで活用されている。

データを確実に保存し、矛盾なく扱うためには、本来複雑なプログラムが必要となる。この中で、データを表形式のテーブルを組み合わせて管理するシステムはリレーショナルデータベースと呼ばれる。リレーショナルデータベースでは、データの問い合わせなどの処理が簡単にできるように、SQL と呼ばれる言語を使って処理を行う。

大量のデータをインターネットの中で利用するためには、ネットワークを経由してデータの問い合わせが求められ、有名なデータベースシステムには、Oracle, MySQL などがある。今回の実験では、ネットワーク機能は持たないが簡単な手続きで使うことができる SQLite を使って説明する。

また、今回の予備実験では時間も限られることから、複数の表を組み合わせた SQL の処理については割愛する。

SQLの基本

リレーショナルデータベースでは、データの基本は表形式データであり、1つの表に相当するデータはテーブルと呼ぶ。

以下の様な名前・住所・年齢のデータがあったとすると、1人前のデータをレコードと呼び、name, addr, age といった属性はカラムと呼ぶ。

name	addr	age
t-saitoh	越前市	55	←レコード
sakamoto	福井市	50
murata	福井市	35
	↑カラム

データの型には、文字列型(char型,varchar型,text型)や、数値型(integer型,decimal型,real型)などがあり、create table 文にてカラムの型を定義する。

create table テーブルを作る

データベースの表を使う最初には、create table 文を実行する。C言語での struct 文をイメージすると解り易いかもしれないが、データはデータベースの中に永続的に保存されるので、システムを動かす最初に一度実行するだけで良い。

上記のような名前・住所・年齢のデータ構造であれば、次の様な create table 文を使う。

create table テーブル名 (
    カラム名1  型1 ,
    カラム名2  型2 
    ) ;
-- 例 --
create table PERSON (        -- テーブル名：PERSON
    name  varchar( 20 ) ,    -- 名前
    addr  varchar( 20 ) ,    -- 住所
    age   integer ,          -- 年齢
    primary key( name )      -- name はデータ検索のキーであり重複は許されない
    ) ;

これと同じ様な処理をC言語で書くのであれば、以下の様な構造体宣言と同じであろう。

struct PERSON {
    char name[ 20 ] ;    // 名前
    char addr[ 20 ] ;    // 住所
    int  age ;           // 年齢
} ;

drop table テーブルを消す

データベースは永続的に保存されるので、テーブル全体のデータが不要であれば、drop table 命令で、テーブル全体を消す。

drop table テーブル名 ;
-- 例 --
drop table PERSON ;

insert into レコードを追加

データベースに１レコードを保存するには、insert文を用いる。

insert into テーブル名 ( カラム名... ) values( 値... ) ;
-- 例 --
insert into PERSON ( name ,       addr ,    age )
            values ( 't-saitoh' , '越前市' , 55  ) ;
insert into PERSON ( name ,       addr ,    age )
            values ( 'sakamoto' , '福井市' , 50  ) ;
insert into PERSON ( name ,       addr ,    age )
            values ( 'murata' ,   '福井市' , 35  ) ;

delete レコードを消す

データベースのレコードを消すには、delete 文を用いる。条件を満たす複数のデータをまとめて消すことができる。

delete from テーブル名 where 条件 ;
-- 例 --
-- 40歳未満のデータを全て消す。 murata,福井市,35 が消える。
delete from PERSON
       where age < 40 ;

update レコードを更新

データベースのレコードを修正するには、update 文を用いる。条件を満たす複数のデータをまとめて修正することもできる。

update テーブル名 set カラム = 値 where 条件 ;
-- 例 --
-- 住所が越前市のレコードの年齢を 0 にする。
update PERSON set age = 0
       where addr == '越前市' ;

select データを探す

データベースの内容を参照するための命令が select 文。where を記載することで、特定の条件のデータだけを選択したり、特定のカラムだけを抽出することができる。

select カラム名 from テーブル名 where 条件 ;
-- 例 --
-- PERSON の全データを出力
select * from PERSON ;

-- PERSON の住所が福井市だけを選別し、名前と住所を抽出
select name,addr from PERSON
       where addr = '福井市' ;

-- PERSON の年齢の最高値を出力 (集約関数)
select max(age) from PERSON
       where addr = '福井市' ;

-- PERSON の年齢条件を満たす人数を数える (集約関数)
select count(name) from PERSON
       where age >= 50 ;

動的なプログラム言語とPHP

本来、Webサーバが作られた頃は、論文や研究用のデータを公開する物であったが、扱うデータが増えるにつれ、特定の論文や研究データの一覧を表示したり探したりという処理が求められた。こういった処理のためにWebページのアクセスを受けた時に処理を実行する CGI という機能があったが、これを発展させてできたプログラム言語が PHP である。

PHPでは、ページを表示するための HTML の中に <?php … ?> のといった開始タグ・終了タグの中に、ブラウザから送られてきたデータに合わせて、処理を行うPHPの命令を記述し、データを(一般的にはHTML形式で)表示することができる。基本文法は C 言語に似ているが、様々なデータを扱うために変数にはどのような型でも保存できるようになっている。

ブラウザからデータを送るためのform文

ブラウザで入力欄を作ったり選択肢を表示し、その結果を送るための HTML は、入力フォーム(form)と呼ぶ。

<form method="get" action="処理ページ" >

  <input type="text" name="変数名" />

  <input type="radio" name="変数名" value="値" />
  <input type="checkbox" name="変数名" value="値" />

  <textarea cols="横文字数" rows="行数"></textarea>

  <select name="変数名">
    <option value="値1">表示1</option>
    <option value="値2">表示2</option>
  </select>
  <input type="submit" value="実行ボタンに表示する内容" />
</form>

formでは、入力する項目に変数名の名前を付け、action=”” で示したページにデータを送る。

PHPのプログラムの基本

PHPのプログラムは、外見は一般的に HTML ファイルであり、途中で <?php のタグからは、?> までの範囲が、PHP で処理が行われる。PHP のプログラムで print が実行されると、その場所に print 内容が書かれているような HTML ファイルが生成され、ブラウザで表示される。

PHP の中で変数は、$ で始まり、型宣言は基本的に不要である。

文字データを連結する場合は、”.” 演算子を使う。ダブルクオテーション”…”で囲まれた文字列の中の $名前 の部分は、変数名として扱われ、変数名の内容に置き換えられる。

HTMLのform文の action 属性で示された php であれば、PHPの中で送られてきた値を $_GET[‘変数名’] (method=”get”の場合)、 $_POST[‘変数名’] (method=”post”の場合)、または $_REQUEST[‘変数名’] (method=”get” or “post”) で参照できる。

((( sample.php )))
<html>
   <head>
      <title>sample.php</title>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   </head>
   <body>
      <form action="sample.php" method="POST">
         <input name="A" type="text" />     <!-- 変数 $A -->
         ＋
         <input name="B" type="text" />     <!-- 変数 $B -->
         ＝
         <?php 
            ini_set( 'error_reporting' , E_WARNING ) ;
            if ( $_REQUEST[ "A" ] != "" && $_REQUEST[ "B" ] != "" ) {
               print $_REQUEST[ "A" ] + $_REQUEST[ "B" ] ;
            } else {
               print "<INPUT TYPE=submit>" ;
            }
         ?>
      </form>
   </body>
</html>

PHPでデータベースを扱う

SQLのデータベースを、プログラム言語の中で扱う場合は、その記述も色々である。PHPでは以下の様にSQLを扱う。

((( survey-init.php )))
<html>
   <head>
      <title>survey_init.php</title>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   </head>
   <body>
      <?php
         // デバッグ用にエラー警告を表示する
         ini_set( 'error_reporting' , E_WARNING ) ;
         // データベースに接続する
         $data_dir = "../public_data" ;
         $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ;
         // データベースを初期化する
         $init_sql = "drop table if exists Survey ;"
                   . "create table Survey ("
                   . "  uid  varchar( 20 ) ,"
                   . "  item varchar( 10 )"
                   . ") ;"
                   . "insert into Survey ( uid , item ) values ( 't-saitoh' , '猫'        ) ;"
                   . "insert into Survey ( uid , item ) values ( 'tomoko' ,   'ケーキ'     ) ;"
                   . "insert into Survey ( uid , item ) values ( 'mitsuki' ,  'ボードゲーム' ) ;"
                   ;
         if ( $dbh->exec( $init_sql ) < 0 ) {
            print "Error: $init_sql" ;
         }
         // データベースの表形式を読み出し、表形式で出力する。
         print "<table border='1'>\n" ;
         print "<tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ;
         $select_sql = "select uid,item from Survey ;" ;
         foreach( $dbh->query( $select_sql ) as list( $uid , $item ) ) {
            print "<tr><td>$uid</td><td>$item</td></tr>\n" ;
         }
         print "<table>\n" ;

         // データベースの単一データを取り出す
         $count_sql = "select count(item) from Survey where item = 'ケーキ' ;" ;
         print $dbh->query( $count_sql )->fetchColumn() ;
      ?>
   </body>
</html>

PHPの主要なSQL関数(PDO)

$dbh = new PDO(…) ;	データベースに接続するハンドラを取得。
$dbh->exec( “create…” ) ;	データベースでSQLを実行。
$dbh->query( “select…” ) ;	データベースに問い合わせ。「1レコードに対応した配列」が全データだけ繰り返す、2次元配列を返す。
$dbh->query( “…” )->fetchColumn()	結果が１つだけの問い合わせ。集約関数の結果を参照する場合に用いる。

練習問題(1)

• 上記の survey-init.php の select 文の部分を編集し、色々なデータ検索を試してみよ。

入力フォームのデータをデータベースに書き込む

((( survey-vote.php )))
<?php
    // エラー警告を表示                                                                                                     
    ini_set( 'error_reporting' , E_WARNING ) ;

    // form から送られてきた変数を保存                                                                                      
    $uid  = $_REQUEST[ "uid" ] ;
    $item = $_REQUEST[ "item" ] ;

    // データベースに接続する                                                                                               
    $data_dir = "../public_data" ;
    $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ;

    // データベースに項目を追加する                                                                                         
    if ( $uid != "" && $item != "" ) {
        $insert_sql = sprintf( "insert into Survey( uid , item ) values ( %s , %s ) ;" ,
                               $dbh->quote( $uid ) , $dbh->quote( $item ) ) ;
        $dbh->exec( $insert_sql ) ;

        // reload処理で追記しないためページを強制的に再表示させる                                                           
        header( "Location: survey-vote.php" ) ;
    }
?>
<html>
  <head>
    <title>survey_vote.php</title>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  </head>
  <body>
    <form method="get" action="survey-vote.php">
       名前：   <input type="text" name="uid" />
       好きな物：<input type="text" name="item" />
       <input type="submit" value="投票" />
    </form>
    <?php
      // データベースの表形式を読み出し、表形式で出力する。                                                                   
      print "<table border='1'>\n" ;
      print "  <tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ;

      $select_sql = "select uid,item from Survey ;" ;
      foreach( $dbh->query( $select_sql ) as list( $t_uid , $t_item ) ) {
          print "  <tr><td>$t_uid</td><td>$t_item</td></tr>\n" ;
      }
      print "</table>\n" ;
    ?>
  </body>
</html>

練習問題(2)

• 上記の survey-vote.php のプログラムを編集し色々な入力方法・出力方法を試してみよ。
  • 例えば、入力の item 選択に select や ラジオボタン フォームを使う。
  • 例えば、出力結果で、item の投票結果を、棒グラフで出力する。