4384

Основные понятия программирования на С++. Алгоритмы

Лекция

Информатика, кибернетика и программирование

Основные понятия программирования на С++. Алгоритмы Языки программирования Компьютер работает по программам, которые составляет для него человек. Человек пишет программы, пользуясь языками программирования. За последние несколько десятилетий языки п...

Русский

2012-11-18

67.87 KB

66 чел.

Основные понятия программирования на С++. Алгоритмы

Языки программирования

Компьютер работает по программам, которые составляет для него человек. Человек пишет программы, пользуясь языками программирования. За последние несколько десятилетий языки программирования претерпели значительную эволюцию. Вначале программисты работали с ограниченным набором примитивных команд, представлявших собой машинный язык. Эти команды состояли из длинных строк нулей и единиц. Вскоре был изобретен ассемблер, способный преобразовывать в машинные команды более понятные для человека инструкции (например, ADD (добавить) и MOV (переместить)).

Со временем были созданы языки высокого уровня, такие как BASIC, FORTRAN, PASCAL или COBOL. Благодаря им появилась возможность программировать, используя логические конструкции из слов и предложений, например, “Let i = 100”. В языках высокого уровня одна команда соответствует целой подпрограмме, написанной на ассемблере.

Инструкции языка высокого уровня переводятся на машинный язык с помощью специальных программ: интерпретаторов и компиляторов.

 Интерпретатор превращает инструкции программы в команды машинного кода последовательно, по мере чтения текста программы.

 Компилятор преобразует исходный код программы в некоторую промежуточную форму – объектный файл. Этот этап называется компиляцией. Затем компилятор вызывает программу компоновки, которая превращает объектный файл в исполняемый файл программы.

С интерпретатором работать проще, поскольку команды программы выполняются в той последовательности, в какой они написаны. В некоторых языках (например, Visual Basic 6) роль интерпретатора выполняет динамическая библиотека. Интерпретатором языка Java является виртуальная машина (Virtual Machine, или VM).

В процессе компиляции возникают дополнительные этапы преобразования исходного кода (читаемого людьми) в объектный код (который читается машинами). Наличие дополнительного этапа создает определенные неудобства, но скомпилированные программы выполняются гораздо быстрее, поскольку трансляция исходного кода в машинный язык, отнимающая достаточно много времени, выполняется только один раз во время компиляции, и не производится во время выполнения программы.

Еще одно преимущество компилируемых языков программирования заключается в том, что программы, написанные на этих языках, могут выполняться на компьютерах, не обладающих соответствующим компилятором. При работе же с интерпретируемыми языками для выполнения готовой программы необходимо обязательно иметь соответствующую программу-интерпретатор.

  1.  Структурное программирование

Основная идея структурного программирования заключается в следующем. Компьютерную программу можно представить в виде набора задач. Любая задача, которая слишком сложна для простого описания, должна быть разделена на несколько более мелких составных задач, и это деление необходимо продолжать до тех пор, пока задачи не станут достаточно простыми для понимания. Таким образом, в соответствии с принципом структурного программирования сложная компьютерная программа делится на множество простых подпрограмм.

Преимуществом такого подхода является возможность многократного использования подпрограмм. Это приводит к удешевлению программирования, поскольку одну и ту же подпрограмму использует множество людей, и к повышению его качества, поскольку программы многократного использования, как правило, разрабатывают программисты высокого класса.

 

  1.  Объектно-ориентированное программирование

Структурное программирование до сих пор остается довольно успешным способом решения сложных проблем. Однако к концу 1980-х годов слишком очевидными стали некоторые его недостатки. К сожалению, структурное программирование отделяет структуры данных от функций, управляющих ими. Кроме того, в структурном программировании полностью отсутствуют встроенные способы связи данных с функциями. Программисты обнаружили, что возможность многократного использования стандартных блоков, повторяющихся во многих программах, вполне естественна. Однако функции, которые прекрасно работали с одним типом данных, зачастую не могли воспользоваться другими типами, что ограничивало их преимущества.

Вследствие этого была разработана новая концепция объектно-ориентированного программирования. Суть объектно-ориентированного программирования заключается в использовании «объектов», т.е. скорее образов, чем «данных». Объекты объединяются в классы, причем любой программист может создавать собственные классы. Например, можно создать класс «Животные», или «Механизмы», или «Средства передвижения». Каждый конкретнй класс имеет собственные функции (методы) и собственные переменные. Некоторые переменные (члены класса) могут быть защищены от прямого доступа из внешней программы.

  1.  Понятие алгоритма

Любая компьютерная программа выполняет какую-то конкретную задачу, в решении которой заинтересован человек. Для решения этой задачи задаются определенные исходные данные. Правильно написанная программа позволяет получить требуемый результат.

Алгоритмом называется конечная последовательность действий, преобразующая исходные данные в  результат. 

Другими словами, алгоритм – это метод получения результата.

Само слово «алгоритм» произошло от имени арабского математика аль-Хорезми (полное имя – Abu Jafar Mohammed ibn Musa al-Khowarizmi, означающего буквально «Отец Джафара, Магомет, сын Моисея, уроженец Ховаризма»). Аль-Хорезми  родился около 825 года (в настоящее время Ховаризм – это небольшой узбекский город Хива). Этот математик написал знаменитую книгу «Kitab al jabr wal-muqabala» («Правила восстановления и преобразования»). Заглавие этой книги дало начало другому слову – «алгебра», хотя сама книга в действительности была совсем не алгебраистической.

В средневековой Европе алгоритмом называлась десятичная позиционная система счисления и искусства счета в ней, поскольку именно благодаря латинскому переводу (12 век) трактата аль-Хорезми Европа познакомилась с позиционной системой. Один из ранних немецких математических словарей “Vollstandiges Mathematisches Lexikon” (Leipzig, 1747) дает следующее определение слова Algorithmus: «Под этим именем объединены понятия о четырех типах арифметических действий, а именно о сложении, умножении, вычитании и делении».

 В настоящее время термин алгоритм используется в компьютерных науках для описания метода решения задачи, пригодного для реализации в виде компьютерной программы.

Решение задачи осуществляется с использованием вычислительных и логических операций. Поэтому компьютерная программа, которая решает определенную задачу, должна содержать математические и логические операторы. Если логические операции составляют значительную часть программы, то ее обычно относят к области искусственного интеллекта.

Алгоритмы составляют основу компьютерных наук, они являются основными объектами изучения во многих, если не в большинстве ее областей. Одну и ту же задачу можно решить разными методами, используя различные алгоритмы. Предпочтение отдается тем из них, которые обеспечивают наименьшее время исполнения компьютерной программы. Существует наука, изучающая алгоритмы. Она называется «Теория алгоритмов» и является частью математики. Достижения этой науки используются для разработки эффективных алгоритмов. Созданием и развитием теории алгоритмов занимались европейские ученые: голландец Лейтзен Эгберт Ян Брауэр (1881-1966), немец Герман Вейль (1885-1955), англичанин Алан Матисон Тьюринг (1912-1954) американские – Алонзо Черч (родился в 1903), Эмиль Леон Пост (1897-1954) и Стивен Коул Клини (р. 1909), русские ученые Андрей Андреевич Марков (р. 1903) и Андрей Николаевич Колмогоров (р. 1903).

 Пример 1.1. Рассмотрим следующий пример. Студент приходит домой, и там ему сообщают, что в его отсутствие его навещал один из друзей. У студента четверо друзей: блондинка Маша, брюнетка Юля, блондин Юра и брюнет Сережа. Кто из них приходил сегодня?

  Девушка?

Блондинка?

  Блондин?

Маша

 Юля

 Юра

  Сережа

  Начало

  Конец

Нет

Нет

Нет

Да

Да

Да

Рис. 1.1. Алгоритм ведения беседы

Чтобы это узнать, нужно задать несколько вопросов. Например, такие: «Это была девушка?», «Каков цвет ее волос?». Вопросы можно задавать в соответствии с алгоритмом, изображенным на рис. 1.1. Данная форма записи алгоритма является стандартной. Она называется блок-схемой алгоритма. Схема начинается и заканчивается рамками со скругленными углами, внутри которых написано: «Начало» и «Конец». При реализации алгоритма в виде компьютерной программы это означает начало и конец выполнения программы. Каждая представляющая практический интерес программа должна иметь начало и конец. Последовательно выполняемые операторы изображаются в виде прямоугольников, а операторы перехода по условию – в виде ромбов.

Приведенный алгоритм позволяет прояснить ситуацию после пары вопросов. До начала беседы студент пребывает в состоянии неопределенности. После ее окончания он обладает информацией, позволяющей ему точно установить личность навестившего друга (подруги). В теории алгоритмов используются также такие математические объекты как графы. Пример графа изображен на рис. 1.2.

Девушка

Юноша

Блондинка

Брюнет

Неопределенность

Маша

Юля

Юра

Сережа

Брюнетка

Блондин

Рис. 1.2. Граф, описывающий все возможные варианты хода беседы

Данный граф описывает изменения состояния информированности студента. Он напоминает дерево, перевернутое вверх ногами. Такие графы и в самом деле называют деревьями. Графы и их свойства изучают в разделе математики, именуемой: «Дискретная математика». Как можно видеть, граф представляет собой совокупность линий, соединяющих между собой некоторые точки. Точки называются вершинами, а линии – ребрами. В данном случае вершины соответствуют состоянию информированности студента на разных этапах беседы, а ребра означают действия (вопросы).

  1.  Язык программирования С++

С++ в настоящее время считается господствующим языком, используемым для разработки коммерческих программных продуктов. В последние годы это господство слегка поколебалось вследствие аналогичных претензий со стороны такого языка программирования, как Java, однако многие программисты, которые бросили С++ ради Java, в последнее время решили вернуться назад. В любом случае эти два языка настолько похожи, что, изучив один из них, можно автоматически освоить 90% другого.

Как правило, язык С++ поставляется пользователям в виде компиляторов, хотя и для его кода существует несколько интерпретаторов. Он полностью поддерживает принципы объектного программирования. Когда назрела необходимость в переменах, Бьерн Страуструп (Bjarne Stroustrup) взял язык С, используемый для разработки коммерческих программных продуктов, и расширил его, обогатив средствами, необходимыми для объектно-ориентированного программирования.

Программы на языке С++ обычно создаются в ходе компоновки одного или нескольких объектных файлов (с расширением .obj или .o) с одной или несколькими библиотеками. Библиотекой называется набор компонуемых файлов, которые поставляются вместе с компилятором. Все компиляторы С++ укомплектованы библиотекой функций (или процедур) и классов, которые можно включить в программу. Чтобы создать исполняемый файл, необходимо выполнить следующие действия:

  1.  Создать файл исходного кода с расширением .cpp;
  2.  Скомпилировать исходный код в объектный файл с расширением .obj или .o;
  3.  Скомпоновать объектный файл со всеми необходимыми библиотеками, получив исполняемый файл с расширением .exe.

Традиционно в книгах по программированию первые примеры программ начинаются с вывода на экран слов “Hello World”. Мы не будем отступать от этой традиции. Ниже приведен листинг программы, написанной на языке программирования С++.

Листинг 1.1.

1: #include <iostream>

2:

3: int main()

4: {

5: std::cout << “Hello World!\n”;

6: char response;

7: std::cin >> response;

8: return 0;

9: }

В приведенном листинге слева расположены номера строк. Эти номера установлены только для ссылок на соответствующие строки кода в тексте лекций. В окне редактора их вводить не нужно. Строка 1 подключает к файлу программы внешнюю библиотеку iostream. Это осуществляется следующим образом. Первым стоит символ # (это символ фунта, читается как «паунд»), который является инструкцией для препроцессора. При каждом запуске компилятора запускается и препроцессор. Он читает исходный текст программы, находит строки, которые начинаются с символа фунта #, и обрабатывает их перед началом компиляции программы. Команда #include (подключить) это инструкция препроцессора, которая указывает, что «далее следует имя файла, который необходимо найти и подключить именно здесь». Угловые скобки, в которые заключено имя файла, означают, что этот файл нужно искать во всех папках, отведенных для хранения подобных файлов. Файл iostream (Input-Output-Stream – поток ввода-вывода) используется объектом cout, который обслуживает процесс вывода данных на экран.

Основной код программы начинается в строке 3 с вызова функции main(). Каждая программа на языке С++ содержит эту функцию. Функция – это блок кода программы, который выполняет одно или несколько действий. Обычно функцию вызывает другая функция или оператор, но функция main() – особая: она вызывается автоматически при запуске программы.

Функция main(), подобно всем остальным функциям, должна быть объявлена с указанием типа возвращаемого значения. В данной программе функция main() возвращает целое число (значение типа int от слова integer – целый). По окончании работы эта функция возвратит операционной системе число 0, как показано в строке 8. Возвращение значения в операционную систему не столь важно, и в общем-то это значение самой системой почти не используется, но стандарт языка С++ требует, чтобы функция main() была объявлена по всем правилам (как показано в листинге). Считается, что возврат значения 0 свидетельствует о нормальном завершении программы.

Все функции начинаются открывающей фигурной скобкой ({) и оканчиваются закрывающей фигурной скобкой (}). Фигурные скобки функции main() помещены в строках 4 и 9. Все что находится между этими скобками, считается телом функции.

Объект cout используется для вывода сообщений на экран (Console Output – вывод на консоль (экран)). Для ввода сообщений с клавиатуры используется объект cin (Console Input – ввод с консоли (клавиатуры)).

Объект cout содержится в стандартной библиотеке. Компилятору необходимо указать, что будет использован объект cout именно из стандартной библиотеки. Для этого и предназначена спецификация пространства имен std в сопровождении двух двоеточий.

За словом cout стоит оператор вывода (<<). Все, что следует за этим оператором, будет выводиться на экран. Если необходимо вывести на экран строку текста, то ее необходимо заключить в двойные кавычки (“), как показано в строке 5. Два заключительных символа текстовой строки (\n) означают, что после слов “Hello World!” необходимо перейти на новую строку.

Строки 6 и 7 необходимы для того, чтобы результат оставался на экране после выполнения программы. Это заставит программу приостановиться и ожидать ввода значения. Чтобы завершить выполнение программы, нужно ввести любой символ или число, а затем нажать клавишу <Enter>. Переменная типа char (сокращение слова character – читается как «кар») используется для хранения символов.

Чтобы приступить к созданию и отладке программы, необходимо выполнить следующие действия:

  1.  Запустить компилятор;
  2.  Выбрать в меню File (Файл) пункт New (Новый);
  3.  На вкладке Projects (Проекты) выберите тип Win32 Console Application (Консольное приложение для Win32), введите имя проекта, например, hello, и щелкните по кнопке OK;
  4.   В появившемся окне мастера нового проекта выберите переключатель An Empty Project (Пустой проект) и щелкните по кнопке Finish (Готово). В результате  на экране появится диалоговое окно, отображающее информацию о новом проекте;
  5.  Чтобы вернуться к основному окну, щелкните по кнопке OK;
  6.  Выберите в меню File пункт New;
  7.  Во вкладке Files (Файлы) выберите пункт С++ Source File (Исходный файл С++) и введите его имя hello. Это имя уже было введено в текстовое поле File Name (Имя файла);
  8.  Чтобы вернуться к основному окну, щелкните по кнопке OK;
  9.  Введите текст программы;
  10.   Выберите в меню Build (Создать) пункт Build hello.exe (Создать hello.exe);
  11.   Убедитесь в отсутствии ошибок компиляции. Эта информация отображается в нижней части окна редактора кода;
  12.   Для запуска программы выберите в меню Build (Создать) пункт Execute hello.exe (Выполнить hello.exe) или нажмите комбинацию клавиш <Ctrl+F5>.

К сожалению, почти все программы содержат ошибки. Одни ошибки обнаружит компилятор, другие – компоновщик, а третьи проявятся только при запуске программы. Ошибки компиляции могут происходить по разным причинам. Обычно они являются результатом небрежного ввода исходного кода и других случайностей. Приличные компиляторы сообщат не только о том, что именно не в порядке, они укажут также точное место обнаружения ошибки. Наиболее совершенные компиляторы даже предложат вариант исправления.


 

А также другие работы, которые могут Вас заинтересовать

27931. Коэффициенты корректирования и кратности. Их назначение 49.5 KB
  4Системы вознаграждения работников АТП Ни одно АТП не может обеспечить достаточно высокий уровень профессиональной надежности работников если оно не выплачивает денежное вознаграждение по конкурентоспособным ставкам и не имеет шкалы оплаты стимулирующей высокую эффективность труда. В ходе мотивации особое внимание уделяется организации заработной платы денежного вознаграждения выплачиваемого предприятием работнику. Система вознаграждения отдельного работника в значительной степени влияет на его поведение поскольку это своего рода...
27932. Расчёт потребности АТП в смазочном масле 42.5 KB
  По содержанию перспективное планирование предприятия в новых условиях обычно включает долгосрочный прогноз на 515 лет обоснованное вероятностное предположение об изменениях в структуре и запросах рынка технике и технологии производства и их социальноэкономических последствиях план развития на 35 лет с разбивкой по годам и целевые программы решения важнейших проблем. Оперативное планирование заключается в разработке на основе годовых планов конкретных производственных заданий на короткие промежутки времени как для предприятия в...
27933. Технология очистки воды после мойки а/м для повторного использования 115.5 KB
  Размер запасов в основном определяется объемом производства транспортных услуг и временем между двумя поставками материальных ресурсов. Важность этой задачи в определенной степени обусловливается тем что сверхнормативные запасы материальных ресурсов вызывают финансовые затруднения снижают качество хранения материалов требуют дополнительных складских помещений. Образование значительных запасов сопряжено не только с появлением дополнительных складских расходов но и с риском устаревания материальных ресурсов а также с упущенной выгодой...
27934. Поточный метод. Дефектовка и ремонт пары «клапан-седло» газораспределительного механизма 42.5 KB
  2При расчетном числе рабочих постов ТО1 Д1 = 3 для одиночных а м 2 автопоездов ТО2 Д2 = 4 для одиночных 3 автопоездов 3Расчетное число линий обслуживания – целое число или меньше целого числа с отклонением не более 008 на 1 линию: 0 mцел – mрасч mцел= 008 При соблюдении всех этих условий для зон ТО экономически целесообразно является применение поточное производство с применением конвейера или других механизмов для принудительного перемещения автомобилей. Число поточных линий: m = такт ритм ритм = 60 ТсмС Nicфи фи – коэфт...