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。找到该单词后将立即返回,此时搜索将被缩短。如果没有 in ,当所有循环都运行到lex最后时,最终将返回空字符串。for

第二个片段只会尝试一个词:初始soFarrest字符串的连接。如果那个连接的字符串是 in lex,它会updateSet用它调用。然后它会返回,表示失败。不会执行进一步的搜索,因为循环return内部的 from是无条件的。for

所以这两个功能是完全不同的。要使第二个代码的行为与第一个代码一样,您需要它返回其他内容以指示成功,并且仅在调用返回值指示成功for时从循环内返回。FindWord显然,void不能用于信号failuresuccess。至少,您需要为此返回bool值。

如果没有返回,您的第三个代码将执行详尽的搜索。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在堆栈上调用帧,用于初始字符串n中的字母。rest

每次我们触底时,我们都会从 中挑选出所有的字母rest。执行检查以查看它是否在 中lex,然后控制返回上一级。

因此,如果没有返回,则每个for循环都会运行到结束。如果返回是无条件的,则只会尝试一种排列 - 微不足道的排列。但是如果返回是有条件的,那么整个事情只会在第一次成功时停止。

于 2012-08-05T15:13:36.770 回答