しりとりのパターンを全パターンするには？ (ID:39020)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文

再帰使わないで行けると判断した私が馬鹿でした。
再帰版です。全通りを比較的効率よく集めています。

unit Unit1;

interface

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

type
  TSiritori = class
  private
    procedure GetCount;
  public
    fChildList:TList;
    fParent : TSiritori;
    fLeftList : TStringList;
    fHiraWord : string;
    fCount : Integer;
    Constructor Create(aParent:TSiritori);
    Destructor Destroy; override;
    procedure  Analize(var aBestCount:Integer; aBestList:TList);
    function SiriStr:string;
  end;

TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private 宣言 }
  public
    { Public 宣言 }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

//しりとりの判別関数
//濁点の判別を甘くするならここを変更
function HiraConnect(aStrA,aStrB:string):Boolean;
begin
  Result := (aStrA[Length(aStrA)] = aStrB[1]);
end;

{ TSiritori }

procedure TSiritori.Analize(var aBestCount:Integer; aBestList:TList);
var
  i,p: Integer;
  Siritori:TSiritori;
begin
  for i := 0 to fLeftList.Count - 1 do
  begin
    if (fParent=nil) or
       (HiraConnect(fHiraWord,fLeftList.Strings[i])) then
    begin
      Siritori := TSiritori.Create(Self);
      Siritori.fLeftList.Assign(fLeftList);
      Siritori.fHiraWord := fLeftList.Strings[i];
      Siritori.fLeftList.Delete(i);
      SiriTori.Analize(aBestCount,aBestList);
    end;
  end;
  GetCount;
  if fChildList.Count=0 then
  begin
    if fCount > aBestCount then
    begin
      aBestCount := fCount;
      aBestList.Clear;
    end;
    if fCount = aBestCount then
      aBestList.Add(Self);
  end;
end;

constructor TSiritori.Create(aParent:TSiritori);
begin
  fParent := aParent;
  fChildList := TList.Create;
  if aParent<>nil then
    aParent.fChildList.Add(Self);
  fLeftList := TStringList.Create;
end;

destructor TSiritori.Destroy;
var
  i: Integer;
begin
  for i := 0 to fChildList.Count - 1 do
    TSiritori(fChildList.Items[i]).Free;
  fLeftList.Free;
  fChildList.Free;
  inherited;
end;

procedure TSiritori.GetCount;
var
  aSiritori:TSiritori;
begin
  fCount := 0;
  aSiritori := Self;
  while aSiritori<>nil do
  begin
    inc(fCount);
    aSiritori := aSiritori.fParent;
  end;
end;

function TSiritori.SiriStr: string;
var
  aSiritori:TSiritori;
begin
  aSiritori := Self;
  Result := '';
  while aSiritori.fParent<>nil do
  begin
    Result := aSiritori.fHiraWord + #$D#$A + Result;
    aSiritori := aSiritori.fParent;
  end;
end;

{ TForm1 }
procedure TForm1.Button1Click(Sender: TObject);
var
  Siritori : TSiritori;
  MaxCount:Integer;
  List:TList;
  i: Integer;
begin
  Siritori := TSiritori.Create(nil);
  Siritori.fLeftList.Add('りんご');
  Siritori.fLeftList.Add('ごりら');
  Siritori.fLeftList.Add('ごあ');
  Siritori.fLeftList.Add('あんぱんまん');
  Siritori.fLeftList.Add('ごご');
  Siritori.fLeftList.Add('ごぼう');
  Siritori.fLeftList.Add('らくだ');
  MaxCount := 0;
  List := TList.Create;
  Siritori.Analize(MaxCount,List);
  for i := 0 to List.Count - 1 do
  begin
    ShowMessage(TSiritori(List.Items[i]).SiriStr);
  end;
  Siritori.Free;
end;

end.

←解決時は質問者本人がここをチェックしてください。

戻る