@BMinhoj

Как перевести мою логику решения в доказательство?

Задача такая:
В ряд написано n чисел. Разрешается взять любой начальный отрезок ряда a1, a2, . . . , ak и переставить его числа в обратном порядке: ak, ak−1, . . . , a1. Докажите, что возможно расставить числа в
порядке возрастания после применения нескольких таких операций
У меня такая идея её решения
1. Найдем самый минимальный элемент. Пусть он находится на позиции k.
2. Переворачиваем отрезок a_1 .... a_k. Получаем отсортированный массив длины 1
3. Найдем самый минимальный элемент, начиная уже с позиции 2. Пусть он находится на позиции k.
4. Переворачиваем отрезок a_2 .... a_k. Получаем отсортированный массив длины 2
3. Найдем самый минимальный элемент, начиная уже с позиции 3. Пусть он находится на позиции k.
4. Переворачиваем отрезок a_3 .... a_k. . Получаем отсортированный массив длины 3
И так далее, пока не получим отсортированный массив

Но мне нужно доказать её мат. индукцией
  • Вопрос задан
  • 102 просмотра
Решения вопроса 1
Alexandroppolus
@Alexandroppolus
кодир
Найти k - позицию максимального элемент. Если k < n, то сделать 2 шага: разворот 1...k и разворот 1...n. Теперь максимум точно в конце, и задача свелась к сортировке первых n-1 чисел.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@galaxy
Индукцией вроде так:
1. База: ряд из 2-х элементов - либо уже отсортирован, либо сортируется переворачиванием всего ряда.
2. Пусть мы знаем как отсортировать ряд из k элементов, рассмотрим ряд a_1 ... a_k a_k+1, где первые k элементов отсортированы. Далее три случая:
  • a_k+1 больше всех a_1 ... a_k - ряд уже отсортирован
  • a_k+1 меньше всех a_1 ... a_k - переворачиваем a_1 ... a_k, затем переворачиваем обратно весь ряд (a_k ... a_1 a_k+1)
  • a_k+1 должен идти по порядку между некоторыми a_m и a_m+1:
    1. переворачиваем весь ряд a_1 ... a_k+1
    2. переворачиваем ряд a_k+1 ... a_m+1 (получится: a_m+1 ... a_k a_k+1 a_m a_m-1 ... a_1)
    3. переворачиваем ряд a_m+1 ... a_k (получится: a_k ... a_m+1 a_k+1 a_m a_m-1 ... a_1) - новый элемент в нужной позиции
    4. переворачиваем снова весь ряд

Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы