Задача 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. помогите библиотекарю упорядочить этот ряд книг за минимальное число действий

Учитывая, что 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