さめがめを作る(その 3)

このページでは、次のことを考察します。

• ターゲットとなるセルに対して、そのセルの隣(上下左右)に位置するセルが自分と同じ値をもつかどうかを調べる。

ただ同じ値かどうかを調べるだけではありません。もし、隣接するセルが自分と同じ値を持っていたなら「その隣のセルに対しても」同様な操作を繰り返します。

まず結論から言ってしまいますが、ここでは、それらのセルを見つけ出す為に再帰関数を使用します^*1 そこで、まずは簡単に再帰関数とはどういうものかについてのおさらいをします。

再帰関数というのは、自身の中で再び自分自身を呼び出す関数の事を言います。再帰関数を理解するうえで、とても大切な事は、再帰関数とは基本部分（ベースケース）と再帰部分の 2 つから構成されているということを理解する事です。

再帰関数は「自身をその中で再び呼び出す」ということを強く強調され説明されますが、どのような条件であれ自分自身を常に（どんな時でも）呼び出しているわけでは「ありません」。もし再帰関数が常にその中で自身を呼び出しているなら、その関数は一生処理を終えることがありません。

再帰関数は再帰呼び出しをする再帰部分と、再帰呼び出しを「しない」基本部分(ベースケース)で構成されています。基本部分とは関数の「止め時はいつか」ということ、すなわち、どういう条件であれば再帰呼び出しをしないかを決める部分です。簡単な例をあげましょう。

function Fact(x: Integer): Integer;
begin
  if x = 0 then
    Result := 1
  else
    Result := x * Fact(x-1);
end;

Fact は、階乗を求める関数です。この関数の再帰部分とはどのことを指しますか?自身を再び呼び出している部分ですから、

Result := x * Fact(x-1);

が相当します。では、基本部分はどこでしょうか?再帰呼び出しを「しないで」処理を行っている部分が相当しますから、この場合は、

Result := 1;

がそれに当たります。再帰関数には、この 2 つの部分で構成されていることを認識することが大切です。

では、さっそくプログラムを見ていきます。

Unit1

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Grids, Unit2;

const
  MAX_COL_COUNT = 7;
  MAX_ROW_COUNT = 5;
  MAX_CELL_COUNT = MAX_COL_COUNT*MAX_ROW_COUNT;

  DOES_NOT_EXIST_CELL = -1;
  
type
  TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    Button1: TButton;
    Memo1: TMemo;
    Button2: TButton;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private 宣言 }
    FCells: array[1..MAX_CELL_COUNT] of TCell;
    function GetEastIndex(x: Integer): Integer;
    function GetWestIndex(x: Integer): Integer;
    function GetNorthIndex(x: Integer): Integer;
    function GetSouthIndex(x: Integer): Integer;
    procedure DisplayCell;
    procedure InitializeCell;
    procedure SearchSameValue(CellIndex, FindValue: Integer);
    procedure SearchCell;
  public
    { Public 宣言 }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

{ TForm1 }

function TForm1.GetEastIndex(x: Integer): Integer;
begin
  if (x mod MAX_COL_COUNT) = 0 then
    Result := DOES_NOT_EXIST_CELL
  else
    Result := x+1;
end;

function TForm1.GetWestIndex(x: Integer): Integer;
begin
  if (x mod MAX_COL_COUNT) = 1 then
    Result := DOES_NOT_EXIST_CELL
  else
    Result := x-1;
end;

function TForm1.GetNorthIndex(x: Integer): Integer;
begin
  if (x-MAX_COL_COUNT) < 1 then
    Result := DOES_NOT_EXIST_CELL
  else
    Result := x-MAX_COL_COUNT;
end;

function TForm1.GetSouthIndex(x: Integer): Integer;
begin
  if (x+MAX_COL_COUNT) > MAX_CELL_COUNT then
    Result := DOES_NOT_EXIST_CELL
  else
    Result := x+MAX_COL_COUNT;
end;

procedure TForm1.DisplayCell;
var
  i, j, Idx: Integer;
begin
  for i := 0 to MAX_ROW_COUNT-1 do
    for j := 0 to MAX_COL_COUNT-1 do begin
      Idx := (j+1) + MAX_COL_COUNT*i;
      StringGrid1.Cells[j, i] := Format('%d: %d', [Idx, FCells[Idx].Num]);
    end;
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  i: Integer;
begin
  Randomize;
  StringGrid1.ColCount := MAX_COL_COUNT;
  StringGrid1.RowCount := MAX_ROW_COUNT;

  for i := Low(FCells) to High(FCells) do
    FCells[i] := TCell.Create(Random(3));

  DisplayCell;

  Button1.Caption := 'Initialize';
  Button2.Caption := 'DeleteCell';
  Memo1.ScrollBars := ssVertical;
end;

procedure TForm1.FormDestroy(Sender: TObject);
var
  i: Integer;
begin
  for i := Low(FCells) to High(FCells) do
    FCells[i].Free;
end;

procedure TForm1.InitializeCell;
var
  i: Integer;
begin
  for i := Low(FCells) to High(FCells) do
    FCells[i].Num := Random(3);
  DisplayCell;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  InitializeCell;
end;

procedure TForm1.SearchSameValue(CellIndex, FindValue: Integer);

  function IsSameValue(Idx: Integer): Boolean;
  begin
    Result := (Idx <> DOES_NOT_EXIST_CELL) and (FCells[Idx].Num = FindValue);
  end;

  function NotYetKnowingCell(Idx: Integer): Boolean;
  begin
    Result := false;
    if not FCells[Idx].DeleteMe then begin
      Result := true;
      FCells[Idx].DeleteMe := true;
    end;
  end;

var
  Idx: Integer;
begin
  // 隣のセルが自分のセルの値と同じかどうかをしらべる。

  Idx := GetWestIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetNorthIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetEastIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetSouthIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  i: Integer;
begin
  for i := Low(FCells) to High(FCells) do
    FCells[i].DeleteMe := false;

  Memo1.Clear;
  Memo1.Lines.Add('消去されるべきセル:');

  SearchCell;

  for i := Low(FCells) to High(FCells) do
    if FCells[i].DeleteMe then
      Memo1.Lines.Add(Format('%2d: %d', [i, FCells[i].Num]));
end;

procedure TForm1.SearchCell;

  function GetCellIndex(Row, Col: Integer): Integer;
  begin
    Result := (Col+1) + MAX_COL_COUNT*Row;
  end;

var
  Idx: Integer;
begin
  Idx := GetCellIndex(StringGrid1.Row, StringGrid1.Col);
  SearchSameValue(Idx, FCells[Idx].Num);
end;

end.

Unit2

unit Unit2;

interface

type
  TCell = class
  private
    FNum: Integer;
    FDeleteMe: Boolean;
  public
    constructor Create(Num: Integer);
    property Num: Integer read FNum write FNum;
    property DeleteMe: Boolean read FDeleteMe write FDeleteMe;
  end;

implementation

{ TCell }

constructor TCell.Create(Num: Integer);
begin
  Fnum := Num;
end;

end.

コードの大部分は「さめがめを作る(その 2)」と同じです。隣接したセルが同じであるセルを見つけ出す部分のコードを見ていきましょう。

procedure TForm1.Button2Click(Sender: TObject);
var
  i: Integer;
begin
  for i := Low(FCell) to High(FCell) do
    FCells[i].DeleteMe := false;

  Memo1.Clear;
  Memo1.Lines.Add('消去されるべきセル:');

  SearchCell;

  for i := Low(FCell) to High(FCell) do
    if FCells[i].DeleteMe then
      Memo1.Lines.Add(Format('%2d: %d', [i, FCells[i].Num]));
end;

ボタンを押すと、TMemo に消去されるべきセルの一覧が表示されるはずです。その一覧に表示されたセルとは、StringGrid1 で現在選択中のセルと同じ値を保持していて、なお且つ、そのセルと（異なる値を持つセルを跨ぐことなく）繋がっているセルであることが分かります。上のコードを見ると、それらのセルだけ DeleteMe プロパティが true になっています。これの設定は、SearchCell 関数(の中で呼び出す SearchSameValue 関数)が行います。

procedure TForm1.SearchCell;

  function GetCellIndex(Row, Col: Integer): Integer;
  begin
    Result := (Col+1) + MAX_COL_COUNT*Row;
  end;

var
  Idx: Integer;
begin
  Idx := GetCellIndex(StringGrid1.Row, StringGrid1.Col);
  SearchSameValue(Idx, FCells[Idx].Num);
end;

procedure TForm1.SearchSameValue(CellIndex, FindValue: Integer);

  function IsSameValue(Idx: Integer): Boolean;
  begin
    Result := (Idx <> DOES_NOT_EXIST_CELL) and (FCells[Idx].Num = FindValue);
  end;

  function NotYetKnowingCell(Idx: Integer): Boolean;
  begin
    Result := false;
    if not FCells[Idx].DeleteMe then begin
      Result := true;
      FCells[Idx].DeleteMe := true;
    end;
  end;

var
  Idx: Integer;
begin
  // 隣のセルが自分のセルの値と同じかどうかをしらべる。
  
  Idx := GetWestIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetNorthIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetEastIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetSouthIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);
end;

SearchSameValue 関数は再帰関数です。再帰部分は IsSameValue 関数と NotYetKnowingCell 関数が共に true を返した時に呼び出されます。基本部分はどこでしょうか? 基本部分は、IsSameValue 関数又は NotYetKnowingCell 関数(を呼び出している箇所全て)が false を返した場合が相当します。コードとして直接表に現れていませんが、「何もしない」ということも処理の一つであると考えれば納得できるはずです。

SearchSameValue 関数が行うことを文章で表現すれば、こうなります。

自分と隣り合っているセルがあるなら、そのセルが保持している値を調べる。その値が自分が持っている値と同じであるなら、「その同じ値を持っているセルに対して」同様の処理を実行する(これを「文章1」とおきます)。

処理の止め時はいつでしょうか。上の文章には止め時が書いてありません。ですから、上の文章をそのまま適用してしまうと処理は永遠に終了しません。その例として、下の図をみて下さい。4 つのセルがあり、どれも値として 1 を持っています。

注目しているのが左上のセルだと考えてください。このセルに対し「文章1」を適用すると、右隣のセルが同じ値を持っていますので、右隣のセルに対して「文章1」を適用することになります。

注目しているセルが右上のセルに移りました。ここで再び、このセル(右上のセル)に対し「文章1」を適用すると、左隣のセルが同じ値を持っているので、左隣のセルに対して「文章1」を適用する事になります。

さて、注目しているセルが左上のセル、すなわち、一番最初に注目していたセルになりました。つまり、一番最初のステップに戻ったということです。このことから言える事は、「文章1」には（もし隣のセルが自分のセルと同じ値を持っているなら）処理の止め時が一切ないということです。だから処理は、一生終わりません。同じことを何度も繰り返します。

「文章1」に足りないものは何でしょうか。これまでの考察を見ていれば、一度調べたセルに対して同じ処理を施しているのが原因であることが分かります。ですから「文章1」を次のように書き換えましょう。

自分と隣り合っているセルがあるなら、そのセルが保持している値を調べる。その値が自分が持っている値と同じであるなら、「その同じ値を持っているセルに対して」同様の処理を実行する。ただし, 既に調べ済みのセルであるなら処理は行わない。

この「処理を行わない」という部分をチェックしているのが以下のコードです。

function IsSameValue(Idx: Integer): Boolean;
begin
  Result := (Idx <> DOES_NOT_EXIST_CELL) and (FCells[Idx].Num = FindValue);
end;

function NotYetKnowingCell(Idx: Integer): Boolean;
begin
  Result := false;
  if not FCells[Idx].DeleteMe then begin
    Result := true;
    FCells[Idx].DeleteMe := true;
  end;
end;

IsSameValue は自分が保持する値と同じ値かどうかを調べます。NotYetKnowingCell 関数は、IsSameValue 関数が true であるなら呼び出されます。この関数が呼び出された時点で、そのセルは「消去されるべきセル」であることが決定していますので、DeleteMe プロパティを true にセットします。ただし、一度 DeleteMe プロパティを true にセットされたセルに対しては行いません。そのセルがまだ手付かずであるなら true とします。セルが手付かずであるので、そのセルに対して再び SearchSameValue を呼び出します。それを行っているのが、次のコードです。

procedure TForm1.SearchSameValue(CellIndex, FindValue: Integer);

  function IsSameValue(Idx: Integer): Boolean;
  begin
    Result := (Idx <> DOES_NOT_EXIST_CELL) and (FCells[Idx].Num = FindValue);
  end;

  function NotYetKnowingCell(Idx: Integer): Boolean;
  begin
    Result := false;
    if not FCells[Idx].DeleteMe then begin
      Result := true;
      FCells[Idx].DeleteMe := true;
    end;
  end;

var
  Idx: Integer;
begin
  // 隣のセルが自分のセルの値と同じかどうかをしらべる。
  
  Idx := GetWestIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetNorthIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetEastIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);

  Idx := GetSouthIndex(CellIndex);
  if IsSameValue(Idx) and NotYetKnowingCell(Idx) then
    SearchSameValue(Idx, FindValue);
end;

まとめ

注目しているセルの値と同じ値を持つセルが隣にあるかどうかを再帰的に調べていく関数を作成しました。繰り返しになりますが、再帰関数には基本部分(ベースケース)と再帰部分の 2 つの部分から構成されているのを理解することが大切です。

*1 それらのセルを見つけ出すには再帰関数と使わなければならないということではありません。

up next
Last update: 2004/3/8