如何查找二进制表示为回文的数字总数

Question

查找二进制表示为回文的两个给定数字之间的数字总数的最佳方法是什么？我试图解决的问题在 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

一种可能的方法是：

取第一个数字 M 的二进制表示。

找到二进制表示中回文的第一个大于 M 的数字：
- 对于 M，保持左半部分位，相同的值，并将二进制字符串的右半部分与左半部分匹配。

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

如果结果数字为

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

要查找后续数字，请从中间向末尾递增位。

10011001
10100101
10111101
11000011

Answer 3

这个问题的时间限制非常严格。即使是优化的回文生成器也可能不起作用。对于此给定整数序列，您可能必须在 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）， where 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"