再帰アルゴリズムの効率を上げる方法は?

Aug 22 2020

質問は:

負でないintnが与えられた場合、8の出現回数を数字として再帰的に(ループなしで)計算します。ただし、8とそのすぐ左に別の8がある場合は、2倍になるため、8818は4になります。mod(%)に注意してください。 10で割ると右端の桁(126%10は6)になり、(/)を10で割ると右端の桁が削除されます(126/10は12)。

count8(8)→1 count8(818)→2 count8(8818)→4

私の解決策は次のようになりました。

public int count8(int n) {
  if(n == 0)  return 0;
  
  int faith = count8(n/10);
  int c = 0;
  if(n%10 == 8){
    n /= 10;
    if(n%10 == 8){
      c++;
    }
    c++;
  }
  return c + faith;
}

複数のif条件を削除して、これをよりクリーンで効率的にする方法はありますか?

回答

4 Bobby Aug 23 2020 at 06:53

変数名。例外なく、変数の機能にちなんで変数に名前を付けます。


補足として、Javaで整数除算がどのように機能するかに依存していることに注意してください。


そうは言っても、明示的にすることでコードを改善できます。

// As I've said, always name your variables and functions after
// what they are doing. Don't be afraid to use longer names,
// longer names which tell you what the class does are a good
// thing, even if they sound "funny".
public int countEights(int value) {
    // Early exit conditions are a good thing.
    if(value == 0) {
        return 0;
    }
    
    // We could also skip the declaration and instead return
    // the right count together with the function call. From
    // the viewpoint of the JVM it doesn't make a difference,
    // but here in the code it means that we have the logic
    // for stripping the last digit only once.
    int countedEights = 0;
    
    // We are testing explicitly for the mentioned "double eights",
    // this has the upside that the intent is clearly visible
    // when reading the code.
    if ((value % 100) == 88) {
        countedEights = 2;
    } else if ((value % 10) == 8) {
        countedEights = 1;
    }
    
    // And finally we call the function again in the return
    // statement, as it is easier to follow the recursion when
    // it is being called at the end of the function.
    return countedEights + countEights(value / 10);
}

ご覧のとおりif、意図を明示することで、ネストされたものを完全に取り除くことができます。

2 chromaticc Aug 22 2020 at 15:22

再帰を扱うときは、基本ケースと再帰ケースが何であるかを書き留めて、そこから進むことが重要です。これらのさまざまなケースは、基本的に関数の構造になります。

あなたはすでにあなたの問題のさまざまなケースを理解しています:

  1. 場合 n == 0
  2. 8が1桁の場所にある場合(n % 10 == 8
  3. 8が1桁の桁にない場合(n % 10 != 8

の場合n == 0、0を返します。

の場合n % 10 == 8、8が1つあることがわかりますが、への入力パラメーターとしてを使用してcount8再度呼び出す必要がありn / 10ますcount8この呼び出しから戻るときは、すでに1つ8が見つかっているため、結果に1を追加してから返します。次に、count8呼び出しの結果に1(すでに見つけた8)を追加します。

  • この場合、次の桁も8であるかどうかを確認する必要があります。そうである場合は、戻る前に結果を1つインクリメントする必要があります。これは、最初の再帰呼び出しの前または後に行うことができます。連続したn / 108を「削除」した後は、必ずパスしてください。

場合はn % 10 != 8、その後、我々は単に呼んcount8n / 10私たちの入力パラメータとしてこの呼び出しから結果を返します。

うまくいけば、これにより、関数をより明確に構造化する方法がわかります。