RSS

  

RSS


プ：探索プログラムをリストで

  • いわいまさか
  • at 2011/4/01 14:52:55

　探索プログラムは、再帰呼び出しの関数で書くかわりに、リスト構造で書ける。

　リストで書く利点は思いつくところでざっとあげる。
・スタックオーバーフローの心配をしなくてよい。
・見通しが利く。
・探索に関して俯瞰したような処理もしやすい。

　過去の上野のパンダの名前で「ファンファン」と「フェイフェイ」というのがあった。
　今回の問題は
　「フ・ァ・ン・ェ・イ」という５個のカタカナを使い、６文字以下で作れる名前にはどんなものがあるか？
　というもの。
　ひとつのポイントは「ァから始まるのはおかしい」「ンンとならない」とかそういう禁則があるということ。「イェ」と「イァ」はなしにした。


using namespace System;
using namespace System::Collections::Generic;

int _tmain(int argc, _TCHAR* argv[])
{
    List<String^>^ fanfei = gcnew List<String^>();

    fanfei->Add("フ");
    fanfei->Add("イ");

    for(;;){
     if(fanfei->Count<=0){
       break;
     }

     int index=0;                         //  横型探索
//   int index=fanfei->Count-1;  //  縦型探索

     String^ abab=fanfei[index];
     Console::WriteLine(abab);
     if(abab->Length<6){
       if(abab->EndsWith("フ")){
         fanfei->Add(abab+"フ");
         fanfei->Add(abab+"ァ");
         fanfei->Add(abab+"ン");
         fanfei->Add(abab+"ェ");
         fanfei->Add(abab+"イ");
     }else if(abab->EndsWith("ァ") || abab->EndsWith("ェ")){
        fanfei->Add(abab+"フ");
        fanfei->Add(abab+"ン");
        fanfei->Add(abab+"イ");
     }else if(abab->EndsWith("ン")){
        fanfei->Add(abab+"フ");
        fanfei->Add(abab+"イ");
     }else if(abab->EndsWith("イ")){
        fanfei->Add(abab+"フ");
        fanfei->Add(abab+"ン");
        fanfei->Add(abab+"イ");
     }
   }
    fanfei->RemoveAt(index);
  }
}

一行かえるだけで横型探索と縦型探索の切り替えができる。

今、登録した項目（リストで言えば後ろ側）をどんどん調べていけば縦型探索。
そうでなく、リストの前側から処理していけば横型探索。

　横型探索を再帰関数で書くのはそう簡単でない（できない？）のでこの点もリストで書いた効能といえる。

横型探索の出だしは
フ・イ・フフ・ファ・フン・フェ・フイ・イフ・イン・イイ・フフフ・フファ・フフン・フフェ・フフイ・ファフ・ファン・ファイ・フンフ・・・
（まだ、３文字以下の単語しか現れてない）

縦型探索の出だしは
イ・イイ・イイイ・イイイイ・イイイイイ・イイイイイイ・イイイイイン・イイイイイフ・イイイイン・・・
（６文字の単語が６個目に現れてる）


  • コメント (0)
  • トラックバック (0)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/55237

コメントを書く