Jaka jest logika do rozwiązania tej sekwencji?

Question

Sekwencja wygląda następująco: 7,8,77,78,87,88,777,778,787,788 i tak dalej ..

Jaka może być logika do znalezienia n-tego numeru sekwencji? Próbowałem tego, dzieląc go przez 2, a następnie przez 4, a więc, ale wydaje się, że nie działa.

Answer 1

obserwacje:

1. sekwencja wydaje się być rosnącej listy numerów zawierających tylko cyfry 7 i 8.

2. Liczba cyfr nie zmniejsza się, a dla każdej n-cyfrowej sekcji są numery 2 ** n w sekwencji.

3. Pierwsza połowa N liczb dwucyfrowych rozpoczyna 7, a drugą połowę rozpoczyna 8.

4. Do każdej połowy N liczb dwucyfrowych pozostałe cyfry po pierwsze są takie same jako liczby n-1 cyfrowe.

Fakty te mogą być wykorzystane do skonstruowania racjonalnie efektywne rekurencyjną implementację.

Oto implementacja 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); 
} 

wyjściowa:

7 
8 
77 
78 
87 
88 
777 
778 
787 
788 

Answer 2

substytut 0 do 7 oraz 1 do 8 i z niego jak binarnej sekwencji

Answer 3

wygląda jak prosty sekwencją binarną, w którym R7 oznacza binarnym zerem, a R8 oznacza binarnych 1.

Answer 4

od wielkości bloku rośnie wykładniczo (2 elementy o długości 1, 4 elementy o długości 2, 8 elementy długości 3 itd.), Można łatwo określić liczbę cyfr w numerze wynikowym.

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

Teraz wystarczy utworzyć reprezentację binarną z n - 1, z 7 do 8 zer i jedynek (dla wyściółka go do długości len zerami). Całkiem proste.

Zakładam, że indeksy zaczynają się od 1 tutaj.

Answer 5

Binary, licząc od dwóch, ignorując wiodącą cyfrę za pomocą 7 i 8 dla zera do jednego:

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

Answer 6

Można obliczyć tę bezpośrednio dla liczby n-ty (num) bez rekursji lub zapętlenie w następujący sposób (przykładowy kod jest w MATLAB):

• obliczyć liczbę cyfr w liczbie:

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

• Znajdź binarną reprezentację liczby num (tylko pierwsze nDigits cyfr) po uprzednim odjęciu jeden mniej niż dwa podniesione do potęgi nDigits:

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

• dodać 7 do każdej wartości w ciąg zer i jedynek:

  result = char(binNum+7); 
  

A oto test, stawiając powyższe trzy kroki do jednego anonimowego funkcji 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

Wpisany jak PHP. Zakładam, że elementy sekwencji są ponumerowane począwszy od 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 
         );