C++ এ ব্যাকরণে K-তম চিহ্ন

ধরুন প্রথম সারিতে, আমাদের একটি 0 আছে। এখন প্রতিটি পরবর্তী সারিতে, আমরা আগের সারির দিকে তাকাই এবং 0 বাই 01 এর প্রতিটি ঘটনা এবং 1 বাই 10 এর প্রতিটি ঘটনা প্রতিস্থাপন করি। ধরুন আমাদের এন সারি এবং সূচক K আছে, আমরা সারিতে K-তম সূচীযুক্ত চিহ্নটি খুঁজে বের করতে হবে। তাই যদি 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