K-th Symbol trong Grammar trong C ++

Giả sử trên hàng đầu tiên, chúng ta có số 0. Bây giờ, trong mỗi hàng tiếp theo, chúng ta nhìn vào hàng trước đó và thay thế mỗi lần xuất hiện của 0 bằng 01 và mỗi lần xuất hiện bằng 1 bằng 10. Giả sử chúng ta có N hàng và chỉ mục K, chúng ta phải tìm ký hiệu được lập chỉ mục thứ K trong hàng N. (Các giá trị của K là 1 được lập chỉ mục.) (1 được lập chỉ mục). Vì vậy, nếu N =4 và K =5, thì đầu ra sẽ là 1. Điều này là do -

• Hàng 1:0
• Hàng 2:01
• Hàng 3:0110
• Hàng 4:01101001

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Giả sử tên của phương thức là kthGrammar. Điều này mất N và K.
• nếu N là 1, thì trả về 0
• nếu k chẵn, trả về 1 khi kthGrammar (N - 1, K / 2) bằng 0, nếu không thì 0
• nếu không thì trả về kthGrammar (N - 1, (K + 1) / 2)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

4
5

Đầu ra

1