recursion - 再帰をスキップする

Question

最初の行は数値 int x です。次の m 行には文字が含まれています。m 行の後に、数値 int y を読み込みます。

目標は、各行から 1 文字の再帰から解数 int y を見つけることです。

この問題は、可能性のある各パスワードを通過することを回避する、はるかに高速なソリューションがあることを示しています。それが私の質問です。これはどのように行うことができますか？どんな助けでも大歓迎です。

score -1 · Accepted Answer

これはそれほど複雑ではありません。m 行の文字数を数えることができます。次に、文字の行ごとに値を計算します。これは、参照された行の 1 文字がスキップされた場合に、スキップされる可能性のあるソリューションの数を指定します。可視化:

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

「abc」行の n 番目の文字から n+1 番目の文字までスキップすると、次の各行の長さの積が示す数の可能なソリューションをスキップします。したがって、2*4 ソリューションをスキップします -> 8 solutions。

xy についてこの手順を繰り返します ->4 solutionsスキップされます。

1 solution再帰パス自体であるため、最後の行は alwasy をスキップします。

これで、特定の文字にスキップすると、スキップするソリューションの数がわかります。最後は簡単です。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」からの文字のインデックスであり、「dmnr」からの i3 は :) 以上です。アルゴリズムは i1=1、i2=0、i3=1 で終了する必要があります -> "b" + "x" + "m"

これが役立つことを願っています。再帰を削除しますが、それは問題ありませんね。;)

1 に答える 1