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 सम है, तो 1 लौटाएं जब kthGrammar(N – 1, K/2) 0 हो, अन्यथा 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