2

この質問を一般化するために、Zelenski CS クラスの配布資料から資料を借りています。そして、数年前に別のインストラクターからクラスを受講し、C++ へのこのアプローチを学んだので、それは私の特定の質問に関連しています。配布資料はこちらです。C++ は時々使用するため、私の理解度は低いです。基本的に、プログラムを書く必要があったときは、クラスの資料に戻って、似たようなものを見つけてそこから始めました。

この例 (4 ページ) では、Julie は文字列関数で再帰アルゴリズムを使用して単語を探しています。再帰呼び出しの数を減らすために、彼女は決定点を追加しましたbool containsWord()。

string FindWord(string soFar, string rest, Lexicon &lex)
{
  if (rest.empty()) {
   return (lex.containsWord(soFar)? soFar : "");
  } else {
   for (int i = 0; i < rest.length(); i++) {
     string remain = rest.substr(0, i) + rest.substr(i+1);
     string found = FindWord(soFar + rest[i], remain, lex);
     if (!found.empty()) return found;
   }
  }
 return ""; // empty string indicates failure
}

このアルゴリズムの使用方法に柔軟性を追加するために、これを void 型として実装できますか?

void FindWord(string soFar, string rest, Lexicon &lex, Set::StructT &words)
{
  if (rest.empty()) {
    if (lex.containsWord(soFar)) //this is a bool
       updateSet(soFar, words); //add soFar to referenced Set struct tree
  } else {
   for (int i = 0; i < rest.length(); i++) {
     string remain = rest.substr(0, i) + rest.substr(i+1);
     return FindWord(soFar + rest[i], remain, lex, words); //<-this is where I am confused conceptually
   }
  }
 return; // indicates failure
}

そして、返品なしでどうですか

void FindWord(string soFar, string rest, Lexicon &lex, Set::StructT &words)
{
  if (rest.empty()) {
    if (lex.containsWord(soFar)) 
       updateSet(soFar, words); //add soFar to Set memory tree
  } else {
   for (int i = 0; i < rest.length(); i++) {
     string remain = rest.substr(0, i) + rest.substr(i+1);
     FindWord(soFar + rest[i], remain, lex, words); //<-this is where I am confused conceptually
   }
  }
}
4

1 に答える 1

1

最初のコード フラグメントは、 (おそらく空の文字列?)restの初期値に追加された のすべての順列を試します。soFarにある最初の単語で停止しlexます。その単語は見つかるとすぐに返され、検索はその時点で短くなります。に何もなかった場合、すべてのループが最後までコースを実行しlexたときに、最終的に空の文字列が返されます。for

soFar2 番目のフラグメントは、イニシャルと文字列の連結という 1 つの単語のみを試行しrestます。その連結された文字列が にある場合lex、それを呼び出しますupdateSet。その後、失敗を示して戻ります。returnループ内の fromforは無条件であるため、それ以上の検索は実行されません。

したがって、これら 2 つの機能はまったく異なります。2 番目のコードを最初のコードと同じように動作させるには、成功を示すために別の何かを返す必要があり、呼び出しの戻り値が成功を示しているfor場合にのみループ内から戻る必要があります。FindWord明らかに、と の合図にvoidは使用できません。少なくとも、そのために値を返す必要があります。failuresuccessbool

リターンがなければ、3 番目のコードは徹底的な検索を実行します。の初期文字列値のすべての可能な順列restが試行され、レキシコンで検索されます。

次のように何が起こっているかを視覚化できます。

FindWord:   soFar=""     rest=...........
    for:    i=...    rest[i]=a
       call findWord

FindWord:   soFar=a       rest=..........
    for:    i=...    rest[i]=b
       call findWord

FindWord:   soFar=ab       rest=.........
    for:    i=...    rest[i]=c
       call findWord
       if return, the loop will be cut short
       if not, the loop continues and next i will be tried

 ......

FindWord:   soFar=abcdefgh...      rest=z
    for:    i=0      rest[0]=z
       call findWord

FindWord:   soFar=abcdefgh...z      rest=""      // base case
    // for:    i=N/A    rest[i]=N/A
    if soFar is_in lex                           // base case
      then do_some and return soFar  OR  success
      else             return ""     OR  failure

rest基本ケースに到達する (が空になる)たびに、最初の文字列の文字n+1 FindWordに対して、スタックに呼び出しフレームがあります。nrest

一番下に到達するたびに、 からすべての文字を選択しましたrest。にあるかどうかのチェックが実行されlex、制御が 1 つ上のレベルに戻ります。

したがって、リターンがない場合、各forループは最後まで実行されます。戻り値が無条件の場合、単純な順列のみが試行されます。しかし、リターンが条件付きの場合、すべてが最初の成功でのみ停止します。

于 2012-08-05T15:13:36.770 に答える