recursion - 跳过递归

Question

第一行是一个数字，int x。以下 m 行包含字母。在 m 行之后，你读入一个数字 int y。

目标是从每行 1 个字母的递归中找到解数 int y。

问题表明有一个更快的解决方案可以避免遍历每个可能的密码。这就是我的问题所在。如何才能做到这一点？任何帮助将不胜感激。

Answer 1

这并不复杂。您可以计算 m 行中的字母数。然后为每一行字母计算一个值，指定跳过多少个可能的解决方案，如果引用行中的一个字母被跳过。可视化：

abc -> 3 letters
xy -> 2 letters
dmnr -> 4 letters

如果您从“abc”行中的第 n 个字母跳到第 n+1 个字母，则您会跳过尽可能多的可能解决方案，就像下一行的长度的乘积所说的那样。所以你跳过 2*4 解决方案 -> 8 solutions。

对 xy 重复此步骤 ->4 solutions跳过。

最后一行总是跳过1 solution，因为它本身就是递归路径。

所以现在你知道了，如果你跳到某个特定的字母，你跳过了多少个解决方案。最后一点很简单。您从 1 开始，并将每行的计算值添加到数字中，直到恰好达到 r。

在 C++ 中的意思是：

int v = 1, r=10;
int i1=0, i2=0, i3=0;

while (v<=r-8) {
  i1++;
  v+=8;
}
while (v<=r-4) {
  i2++;
  v+=4;
}
while (v<=r-1) {
  i3++;
  v++;
}

现在 i1 是您需要从“abc”行使用的字母的索引，i2 是来自“xy”的字母的索引，而 i3 是来自“dmnr”的字母的索引 :) 就是这样。算法应该以 i1=1, i2=0, i3=1 -> "b" + "x" + "m" 结尾

我希望这有帮助。它消除了递归，但这没问题，是吗？;)