|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[2] Многие алгоритмы используют сортировку в качестве промежуточного шага. Имеется много разных алгоритмов сортировки; выбор в конкретной ситуации зависит от длины сортируемой последовательности, от того, в какой степени она уже отсортирована, а также от типа имеющейся памяти (оперативная память, диски, магнитные ленты). Алгоритм считают правильным (correct), если на любом допустимом (для данной задачи) входе он он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. В этом случае говорят, что алгоритм решает (solves) данную вычислительную задачу. Неправильный алгоритм может (для некоторого входа) вовсе не остановиться или дать неправильный результат. (Впрочем, это не делает алгоритм заведомо бесполезным - если ошибки достаточно редки. Подобная ситуация встретится нам в главе 33 при поиске больших простых чисел. Но это всё же скорее исключение, чем правило.) Алгоритм может быть записан на русском или английском языке, в виде компьютерной программы или даже в машинных кодах - важно только, чтобы процедура вычислений была чётко описана. Мы будем записывать алгоритмы с помощью псевдокода (pseudocode), который напомнит вам знакомые языки программирования (Си, Паскаль, Алгол). Разница в том, что иногда мы позволяем себе описать действия алгоритма «своими словами», если так получается яснее. Кроме того, мы опускаем технологические подробности (обработку ошибок, скажем), которые необходимы в реальной программе, но могут заслонить существо дела. Сортировка вставками Сортировка вставками (insertion sort) удобна для сортировки коротких последовательностей. Именно таким способом обычно сортируют карты: держа в левой руке уже упорядоченные карты и взяв правой рукой очередную карту, мы вставляем её в нужное место, сравнивая с имеющимися и идя справа налево (см. рис. 1.1) Запишем этот алгоритм в виде процедуры Insertion-Sort, параметром которой является массив А[1.. п] (последовательность длины п, подлежащая сортировке). Мы обозначаем число элементов в массиве А через length[A]. Последовательность сортируется «на месте» (in place), без дополнительной памяти (помимо массива мы используем лишь фиксированное число ячеек памяти). После выполнения процедуры Insertion-Sort массив А упорядочен по возрастанию. Рис. 1.1 Сортировка карт вставками Insertion-Sort (А) 1 for j <- 2 to length[A] 2 do key <3> добавить A[j] к отсортированной части A[l. .j - 1]. 4г <- j - 1 5while i > 0 and А [г] > fcet/ 6do A[i + A[i] 7г <- i - 1 8A[i + l]<r- key Рис. 1.2 Работа процедуры INSERTION-SORT для входа А = (5,2,4,6,1,3). Позиция j показана кружком. На рис. 1.2 показана работа алгоритма при А = (5,2,4,6,1,3). Индекс j указывает «очередную карту» (только что взятую со стола). Участок А[1. .j - 1] составляют уже отсортированные карты (левая рука), a A[j + 1. .га] - ещё не просмотренные. В цикле for индекс j пробегает массив слева направо. Мы берём элемент A[j] (строка 2 алгоритма) и сдвигаем идущие перед ним и большие его по величине элементы (начиная с j - 1-го) вправо, освобождая место для взятого элемента, (строки 4-7). В строке 8 элемент A[j] помещается в освобождённое место. Псевдокод Вот основные соглашения, которые мы будем использовать: 1.Отступ от левого поля указывает на уровень вложенности. Например, тело цикла for (строка 1) состоит из строк 2-8, а тело цикла while (строка 5) содержит строки 6-7, но не 8. Это же правило применяется и для if-then-else. Это делает излишним специальные команды типа begin и end для начала и конца блока. (В реальных языках программирования такое соглашение применяется редко, поскольку затрудняет чтение программ, переходящих со страницы на страницу.) 2.Циклы while, for, repeat и условные конструкции if, then, else имеют тот же смысл, что в Паскале. 3.Символ > начинает комментарий (идущий до конца строки). 4.Одновременное присваивание i <- j <- е (переменные i и j получают значение е) заменяет два присваивания j <- е и г <- j (в этом порядке). 5.Переменные (в данном случае i,j,key) локальны внутри процедуры (если не оговорено противное). 6.Индекс массива пишется в квадратных скобках: A[i] есть г-ж элемент в массиве А. Знак «..» выделяет часть массива: А[1. .j] обозначает участок массива А, включающий А[1], А[2],..., A[j]. 7.Часто используются объекты (objects), состоящие из нескольких полей (fields), или, как говорят, имеющие несколько атрибутов (attributes). Значение поля записывается как имя-Поля[имя-объекта]. Например, длина массива считается его атрибутом и обозначается length, так что длина массива А запишется как length[A]. Что обозначают квадратные скобки (элемент массива или поле объекта), будет ясно из контекста. Переменная, обозначающая массив или объект, считается указателем на составляющие его данные. После присваивания у <- х для любого поля / выполнено f[y] = f[x]. Более того, если мы теперь выполним оператор f[x] <- 3, то будет не только f[x] = 3, но и f[y] = 3, поскольку после у <- х переменные хну указывают на один и тот же объект. Указатель может иметь специальное значение NIL, не указывающее ни на один объект. 8.Параметры передаются по значению (by value): вызванная процедура получает собственную копию параметров; изменение параметра внутри процедуры снаружи невидимо. При передаче объек- |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||