C++の文法のK番目の記号

最初の行に0があるとします。後続のすべての行で、前の行を見て、0の各出現を01に、1の各出現を10に置き換えます。N行とインデックスKがあると仮定します。行NでK番目のインデックス付きシンボルを見つける必要があります（Kの値は1インデックスです）（1インデックス）。したがって、N=4およびK=5の場合、出力は1になります。これは-

• 行1：0
• 行2：01
• 行3：0110
• 行4：01101001

これを解決するには、次の手順に従います-

• メソッドの名前がkthGrammarであるとします。これにはNとKが必要です。
• Nが1の場合、0を返します
• kが偶数の場合、kthGrammar（N – 1、K / 2）が0の場合は1を返し、それ以外の場合は0を返します
• それ以外の場合は、kthGrammar（N – 1、（K + 1）/ 2）を返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int kthGrammar(int N, int K) {
      if(N == 1) return 0;
      if(K % 2 == 0){
      return kthGrammar(N - 1, K / 2) == 0 ? 1 : 0;
      }else{
         return kthGrammar(N - 1, (K + 1) / 2);
      }
   }
};
main(){
   Solution ob;
   cout << (ob.kthGrammar(4, 5));
}

入力

4
5

出力

1