Запросы конкатенации строк

Question

У меня есть список символов, например x, обозначенный b[1], b[2], b[3] ... b[x]. После того, как x,

• b[x+1] является конкатенацией b[1],b[2].... b[x] в таком порядке. Аналогичным образом,

• b[x+2] - это соединение b[2],b[3]....b[x],b[x+1].

• Так, в основном, b[n] будет конкатенацией последних x терминов b[i], взятые слева от правого.

• Учитывая параметры, как p и q как запросы, как я могу узнать, какой характер у b[1], b[2], b[3]..... b[x] делает q^я характера b[p] соответствует?

Примечание:x и b[1], b[2], b[3]..... b[x] фиксирована для всех запросов.

Я пробовал принудительно, но длина строки возрастает экспоненциально для больших x. (X < = 100).

---

Пример:

• Когда x=3,

  b[] = a, b, c, a b c, b c abc, c abc bcabc, abc bcabc cabcbcabc, //.... 
  //Spaces for clarity, only commas separate array elements 
  

• Таким образом, для запроса, где p=7, q=5, ответ вернулся бы 3 (что соответствует характеру 'c').

У меня просто трудно понять математику за ней. Язык не проблема

Answer 1

Я написал этот ответ, как я понял, поэтому, пожалуйста, несите меня.

Как уже упоминалось, это намного проще, чтобы выяснить, где персонаж в b[p][q] приходит из числа первоначальных x символов, чем для создания b[p] для больших p. Для этого мы будем использовать петлю, чтобы найти, откуда пришел ток b[p][q], тем самым уменьшив p до тех пор, пока он не станет между 1 и x и q до тех пор, пока не будет 1.

Давайте посмотрим на пример для x=3, чтобы увидеть, если мы можем получить формулу:

p N(p) b[p] 
- ---- ---- 
1 1  a 
2 1  b 
3 1  c 
4 3  a b c 
5 5  b c abc 
6 9  c abc bcabc 
7 17 abc bcabc cabcbcabc 
8 31 bcabc cabcbcabc abcbcabccabcbcabc 
9 57 cabcbcabc abcbcabccabcbcabc bcabccabcbcabcabcbcabccabcbcabc 

Последовательность ясна: N(p) = N(p-1) + N(p-2) + N(p-3), где N(p) является количество символов в р-й элемент b.Учитывая p и x, вы можете просто перечислить все N для диапазона [1, p]. Это позволит вам выяснить, из какого из предшествующих элементов был bb[p][q].

Для иллюстрации, скажем x=3, p=9 и q=45.

1. Диаграмма выше дает N(6)=9, N(7)=17 и N(8)=31. С 45>9+17 вы знаете, что b[9][45] исходит от b[8][45-(9+17)] = b[8][19].
2. Продолжение итеративно/рекурсивно, 19>9+5, поэтому b[8][19] = b[7][19-(9+5)] = b[7][5].
3. сейчас 5>N(4) но 5<N(4)+N(5), поэтому b[7][5] = b[5][5-3] = b[5][2].
4. b[5][2] = b[3][2-1] = b[3][1]
5. С 3 <= x, у нас есть условие завершения, и b[9][45] является c от b[3].

Что-то, как это может быть очень легко вычислить либо рекурсивно или итеративно с учетом запуска p, q, x и b до x. Мой метод требует p элементов массива для вычисления N(p) для всей последовательности. Это может быть выделено в массиве или в стеке, если они работают рекурсивно.

Вот эталонная реализация в ванильным Python (без внешних импорта, хотя NumPy, вероятно, поможет упорядочить это):

def so38509640(b, p, q): 
    """ 
    p, q are integers. b is a char sequence of length x. 
    list, string, or tuple are all valid choices for b. 
    """ 
    x = len(b) 

    # Trivial case 
    if p <= x: 
     if q != 1: 
      raise ValueError('q={} out of bounds for p={}'.format(q, p)) 
     return p, b[p - 1] 

    # Construct list of counts 
    N = [1] * p 
    for i in range(x, p): 
     N[i] = sum(N[i - x:i]) 
    print('N =', N) 

    # Error check 
    if q > N[-1]: 
     raise ValueError('q={} out of bounds for p={}'.format(q, p)) 

    print('b[{}][{}]'.format(p, q), end='') 

    # Reduce p, q until it is p < x 
    while p > x: 
     # Find which previous element character q comes from 
     offset = 0 
     for i in range(p - x - 1, p): 
      if i == p - 1: 
       raise ValueError('q={} out of bounds for p={}'.format(q, p)) 
      if offset + N[i] >= q: 
       q -= offset 
       p = i + 1 
       print(' = b[{}][{}]'.format(p, q), end='') 
       break 
      offset += N[i] 
    print() 
    return p, b[p - 1] 

Вызов so38509640('abc', 9, 45) производит

N = [1, 1, 1, 3, 5, 9, 17, 31, 57] 
b[9][45] = b[8][19] = b[7][5] = b[5][2] = b[3][1] 
(3, 'c') # <-- Final answer 

Аналогично, для примера в вопрос, so38509640('abc', 7, 5) выдает ожидаемый результат:

N = [1, 1, 1, 3, 5, 9, 17] 
b[7][5] = b[5][2] = b[3][1] 
(3, 'c') # <-- Final answer 

Извините, я не мог придумать лучшего имени функции :) Это достаточно простой код, который должен работать одинаково хорошо в Py2 и 3, несмотря на различия в функции/классе range.

Мне было бы очень любопытно узнать, нет ли итеративного решения этой проблемы. Возможно, есть способ сделать это с помощью модульной арифметики или чего-то еще ...