Программный способ представления алгоритмов
Двоичный поиск
При сравнении целевого значения со средним элементом отсортированного списка возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях можно отбросить половину списка. Когда целевое значение меньше среднего элемента, известно, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента, известно, что если оно имеется в списке, то находится после этого среднего элемента. Этой информации достаточно, чтобы стало возможно одним сравнением отбросить половину списка. При повторении этой процедуры можно отбросить половину оставшейся части списка. Очевидно, что такой алгоритм будет работать только на предварительно отсортированном списке.
При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются компьютеры или иные вычислительные устройства (однокристальные микроЭВМ, промышленные компьютеры, технологические контроллеры и др.), поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.
В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения. В зависимости от степени детализации предписаний обычно определяется уровень языка программирования — чем язык менее детален, тем выше его уровень. По этому критерию можно выделить следующие уровни языков программирования (рис. 14.9)1:
□ машинно-ориентированные языки — машинные языки и языки ассемблера;
□ машинно-независимые языки — языки высокого уровня.
Рис. 14.9. Классификация языков программирования
Машинно-ориентированные языки — это языки низкого уровня, требующие указания мелких деталей процесса обработки данных. Языки же высокого уров¬ня имитируют естественные языки, используя некоторые слова естественного языка и общепринятые математические символы. Эти языки более удобны для человека.
Языки высокого уровня делятся на процедурные, логические и объектно-ориен- тированные.
□ Процедурные, или алгоритмические, языки (Basic, Pascal, С и др.) предназначены для однозначного описания алгоритмов в виде некоторой последовательности операторов языка.
□ Логические языки (Prolog, Lisp и др.) ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи, из которого должно следовать решение.
□ Объектно-ориентированные языки (Object Pascal, C++, Java, C# и др.), в основе которых лежит понятие объекта, сочетают в себе данные и действия над ними. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче. Описание действитель¬ности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.