如何查找二進制表示爲迴文的數字總數？

Question

什麼是最好的方法來找到兩個給定數字之間的二進制表示是迴文的總數字？ The problem I am trying to solve is here on spoj http://www.spoj.com/problems/BINPALI/

Answer 1

我解決了這個問題SPOJ和代碼如下：

#include<iostream> 
#include<algorithm> 
#include<cctype> 
#include<cstring> 
#include<string> 
using namespace std; 
int main() 
{ 
    int a,b,t; 
    cin>>t; 
    while(t--) 
    { 
    cin>>a>>b; 
    int total=0; 
    string s=""; 
    while(a<=b) 
    { 
     s=""; 
     for(int i=a;i>0;i=i/2) 
     { 
     if(i%2) 
      s+='1'; 
     else 
      s+='0'; 
     } 
     string s2="",s3=""; 
     s2=s.substr(0,s.length()/2); 
     int k=s.length(); 
     if(k%2) 
     s3=s.substr(s.length()/2+1,s.length()); 
     else 
     s3=s.substr(s.length()/2,s.length()); 
     reverse(s2.begin(),s2.end()); 
     if(s2==s3) 
     { 
     cout<<a<<" "; 
     total++; 
     } 
     a++; 
    } 
if(!total) 
    cout<<"none"<<endl; 
} 
return 0; 
} 

Answer 2

一個可行的方法是：

採取第1個數字的二進制表示M.

找到第一個數字大於M是迴文的二進制形式：
- 對於M ，保留左半部分，相同的值，並將二進制字符串的右半部分與左半部分匹配。

For example if M is 10110111, the number shall be 10111101 

如果產生的數是< M，則遞增1左子串，然後匹配的權利串。

Eg. if M is 10000011, the number shall be 10000001 < M , hence number shall be 10011001. 

要查找後續數字，請從中間向末尾增加位。

10011001 
10100101 
10111101 
11000011 

Answer 3

這個問題對時間限制非常嚴格。即使是優化的迴文發生器也可能無法工作。對於給定的整數序列，您可能必須使用formula at OEIS。

還有一個反轉公式。它給出如下。如果b> 0是任何二元迴文，那麼其中a（n）= b的索引n是 n = palindromicIndexOf（b）=（（（5 - （ - 1）^ m）/ 2）+ sum_ {k = 1 ... floor（m/2）}（floor（b/2^k）mod 2）/ 2^k））* 2^floor（m/2），其中m = floor （log_2（b））。

您可能不得不採取兩個給定的索引，並以某種方式從序列中找出最低的n和最高的n。然後在範圍內（最低n，最高n）打印出序列中的所有第n個數字。第n個二進制迴文數的每個查詢都是O（1）次，因此每個測試用例應該採用O（log（B-A））時間。這是非常低的，但你需要得到公式的工作。 :)

祝你好運實現這個序列的發電機公式。我試過了，無法啓動它。 :(這是相當複雜的。

但不管怎麼說參考，我試着在Python 2.7.5使用優化的迴文發生器，它給了我超出時間限制。這裏是代碼，如果你有興趣。

from itertools import product, repeat 
from bisect import insort, bisect 

def all_binary_sequences_of_length_(n): 
    return [''.join(seq) for seq in product('01', repeat=n)] 


def main(): 
    binary_palindromes = [0, 1, 3, 5, 7] 
    for n in xrange(1, 15): 
     A = all_binary_sequences_of_length_(n) 
     for a in A: 
      b = a[::-1] 
      # Add palindromes of length 2n + 2 
      insort(binary_palindromes, int((a+b).join('11'), 2)) 
      # Add palindromes of length 2n + 3 
      insort(binary_palindromes, int((a+'0'+b).join('11'), 2)) 
      insort(binary_palindromes, int((a+'1'+b).join('11'), 2)) 

    t = int(raw_input()) 
    for _ in repeat(0, t): 
     a, b = map(int, raw_input().split()) 
     start = bisect(binary_palindromes, a - 1) 
     end = bisect(binary_palindromes, b) 
     output = [str(binary_palindromes[i]) for i in xrange(start, end)] 
     if len(output) == 0: 
      print 'none' 
     else: 
      print ' '.join(output) 


if __name__ == '__main__': 
    main() 

我知道Python是不是一個非常快的語言，但只需要1秒的時間限制使我相信，只有這樣，才能解決這個問題是在OEIS使用公式。:)

Answer 4

Python很強大！不要讓它變得複雜！呃，有點慢！

for _ in range(input()): 
    has = False 
    x,y = map(int, raw_input().split()) 
    for i in range(x,y+1): 
     temp = bin(i) 
     temp = temp[temp.index('b')+1:] 
     if temp[::-1] == temp: 
      has = True 
      print i, 
    if not has: 
     print "none"