Сортировка информации

Сортировка информации

Мы часто пользуемся сортировкой информации, часто даже сами того не подозревая. Например, многие хранят музыку на компьютере, располагая её в папках по музыкальному стилю (Рок, Поп-музыка, Рэп, Классика и т. п.)

А кто-то предпочитает такие классификации, как: Весёлая/Лирическая; Отечественная/Зарубежная

Самые терпеливые даже распределяют аудиозаписи по исполнителям.

Некоторые люди носят деньги в кошельке в порядке возрастания (убывания) номинала купюр. То есть, сначала 10, потом 50 и т. д. до 5000 рублей.

Для выполнения всех указанных действий необходимо выполнить сортировку. Перечисленные выше классификации достаточно просты и не требуют особо сложных действий для сортировки. Понятно, что, к примеру, композиции Григория Лепса разместятся в папке с названием «Отечественная музыка», а песня «Gangnam Style» – в папке «Зарубежная музыка». Однако иногда сортировка может быть затруднена, если предложенная классификация слишком узкая. Например, песня Димы Билана «Never let you go» может быть отнесена как к отечественной музыке, так как исполняется нашим певцом, так и к зарубежной, так как исполняется на английском языке.

Пожалуй, ни одна задача не породила такого количества решений, как задача сортировки информации. Существует множество программных методов сортировки (метод пузырька, метода Шелла, Хоара и т. п.)

Практическое задание

Задача: Машина Поста состоит из ленты, разбитой на ячейки, и каретки, которая может считывать содержимое обозреваемой ячейки, стирать метки и ставить метки. Создайте компьютерную модель машины Поста, вычитающей два числа (Левое число всегда больше правого). Каретка вначале стоит на правой крайней позиции вычитаемого числа.

Указание:

Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»

Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

1. Х - стираем левый символ у Q2. →3. ? 4, 54. Stop - стоп если затерли Q=05. ←6. ? 5, 7 - цикл поиска P7. Х - стираем правый символ у P8. →9. ? 8, 1 - ищем Q

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P. Проверьте работу программы.

Домашнее задание:выполнить задание.

⇐ Предыдущая 1 23