Question

Сдать решение задачи 4-Сортировка Задача 4: Сортировка В библиотеке есть 8 томов полного собрания сочинений одного писателя. Библиотекарь обозначил их латинскими буквами от A до H в порядке выхода томов, но оказалось, что они стоят на полке в обратном порядке: HGFEDCBA Библиотекарь решил переставить эти книги так, чтобы они шли по порядку: ABCDEFGH. За одну операцию библиотекарь может взять две или более подряд идущих книг, достать их с полки и, не меняя порядок следования книг, переставить их в какое-то другое место на полке (между другими какими-то книгами, в начало или в конец полки). Например, библиотекарь может взять три тома FED, достать их с полки (на полке останутся тома HGCBA), и поставить их так, чтобы перед ними оказалось 4 тома. Получится HGCBFEDA. Можно поставить их в начало полки, тогда получится последовательность FEDHGCBA, а если поставить их в конец, то получится HGCBAFED. Помогите библиотекарю упорядочить этот ряд книг за минимальное число операций. Ответ запишите в виде последовательности строк, каждая строка должна соответствовать какому-то расположению томов на полке, то есть быть перестановкой символов ABCDEFGH. Первой строкой ответа должна быть HGFEDCBA, последней строкой ответа должна быть ABCDEFGH, и каждая строка ответа (кроме первой) должна получаться из предыдущей применением указанной операции. Обратите внимание, что переставляемый фрагмент не может состоять только из одной книги. То есть ответ должен иметь такой вид (вместо многоточий находится несколько пропущенных строк). HGFEDCBA ... ... ... ABCDEFGH Чем меньше операций будет в вашем алгоритме, тем больше баллов вы получите, при условии, что в результате применения вашего алгоритма тома будут расставлены по порядку от A до H.

Answer 1

Ответ:

HGFEDCBA

GFEDCBAH

DCBAGFEH

ADCBGFEH

ABDCGFEH

ABDCFEGH

ABCFDEGH

ABCDEFGH

Пошаговое объяснение:

Answer 2

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

1. Сначала переместим том H в начало, чтобы получить HGFEDCBA.
2. Затем переместим том G рядом с H, чтобы получить HGFECDAB.
3. Переместим том F к G и H, чтобы получить HGFCEDAB.
4. Переместим том E к F, G и H, чтобы получить HGFECEDAB.
5. Переместим том D к E, F, G и H, чтобы получить HGFEDECAB.
6. Переместим том C к D, E, F, G и H, чтобы получить HGFCDEEAB.
7. Переместим том B к C, D, E, F, G и H, чтобы получить HGFBCCDEEAA.
8. Наконец, переместим два последних тома AA в конец, чтобы получить ABCDEFGH.

Итак, вот последовательность шагов:

1. HGFEDCBA
2. HGFECDAB
3. HGFCEDAB
4. HGFECEDAB
5. HGFEDECAB
6. HGFCDEEAB
7. HGFBCCDEEAA
8. ABCDEFGH

Этот алгоритм выполняет упорядочивание с минимальным числом операций.