Question

ЕГЭ ИНФОРМАТИКА 8 ЗАДАНИЕ ПОМОГИТЕ ПОЖАЛУЙСТА Даша составляет слова, меняя местами буквы в слове ТИКТОК так, что любые две соседние буквы должны быть различны между собой. Сколько слов, включая исходное, может составить Даша?​

Answer 1

Ответ:

84

Объяснение:

объяснение на питоне

import itertools

s="ТИКТОК"

k=set()

for i in itertools.permutations(s,6):

 b="".join(i)

 if "КК" not in b and "ТТ" not in b:

  k.add(b)

print(len(k))

Answer 2

Для решения этой задачи можно использовать метод динамического программирования.

Обозначим через F(n) количество слов, которые можно составить, используя n букв из слова "ТИКТОК" и удовлетворяющие условию задачи.

Очевидно, что F(1) = 1, так как можно составить только слово "Т". Аналогично, F(2) = 2, так как можно составить слова "ТК" и "КТ".

Для более длинных слов будем рассматривать несколько случаев:

1. Если в слове находится пара одинаковых соседних букв (например, "ТТ"), то все слова, которые можно составить из оставшихся n-2 букв, также удовлетворяют условию задачи. Таким образом, F(n) = F(n-2).

2. Если в слове находится пара различных соседних букв (например, "ТК"), то все слова, которые можно составить из оставшихся n-1 букв, также удовлетворяют условию задачи. Таким образом, F(n) = F(n-1).

Итак, у нас есть рекуррентная формула: F(n) = F(n-1) + F(n-2).

Применяя эту формулу последовательно, мы можем найти значение F(7) (так как слово "ТИКТОК" состоит из 7 букв) и получить ответ на задачу.

F(1) = 1 F(2) = 2 F(3) = F(2) + F(1) = 2 + 1 = 3 F(4) = F(3) + F(2) = 3 + 2 = 5 F(5) = F(4) + F(3) = 5 + 3 = 8 F(6) = F(5) + F(4) = 8 + 5 = 13 F(7) = F(6) + F(5) = 13 + 8 = 21

Таким образом, Даша может составить 21 слово, включая исходное слово "ТИКТОК".