Возврат, Сегментация текста

Question

Я не мог разобраться с этим алгоритмом мозгового штурма! Может ли кто-нибудь помочь?

-------- Описание --------

Предположим, вы ученый, который поиск определенных видов генов. Вы знаете, что искомый ген должен быть сформирован из следующих блоков \

AT GG CTAC

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

'A', 'G', 'C', 'T', вы должны определить, может ли данный ген быть сформирован из допустимых блоков. Примеры генов, которые могут быть сформированы с использованием действительных блоков:

GGATATCTAC CTACGGGG

Примеры генов, которые не могут быть сформированы с использованием действительных блоков:

CCC GGCAC

Question!
1. How many possible choice you have after each reduction?
2. Try to draw a recursion tree for this algorithm
3. What kind of data do you need to store after each reduction?
4. Try to write a recurrence relation for the running time of this algorithm.
5. Try to estimate the running time from the above recurrence relation. Is running time exponential or
polynomial in terms of n, the length of a gene?

Answer 1

python код для возврата назад со сложностью n n l с n - количество блоков здесь 3, а L - длина гена. Для дерева я печатать текущий текст тогда? затем проверяемый элемент для добавления.

def genes(chaine, elements, result):
  print()
  if(chaine == ""):
      return result
  ctn = 1
  for elem in elements:
      print(" ".join([" "]*len(chaine)*ctn), "".join(result) + "? " + elem, end = '')
      if(chaine.startswith(elem)):
          return genes(chaine[len(elem):], elements, result + [elem])
      ctn = ctn + 1

   return 0


result = genes("GGATGGATCTAC", ["GG", "AT", "CTAC"], [])
print(result)

Вывод:

                  ? GG
                GG? GG                                        GG? AT
            GGAT? GG
        GGATGG? GG                        GGATGG? AT
    GGATGGAT? GG                GGATGGAT? AT                        GGATGGAT? CTAC

['GG', 'AT', 'GG', 'AT', 'CTA C «]