Как найти общее число чисел, двоичное представление которых является палиндром?

Каков наилучший подход для нахождения общего числа чисел между двумя заданными числами, двоичное представление которых является палиндромом? Проблема, которую я пытаюсь решить, находится здесь, на spoj http://www.spoj.com/problems/BINPALI/

Источник

4 ответа

Решение

Я решил проблему спой и код, как показано ниже:

#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;
}
Источник

Один из возможных подходов:

Возьмем двоичное представление 1-го числа М.

Найдите 1-е число больше 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
Источник

Питон мощный! Не усложняй! Ну, это немного медленно!

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"
Источник

Срок очень строгий по этой проблеме. Даже оптимизированный генератор палиндрома, вероятно, не будет работать. Вероятно, вам придется использовать формулу в OEIS для данной заданной целочисленной последовательности.

Есть и формула обращения. Это дано следующим образом.

Формула обращения: если b>0 - это любой двоичный палиндром, то индекс n, для которого a(n)=b, равен n=palindromicIndexOf(b)=(((5-(-1)^m)/2) + sum_{k=1... этаж (м /2)} (этаж (b/2^k) mod 2)/2^k))*2^ этаж (m/2), где m= этаж (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.:)

Источник
Другие вопросы по тегам