Какова логика решения этой последовательности?

Question

Последовательность выглядит следующим образом: 7,8,77,78,87,88,777,778,787,788 и т. Д.

Что может быть логикой для нахождения n-го числа последовательности? Я попробовал это, разделив его на 2, а затем на 4 и, следовательно, но он не работает.

Answer 1

Наблюдение:

1. последовательность, как представляется, список по возрастанию чисел, содержащих только цифры 7 и 8.

2. Число цифр не уменьшается и для каждой n-разрядной секции в последовательности записано 2 ** n номеров.

3. Первая половина из н-х цифр, начинается с 7, а вторая половина начинается с 8.

4. Для каждой половины п-х цифр, то остальные цифры после первого одинаковы как n-1 цифры.

Эти факты могут быть использованы для построения достаточно эффективной рекурсивной реализации.

Вот C# реализация:

void Main() { 
    for (int i = 0; i < 10; i++) 
     Console.WriteLine (GetSequence(i)); 
} 

string GetSequence(int idx) { 
    if (idx == 0) return "7"; 
    if (idx == 1) return "8"; 

    return GetSequence(idx/2 - 1) + GetSequence(idx % 2); 
} 

Выход:

7 
8 
77 
78 
87 
88 
777 
778 
787 
788 

Answer 2

замена 0 на 7 и 1 для 8 и рассматривать его как двоичную последовательность

Answer 3

Это выглядит как простая двоичной последовательность, где 7 представляет собой двоичный ноль, и 8 представляют собой двоичные 1.

Answer 4

Так как размер блока растет в геометрической прогрессии (2 элементы длины 1, 4 элемента длины 2, 8 элементов длины 3 и т. Д.), Вы можете легко определить количество цифр в номере результата.

long block_size = 2; 
    int len = 1; 
    while (n > block_size) { 
     n -= block_size; // n is changed here 
     block_size *= 2; 
     ++len; 
    } 

Теперь, вы просто создать бинарное представление о n - 1, с 7 по 8 нулям и для них (отступов его длину len нулей). Довольно просто.

Я предполагаю, что индексы начинаются с 1 здесь.

Answer 5

Двоичных, считая от двух, не обращая внимания на ведущую цифру, используя 7 и 8 для нуля и единицы:

 7, 8, 77, 78, 87, 88, 777, 778, 787, 788 
0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011 

Answer 6

Вы можете вычислить этот непосредственно для N-го числа (num) без рекурсии или зацикливания, выполнив следующие действия (пример кода находится в MATLAB):

• Подсчитать количество цифр в номере:

  nDigits = floor(log2(num+1)); 
  

• Найти двоичное представление числа num (только первые nDigits цифры) после первого вычитания один меньше, чем два, возведенное в степень nDigits:

  binNum = dec2bin(num-(2^nDigits-1),nDigits); 
  

• Добавить 7 для каждого значения в строка нулей и единиц:

  result = char(binNum+7); 
  

А вот тест, поставив выше три шага в одну анонимную функцию f:

>> f = @(n) char(dec2bin(n+1-2^floor(log2(n+1)),floor(log2(n+1)))+7); 
>> for n = 1:20, disp(f(n)); end 
7 
8 
77 
78 
87 
88 
777 
778 
787 
788 
877 
878 
887 
888 
7777 
7778 
7787 
7788 
7877 
7878 

Answer 7

Написанное PHP. Я предполагаю, что элементы последовательности нумеруются начиная с 1.

$n = 45; 
// let's find the 45th sequence element. 
$length = 1; 
while ($n >= pow(2, $length + 1) - 1) { 
    $length++; 
} 
// determine the length in digits of the sequence element 
$offset = $n - pow(2, $length) + 1; 
// determine how far this sequence element is past the 
// first sequence element of this length 
$binary = decbin($offset); 
// obtain the binary representation of $offset, as a string of 0s and 1s 
while (strlen($binary) < $length) { 
    $binary = '0'.$binary; 
} 
// left-pad the string with 0s until it is the required length 
$answer = str_replace(array('0', '1'), 
         array('7', '8'), 
         $binary 
         );