問題 ：
我們得到一系列二進制字串。該系列的第一項是 0。因此，T1 = '0'。為了在任何給定的 Ti 處找到字串，我們查看 Ti - 1 并將所有出現的“0”替換為“01”，將“1”替換為“10”。給你兩個整數 N 和 X，你的作業是找到 TN 并回傳它的第 X 個索引。注意：Ti 是 1-indexed。
輸入格式：
輸入的第一行包含一個整數 T，表示測驗用例的數量。接下來的 T 行包含兩個空格分隔的整數 N 和 X。
輸出格式：
列印第 N 行中的第 X 個索引
樣本輸入：
1
4 5
樣本輸出：
1
解釋：
T1: '0'
T2: '01'
T3: '0110'
T4: '01101001'
T4 中的第 5 個元素是“1”。
我嘗試了下面的解決方案，但是對于大于 25 的 n 值超出了時間限制。如何處理大型測驗用例？
from sys import stdin , setrecursionlimit
setrecursionlimit(10**8)
t = int(input())
def temp(s,n):
if n==0:
return s
ans = ''
d = {
'0':'01',
'1':'10'
}
for ele in s:
ans =d[ele]
return temp(ans,n-1)
while t:
n,x = [int(x) for x in stdin.readline().strip().split()]
s = '0'
res = temp(s,n)
print(res[x-1])
t-=1
uj5u.com熱心網友回復：
嘗試這個。您可以使用迭代（for回圈）而不是遞回：
# Iterative function to get T(i)
def T(i): # Define function
l = '0' # Variable that holds the last value in the sequence
for _ in range(i-1): # Iterate i-1 times
d = {'0': '01', '1': '10'} # Just like in your code
l = ''.join(map(d.get, l)) # Equivalent to ''.join(d[c] for c in l)
return l # Return the last value
r = int(input()) # Number of test cases
while r: # Just like in your code
n, x = map(int, input().split()) # Get n and x as input, and convert to integer
print(T(n)[x-1]) # Get T(n) and get the xth index
r -= 1 # Decrement r by 1
輸入：
1
4 5
輸出：
1
uj5u.com熱心網友回復：
生成的元素有一個模式。
0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110
那個模式nextElement是previousElement flipallbits(previousElement)。并嘗試形成遞回關系以找到特定索引中的位。
所以說如果一個索引說 4，它是索引 0 的翻轉操作。
假設索引為 5，則它是索引 1 的翻轉操作。這反過來又是索引 0 的翻轉操作。
因此，您已從索引中洗掉 2 的最高冪，然后翻轉該位，如果索引為 0，則回傳 0。
x = 3
def findElement(x):
if(x == 0):
return False
power = 1
while (power*2) <= x:
power *= 2
return not findElement(x - power)
print(int(findElement(x)))
在這個實作中不需要 n。另一個選項只是計數，索引 x 的二進制表示中的個數，并檢查它是否偶數。如果它甚至回傳0，否則為1。
uj5u.com熱心網友回復：
您只需要查看模式，對于奇數到偶數的轉換，它只是前一個字串 它的反轉，而對于偶數到奇數的轉換，它是前一個字串 前一個字串的值的補碼
這是代碼
def function(n, x):
tmp = ['0']
if n==0:
if x>len(tmp)-1:
return -1
elif x<=len(tmp)-1:
return tmp[x]
for i in range(1, n):
if not i%2:
tmp = tmp tmp[::-1]
else:
tmp = tmp ['0' if i=='1' else '1' for i in tmp]
if x<=len(tmp)-1:
return tmp[x]
return -1
-1如果索引超出范圍。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/507827.html