Question

На заводе по производству кирпичей установили автоматическую линию. Главной задачей линии является сортировка по весу некоторого поддона с кирпичами. Вес кирпича варьируется от 1 до 9 кг. Количество кирпичей в линии — 7. Кирпичи лежат в лотках, робот проверяет их последовательно одно за другим, проходя от первого до последнего лотка. Робот может менять местами только соседние кирпичи. Если левый кирпич больше правого, они меняются местами. После прохождения всей линии до последнего кирпича, робот возвращается к первому кирпичу и начинает сравнение заново, переставляя, если нужно, соседние кирпичи до предпоследнего и так далее. Таким образом, при многократном возврате линия становиться отсортированной по возрастанию веса кирпичей.

Например, веса кирпичей в исходном порядке: 8 1 2 4 5 3 5
Первое прохождение до последнего кирпича: 1 8 2 4 5 3 5 / 1 2 8 4 5 3 5 / 1 2 4 8 5 3 5 / 1 2 4 5 8 3 5 / 1 2 4 5 3 8 5 / 1 2 4 5 3 5 8 . (6 замен)
Второе прохождение до 6-го кирпича: 1 2 4 3 5 5 8 (1 замена)
Третье прохождение до 5-го кирпича: 1 2 3 4 5 5 8 (1 замена).

Всего произошло 8 замен.




Какое количество замен произведет робот для сортировки линии кирпичей со следующим порядком весов: 7 9 1 2 5 2 3?

Answer 1

Ответ:

1. 7 1 9 2 5 2 3

2. 7 1 2 9 5 2 3

3. 7 1 2 5 9 2 3

4. 7 1 2 5 2 9 3

5. 7 1 2 5 2 3 9

6. (возврат к первому) 1 7 2 5 2 3 9

7. 1 2 7 5 2 3 9

8. 1 2 5 7 2 3 9

9. 1 2 5 2 7 3 9

10. 1 2 5 2 3 7 9

11. (возврат к первому) 1 2 2 5 3 7 9

12. 1 2 2 3 5 7 9

Answer 2

Объяснение:

7 9 1 2 5 2 3

Первое прохождение до последнего кирпича:

7 1 9 2 5 2 3 / 7 1 2 9 5 2 3 / 7 1 2 5 9 2 3 / 7 1 2 5 2 9 3 / 7 1 2 5 2 3 9 (5 замен)

Второе прохождение до 6-го кирпича:

1 7 2 5 2 3 9 / 1 2 7 5 2 3 9 / 1 2 5 7 2 3 9 / 1 2 5 2 7 3 9 / 1 2 5 2 3 7 9 (5 замен)

Третье прохождение до 5-го кирпича:

1 2 2 5 3 7 9 / 1 2 3 3 5 7 9 (2 замены)

Всего произошло 12 замен.