对称字符串-od-python

题目描述

对称就是最大的美学，现有一道关于对称字符串的美学。已知:

第1个字符串:R

第2个字符串:BR

第3个字符串:RBBR

第4个字符串:BRRBRBBR

第5个字符串:RBBRBRRBBRRBRBBR

相信你已经发现规律了，没错!就是第个字符串=第i-1号字符串取反+第i-1号字

符串

取反(R->B，B->R)

现在告诉你n和k，让你求得第n个字符串的第k个字符是多少。(k的编号从0开始)

输入描述

第一行输入一个T，表示有T组用例;

解析来输入T行，每行输入两个数字，表示n，k

1≤T≤100;
1<n<64;
0<=k<2^(n-1);
输出描述

输出T行表示答案;

输出“blue"表示字符是B;

输出"red"表示字符是R。

备注:输出字符串区分大小写，请注意输出小写字符串，不带双引号。

用例

方法1：
将字符串组合出来，然后直接获取k位置的颜色，这种数据大的会超时

def re_br（str1）:
   pass  # 反转BR

def blue_or_red(n):
    if n == 1:
        return 'R'
    return re_br(blue_or_red(n - 1)) + blue_or_red(n - 1)

s = int(input())
for i in range(s):
    n, k = map(int, input().split())
    print(blue_or_red(n)[k])

方法1：

def get_nk(n, k):
    if n == 1: # k只可取0，只有返还red
        return "red"
    if n == 2:  # n=2的话，k只能取0或者1
        if k == 0:
            return "blue"
        else:
            return "red"
    half = 2 ** (n - 2)  # 取字符的一半
    if k >= half:
        return get_nk(n - 1, k - half) # # 如果k是后半段的,跟n-1的一样的，k的参数变为k-half  
    else:  # 在前半段，那么它就是取 n-1相反的即可
        if get_nk(n - 1, k) == "red":
            return 'blue'
        else:
            return 'red'


for _ in range(int(input())):
    n, k = map(int, input().split())
    print(get_nk(n, k))