Question

Задача 2. книжная полка. в библиотеке на полке стоят 8 томов полного собрания сочинений одного писателя. библиотекарь обозначил их латинскими буквами от а до н в порядке выхода томов. получилась следующая последовательность: e d g h c b f a библиотекарь решил переставить эти книги так чтобы они шли по порядку : a b c d e f g h. за одно действие библиотекарь может взять несколько подряд идущих книг, достать их с полки и, не меняя порядок следования книг, перевернуть их и поставить на место в обратном порядке. например если библиотекарь достанет книги H по F и перевернет их то новый порядок следования книг будет таким: E D G F B C G H A. помогите библиотекарю упорядочить этот ряд книг за минимальное число действий

Answer 1

Учитывая, что 8 букв можно переставить примерно 40 тысячами способов, можно просто запустить поиск в ширину, сохранить для всех перестановок то, из какой строчки они получились, и потом восстановить ответ для строчки abcdefgh.

Код на python 3:
from queue import Queue

to_process = Queue()
to_process.put(("edghcbfa", None))
prec = {}

while not to_process.empty():
    s, prev = to_process.get()
    if s in prec:
        continue
    for i in range(7):
        for j in range(i + 1, 8):
            if i == 0:
                next_s = s[j::-1] + s[j+1:]
            else:
                next_s = s[:i] + s[j:i-1:-1] + s[j+1:]
            if next_s not in prec:
                to_process.put((next_s, s))
    prec[s] = prev

current = "abcdefgh"
print(current)
while prec[current] is not None:
    current = prec[current]
    print(current)

Вывод программы:
abcdefgh
edcbafgh
edcbhgfa
edbchgfa
edghcbfa

Answer 2

Problem 2: Книжная полка

В данной задаче библиотекарю необходимо упорядочить ряд книг на полке. Изначально на полке стоят 8 томов полного собрания сочинений одного писателя, обозначенные латинскими буквами от 'а' до 'н' в порядке их выхода. Однако, библиотекарь хочет переставить эти книги так, чтобы они шли по порядку от 'а' до 'н'. Библиотекарь может взять несколько подряд идущих книг, достать их с полки, перевернуть их и поставить на место в обратном порядке, не меняя порядок следования книг.

Например, если библиотекарь достанет книги 'h', 'g', 'f', 'e' и перевернет их, то новый порядок следования книг будет таким: 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'.

Задача: Помогите библиотекарю упорядочить этот ряд книг за минимальное число действий.

Решение:

Для решения этой задачи можно использовать следующий алгоритм:

1. Найдите первую книгу, которая не на своем месте. В данном случае это книга 'e'. 2. Достаньте все книги, начиная с этой и до конца ряда. 3. Переверните их порядок. 4. Поставьте их обратно на полку. 5. Повторите шаги 1-4, пока все книги не будут на своих местах.

Применяя этот алгоритм, мы сможем упорядочить ряд книг за минимальное число действий.

Решение:

1. Достаем книги 'e', 'd', 'g', 'h' и переворачиваем их порядок. Новый порядок: 'h', 'g', 'd', 'e'. 2. Ставим книги 'h', 'g', 'd', 'e' обратно на полку. 3. Достаем книги 'c', 'b', 'f' и переворачиваем их порядок. Новый порядок: 'f', 'b', 'c'. 4. Ставим книги 'f', 'b', 'c' обратно на полку. 5. Достаем книгу 'a' и ставим ее обратно на полку.

Теперь ряд книг упорядочен по порядку от 'а' до 'н': 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'.

Ответ: Библиотекарь может упорядочить этот ряд книг за минимальное число действий, следуя описанному алгоритму.