Александра
4 год назад
В библиотеке на полке стоят 8 томов полного собрания сочинений одного писателя .Библиотекарь обозначил их латинскими буквами от A до H в порядке выхода томов .Получилась следующая последовательность. E D G H C B F A Библиотекарь решил переставить эти книги так, чтобы они шли по порядку A B C D E F G H . За одно действие библиотекарь может взять неКак узнать сколько подряд идущих книг , достать их с полки и , не меняя порядок следования книг ,перевернуть их и поставить на место в обратном порядок. Например ,если библиотекарь достанет книги c H по F и перевернет их , то новый порядок следования книг будет таким: E D G F B C G H A. Пожалуйста посчитайте библиотекарю упорядочить это ряд книг за минимальное число действий. То, что некоторые книги окажутся перевернутыми вверх ногами ,библиотекарю не важно Ответом на эту задачу является последовательность операций . Одна операция записывается в одной строке . Описание каждой операции состоит из двух латинских букв от (A до H ), которые являются обозначениями крайних томов в переворачиваемом фрагменте ,например, выше был рассмотрен пример для операции H F
ОТВЕТЫ
Трифон
Oct 24, 2020
Учитывая, что 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
Соственно, такой:
G B
B C
H A
E A
Код на 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
Соственно, такой:
G B
B C
H A
E A
6
Смежные вопросы:
