Question

Ваня придумал новый алгоритм сортировки и сейчас тренируется на кубиках с цифрами, чтобы понять, как он работает. Перед ним на столе лежат кубики с числами от 1 до 10 (на каждом кубике записано одно число), выложенные в таком порядке: 5 4 10 1 6 7 8 9 2 3 За одну операцию Ваня берет несколько рядом стоящих кубиков как одну конструкцию, переворачивает и кладет на прежнее место. Например, если бы кубики лежали в таком порядке: 1 2 3 4 5 6 7 8 9 10, а Ваня взял бы кубики начиная с кубика с цифрой 4 и заканчивая кубиком с цифрой 9 и перевернул бы, то получилась бы такая последовательность: 1 2 3 9 8 7 6 5 4 10. То, что какие-то кубики после выполнения подобных операций окажутся лежащими вверх ногами, Ваню не смущает. Кроме того, Ваня различает кубик с цифрой 6 и кубик с цифрой 9 (они разного цвета, поэтому невозможно одну цифру получить из другой при перевороте). Помогите Ване понять, какое наименьшее количество таких операций потребуется, чтобы кубики стали лежать в порядке возрастания: 1 2 3 4 5 6 7 8 9 10. Комментарий. Если бы у него было всего 4 кубика и они лежали в таком порядке: 4 1 3 2, то наименьшее количество операций было бы равно двум: сначала переворачиваем кусок из первых двух кубиков слева, получаем 1 4 3 2, затем переворачиваем кусок из трех кубиков справа, получаем 1 2 3 4.

Answer 1

3 операции.

Нам дано: 5 4 10 1 6 7 8 9 2 3

Сначала меняем с 1 по 9, получаем: 5 4 10 9 8 7 6 1 2 3

Потом меняем с 10 по 3, получаем: 5 4 3 2 1 6 7 8 9 10

В заключение меняем с 5 по 1, получаем: 1 2 3 4 5 6 7 8 9 10

Итого 3 операции.

Answer 2

Для решения этой задачи мы можем использовать жадный алгоритм. Жадный алгоритм будет заключаться в том, чтобы двигаться слева направо по массиву кубиков и, если текущий кубик не стоит на своем месте, применить операцию переворота над некоторой частью массива, чтобы поставить его на правильное место.

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

В данном случае нам нужно отсортировать массив: 5 4 10 1 6 7 8 9 2 3, чтобы получить 1 2 3 4 5 6 7 8 9 10.

1. Начнем с первого кубика. Кубик с цифрой 1 находится на 4-м месте, поэтому применим операцию переворота для кубиков с цифрами 5, 4, 10 и 1. Массив станет следующим: 1 10 4 5 6 7 8 9 2 3.

2. Теперь, когда кубик с цифрой 1 уже на своем месте, перейдем к следующему кубику с цифрой 2. Он находится на 9-м месте. Применим операцию переворота для кубиков с цифрами 1, 10, 4, 5, 6, 7, 8 и 9. Массив станет следующим: 1 2 9 8 7 6 5 4 10 3.

3. Теперь кубики с цифрами 1 и 2 уже стоят на своих местах, перейдем к кубику с цифрой 3. Он находится на 10-м месте. Применим операцию переворота для всех кубиков с цифрами от 1 до 10. Массив станет следующим: 1 2 3 10 4 5 6 7 8 9.

4. Теперь кубики с цифрами от 1 до 3 уже стоят на своих местах, перейдем к кубику с цифрой 4. Он находится на 5-м месте. Применим операцию переворота для кубиков с цифрами от 1 до 5. Массив станет следующим: 1 2 3 4 5 10 9 8 7 6.

5. Теперь кубики с цифрами от 1 до 5 уже стоят на своих местах, перейдем к кубику с цифрой 6. Он находится на 10-м месте. Применим операцию переворота для всех кубиков с цифрами от 1 до 6. Массив станет следующим: 1 2 3 4 5 6 7 8 9 10.

Теперь массив отсортирован по возрастанию. Всего было выполнено 5 операций переворота, и это наименьшее количество операций, необходимых для сортировки массива.