字符变换:0 -> 01,1 -> 10,求第N行的第K个字符

编辑:谯胜平      分类:程序与算法      标签:      发布时间:2021-04-27      浏览次数:312

1、题目描述:

第一行输入0,第二行将0变为01,得到01;第三行将0变换为01,将1变换为10,得到0110;之后的每一行都是通过将其前一行中的0变换为01,将1变换为10而得到。

现给定N,K,其中1≤N≤30,1≤K≤2^(30-1)。输出第N行的第K个字符。

示例输入:

3 2

示例输出:

1

示例说明:

按照题目中要求的字符变换方法,第三行的字符是0110,第二个字符是1,所以输出1。

2、思路分析

肯定不能使用递推的方法,时间复杂度过大。

运行过程如下。

由于整棵树是满二叉树,查找第n行第k个数字,可以考虑使用递归的方式,定义递归函数f(n,k,now),now表示当前根节点的数字,递归过程如下:

(1)如果n=1,返回now;

(2)如果n>1且k小于等于叶子结点总数的一半,去左半子树查找,即返回f(n-1,k, now ==0 ? 0 : 1);

(3)如果n>1且k大于叶子节点总数的一半,去右半子树查找,此时k应该减掉左半子树叶子结点数,即返回f(n-1, k - pow(2, n - 2), now == 0 ? 1 : 0);

3、代码

#include<iostream>
using namespace std;

int find(int n, int k, int now){
    if(n == 1){
        return now;
    }else{
        if(k <= (1 << (n - 2))){     //使用左移代替2^(n-2),也就是第n层叶子节点数目的一半 
            return find(n - 1, k, now == 0 ? 0 : 1);
        }else{
            return find(n - 1, k - (1 << (n - 2)), now == 0 ? 1 : 0);
        }
    }
} 

int main(){
    int n, k;
    cin >> n >> k;
    cout << find(n, k, 0) << endl;
    return 0;
}

          



看不清?换一个