Методические указания к выполнению контрольных работ по дисциплине "Основы программирования" (стр. 3 из 40)
Команды, выполняемые Сидом, весьма разнообразны. Простейшая команда просто велит ему перейти к другой ячейке. Если ее номер равен 20, Сиду нужно будет сделать несколько шагов к началу забора, а если это 
байт – ему придется мчаться к самому его концу. Команда перехода может быть условной, например, Сид перейдет к ячейке 20 лишь в том случае, если число, хранящееся в пятнадцатом байте, больше нуля.
Представим себе, что перед выполнением программы в пятнадцатой ячейке хранится число 10. Раз оно больше нуля, Сид перейдет к двадцатому байту, выполнит команды, записанные в ячейках с номерами 21¸30, и, если содержимое 15-й ячейки не изменилось, 31-й байт вновь отошлет его назад, и так он будет крутиться, пока хватит сил. Если же команды, хранящиеся в байтах 21¸30, после многих пробежек Сида запишут нуль в ячейку 15, тот вместо двадцатого байта перейдет к следующей команде, начало которой хранится в ячейке 32. Иными словами, Сид будет выполнять команды последовательно, одну за другой, пока ему не прикажут перейти к иной ячейке, и после очередной пробежки вдоль забора он снова начнет выполнять команды последовательно. И так будет продолжаться до тех пор, пока он не наткнется на команду «Стоп».
Впрочем, еще раньше он может встретить число, которого нет в его таблице, или же предписание перейти к 
доске забора, в то время как в нем их всего 
. И тогда Сид застынет в недоумении или побежит жаловаться Тому. А когда такое случается с настоящим компьютером, на экране возникает сообщение: «Программа выполнила недопустимую операцию и будет закрыта».
Комбинация Тома, Сида и забора, с которой мы только что познакомились, мало похожа на реальный компьютер, хотя в ней, как ни странно, есть все его главные компоненты: память (забор), процессор, выполняющий записанные в памяти команды и пользующийся хранящимися там же данными (Сид), и операционная система, показывающая процессору начало программы (Том).
Первые два компонента (процессор и память) представляют собой мертвый набор микросхем, третья же (операционная система) оживляет эту груду железа, делает возможным запуск программ, взаимодействие со вспомогательными устройствами памяти (жесткими дисками) и многое другое. Собственно, операционная система, – это тоже программа, только самая главная, управляющая другими, прикладными программами, такими как MS Word или Excel.
Итак, для работы компьютера необходимы программы, создаваемые людьми, но процессор компьютера, как мы знаем, понимает только двоичные коды. И первые (сейчас уже легендарные) программисты вынуждены были выписывать на бланках длинные последовательности нулей и единиц.
Эта работа была крайне напряженной – не только потому, что люди плохо воспринимают двоичные коды, но и потому, что записанные таким образом программы очень трудно менять. Ведь включение какой-то команды «растягивает программу», команды наползают на данные, а перенос данных в другое место памяти меняет номера ячеек, к которым обращается программа! Все это делает программирование в двоичных кодах крайне ненадежным, изнурительным и опасным.
Вот почему очень скоро программисты занялись облегчением собственного труда. И поскольку были они программистами, то и придумали для собственной пользы специальные программы – ассемблеры, которые могли перевести команды процессора, записанные «человеческим» языком – с помощью букв и десятичных чисел, – в двоичные коды, понимаемые процессором.
Ассемблеры были гигантским шагом вперед, но и они требовали от первых программистов мыслить на языке машины, а не человека. Программирование на ассемблере требовало знания многочисленных команд процессора, причем программа, написанная для одного процессора, не могла быть выполнена другим процессором с иной системой команд.
Поэтому вслед за ассемблерами были изобретены компиляторы – программы, которые воспринимали язык программирования, понятный человеку и не зависящий от конкретного процессора. Чтобы такое стало возможным, нужно было один раз «помучиться» и написать (на языке ассемблера) компилятор для данного процессора, а затем уже пользоваться языком, понятным и человеку, и компилятору, или, как говорят, языком высокого уровня. К числу таких языков относятся Pascal, Fortran, С и, конечно же, C++.
Создавая ассемблеры и компиляторы, программисты в миллионы раз расширили свои возможности. Число команд, записанных двоичными кодами, едва ли может превысить несколько тысяч. А на языках высокого уровня уже написаны и работают гигантские программы, в которых десятки, сотни миллионов строк.
Особенно пригоден для разработки очень больших программ язык высокого уровня C++. В нём есть возможность создавать объекты – аналоги тех многочисленных вещей, которые нас окружают. И телевизор, и стиральная машина, и компьютер, и тостер имеют внутреннее устройство, нам недоступное, а также интерфейс, то есть кнопки, ручки и т.д., с помощью которых этими объектами можно управлять. Нажимая кнопку на пульте управления, мы не задумываемся о том, как устроен телевизор, нам достаточно знать, что эта кнопка переключит телевизор на ОРТ, а вот эта увеличит громкость.
Как и домашние вещи, объекты языка C++ имеют внутреннее устройство, скрытое от непосвященных, и интерфейс – так называемые собственные функции, или методы, с помощью которых такими объектами можно управлять. Собственные функции похожи на кнопки пульта управления телевизора. Пользуясь собственными функциями, мы не думаем о внутреннем устройстве объекта. Сам объект может быть гораздо сложнее телевизора, и, возможно, его разрабатывали десятки высококвалифицированных программистов, однако собственные функции этого объекта очень просты, и, чтобы научиться ими пользоваться, достаточно пары часов.
Разработка программы на языке C++ обычно начинается с тщательного анализа задачи, выделения в ней объектов и разработки соответствующих интерфейсов. Далее каждый объект можно создавать независимо от других. Остальные программисты, занятые использованием самих объектов, вовсе не обязаны ждать, пока их создадут. Им достаточно знать только интерфейс этих пока не существующих объектов и спокойно писать свою часть программы. Это значит, что C++ позволяет разбить сложную задачу на множество мелких и наладить промышленное, почти конвейерное, производство больших программ.
1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АЛГОРИТМИЗАЦИИ И
1.1. Основные понятия алгоритмизации
«Многие не сведущие в математике люди думают, что поскольку назначение аналитической машины Бэббиджа – выдавать результаты в численном виде, то природа происходящих в ней процессов должна быть арифметической и численной, а не алгебраической и аналитической.
Но они ошибаются. Машина может упорядочивать и комбинировать числовые значения так же, как и буквы или любые другие символы общего характера.
В сущности, при выполнении соответствующих условий она могла бы выдавать результаты и в алгебраическом виде».
Августа Ада, графиня Лавлейс (1844)
Основоположницей программирования считают Августу Аду – дочь великого английского поэта Дж. Г. Байрона. В 19 веке в Англии впервые появилось настоящее арифметическое устройство – аналитическая машина Бэббиджа: с регистрами, сумматором и другими атрибутами, присущими процессору современного компьютера. Программы для такого устройства расписывались на бумаге. Каждая операция совершалась поворотом особой ручки или нажатием рычага такой машины. Большинство идей и принципов программирования для аналитической машины Бэббиджа было рассмотрено в книге Августы Ады* «Комментарии». Позднее появился особый вид деятельности – программирование, а в последствии возникла профессия программиста.
Понятие «алгоритм» является основным для всей области компьютерного программирования, поэтому начать мы должны с тщательного анализа этого термина. Слово «алгоритм» (англ. algorithm) уже само по себе представляет большой интерес.
Историки-математики обнаружили истинное происхождение этого слова: оно берет начало от имени автора знаменитого персидского учебника по математике, Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми (ок. 825 г.). Аль-Хорезми написал знаменитую книгу «Книга о восстановлении и противопоставлении» (перс. Китаб аль-джебр валь-мукабала). От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово – «алгебра».
В старинном немецком математическом словаре Vollstandiges mathematisches Lexicon (Лейпциг, 1747) дается следующее толкосание латинского слова algorithmus: «Этот термин включает в себя понятие о четырех типах арифметических операций, а именно: о сложении, умножении, вычитании и делении». Латинское выражение algorithmus infinitesimalis в то время использовалось для определения способов выполнения действий с бесконечно малыми величинами, открытых великим математиком Лейбницем.
Пример 1-1. Алгоритм Евклида.
Приблизительно через 100 лет после появления аналитической машины Бэббиджа была создана первая электронная вычислительная машина – специально для выполнения атомного проекта в Лос-Аламосе (США). В это время (конец 40-х – начало 50-х годов 19 века) слово «алгоритм» чаще всего ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя двух чисел. Этот алгоритм далее будем называть «алгоритмом Е».