■再帰プログラミング■

演習問題4

まずは関数の練習からで，前回の作成した素数を定義どおり求める方法とエラトステネスのふるいをそれぞれ関数とせよ．関数の仕様は，素数かどうか調べる最大の数maxを引数にとり，調べた結果最大の素数を返値とする．それぞれ次のとおりとする．途中の素数は画面に表示しなくてよい．

public static int sosuu(int max)
public static int eratosthenes(int max)

また，キーボードから調べる最大の数を入力してもらう関数，inputMaxを作成せよ．

public static int inputMax()

この三つの関数を，main関数から呼び出して次の動作をするプログラムを作成する．

最大の数を入力してください．5000 ←キーボード入力
定義どおりの方法で調べた最大素数は xxxx
実行時間はyyyyyミリ秒
エラトステネスのふるいで調べた最大素数は xxxx
実行時間はzzzzzミリ秒
最大の数を入力してください．

演習問題5

次に基本テクニックのひとつ，再帰呼出プログラムを練習する．

再帰呼出とは

再帰呼出とは，ある関数が自分自身を呼び出すことをいう．例えば次のようにfuncAの中でfuncAを呼び出す．

public static int funcA(int param)
{
  int a;
  if(param != 終了条件)
  {
    a = funcA(param+10);
    a+=param;
  }
  else
  {
    a=0;
  }
  return a;
}

しっかり終了条件を考えて，条件を満たさない場合には再帰をせずにそこで止める必要がある．そうしないと無限に再帰されてしまう．

塗りつぶしルーチンとは

この再帰は，使いどころが難しいが，うまく使えば効果的である．画像処理では，塗りつぶしルーチンによく用いられる．例えば9×9の白黒二値画像があったとする．このまんなかの(5,5)から塗りつぶしを行う．塗りつぶしとはその座標に連結している黒画素を抜き出す操作で，この結果次の画像が出力されるはずである．

□■■□□□□□□
■■□■■■■■□
□□□□■□■□□
■■□□■■■□□
■□□□■■□□□
□□□□□■□□□
□■■■■■■□■
□■□□□□□■□
■□□□□□□■□

□□□□□□□□□
□□□■■■■■□
□□□□■□■□□
□□□□■■■□□
□□□□■■□□□
□□□□□■□□□
□■■■■■■□□
□■□□□□□□□
□□□□□□□□□

ここで，連結しているかどうかは上下左右の4方向だけで判定する．(これを4連結と呼ぶ．ちなみに斜めも含めて判定する場合には，8連結と呼ぶ．)

再帰を使わずにこれを実現しようとすると，結構大変である．

塗りつぶしルーチンのヒント

これを再帰呼出を利用して実現するには，次のようなクラス変数と関数を用意するものとする．

static boolean [][] input;                      //入力画像
static boolean [][] output;                     //出力画像
public static void printImage(boolean [][] image) //画像表示関数
public static int fill(int x, int y)        //塗りつぶし関数

入力画像は上記の画像の白をfalse，黒をtrueとしてあらかじめ初期化しておく．出力画像はすべてfalseでよい．

関数printImageは，渡された引数imageを画面に表示する関数である．次のように，入力・出力画像を表示させることを想定している．この結果，上記のような画像表示ができればよい．

printImage(input);
printImage(output);

関数fillは，座標(x,y)から塗りつぶしを始めて，塗りつぶした画素の数を返すとする．ただし，返値だけでなく呼び出された時の画像inputの(x,y)座標を調べて，もしも(x,y)座標が連結していればoutputの(x,y)にtrue,していなければfalseを出力する．

関数fillの中身はだいだい次のような感じになる．

public static int fill(int x, int y)
{
   座標(x,y)がinputの範囲外であればダメ
   inputの座標(x,y)を調べる．trueでなければダメ
   outputの座標(x,y)を調べる．すでに出力があればダメ
　　　失敗した場合は，返値は0;
　　そうでないならOK
     OKなのでoutputの(x,y)をtrueに置き換える．
　　　自分の上下左右を調べる．
       つまり，int left = fill(x-1, y);
              int right = fill(x+1,y);
              int up = fill(x,y-1);
              int down = fill(x,y+1);
       返値は，left+right+up+down+1; //+1は自分自身の1画素分
}

たったこれだけで，複雑な塗りつぶしルーチンを記述できてしまう．

再帰プログラミングのポイントは，作成中の関数が予定どおりに動作できると思い込んでプログラムすることである．この場合，fillがちゃんと動作して，ちゃんと塗りつぶしを行って面積も正しく返してくれることが期待できれば，このように書くことができる．

課題内容

このプログラムを全体(main関数なども含めて)を完成させて動作させよ．