методичка по программированию

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

установление и выбор аппаратуры, ЯП и инструментария;

интеграция с уже имеющимися частями программы;

повторное применение имеющихся частей программ;

дальнейшее развитие и приспособление имеющихся систем;

оценка срока и стоимости.

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

К понятию "алгоритм"

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

Определение (алгоритм). Алгоритм - это способ с точным (т. е. выраженным в точно определенном языке) конечным описанием применения эффективных (т. е. практически выполнимых) элементарных шагов (переработки).

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

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

Алгоритмы, как правило, для этих исходных данных доставляют результаты. Эти результаты в случае задан информационной обработки могут быть информацией (или, точнее, представлением информации) или же последовательностью указаний ("управляющих сигналов"), по которым осуществляются определенные преобразования.

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

Независимо от их формы описания, для алгоритмов важно различать следующие аспекты:

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

специфичный способ, каким решается задача, при этом для алгоритма различают:

элементарные шаги обработки, которые имеются в распоряжении;

описание выбора отдельных подлежащих выполнению шагов.

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

Языки программирования и их формальное описание

Структура программы

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

2

директив препроцессора;

указаний компилятору;

объявлений и определений. Определим каждый из элементов.

Директивы препроцессора – определяют действия препроцессора по преобразованию текста программы перед компиляцией.

Указания компилятору – это специальные инструкции, которым следует компилятор во время компиляции.

Объявление переменной – задает ее имя и тип.

Объявление функции – ее имя, тип возвращаемого значения, атрибуты формальных параметров.

Определение переменной – приводит к выделению для нее памяти и задает ее начальное значение (явно или неявно).

Объявление типа – позволяет программисту создавать собственный тип – точнее присвоить имя базовому или составному типу языка программирования. Часто это позволяет повысить читаемость программы.

Определение функции – специфицирует тело функции, представляющее собой составной оператор или блок – содержащий определения переменных и операторы языка.

Описание языка

Дадим сводку определений элементов языка присущих большинству языков программирования.

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

Идентификаторы – имена, которыми обозначаются переменные, константы, типы, функции и метки.

Ключевые слова – идентификаторы, имеющие специальное значение для компилятора или компоновщика языка программирования.

Тип переменной – определяет, как будет интерпретироваться значение этой переменной. Константы – это лексемы представляющие собой фиксированные числовые или символьные значения.

Строки – последовательности символов заключенных в кавычки.

Структура – набор переменных различных типов, образующих единый объект. Операции – элементы языка, используемые для вычислений над значениями переменных, называемых операндами, и результатами, возвращаемыми функциями.

Арифметические операции – операции результатом, которых являются числовые значения.

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

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

Класс памяти – определяет для переменной время существования и область видимости.

Задается либо по расположению переменной, либо при помощи специального спецификатора, располагаемого перед обычным описанием.

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

3

Язык С++

C++ - это универсальный язык программирования, задуманный так, чтобы сделать программирование более приятным для серьезного программиста. За исключением второстепенных деталей C++ является надмножеством языка программирования C. В основе концепции C++ лежит понятие функции. Все операции выполняются при помощи функций, которые являются либо подмножеством библиотек C++, либо созданы пользователем. Операторы языка это по сути своей те же функции. Любой оператор и любая функция в C++ могут быть перегружены, т. е. переписаны заново.

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

Информация о типах содержится в некоторых объектах типов, определенных пользователем. Такие объекты просты и надежны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. При правильном использовании этот метод дает более короткие, проще понимаемые и легче контролируемые программы.

Выполнение программы написанной на языке C++ можно представить себе как работу некоторой виртуальной машины системой команд, которой является подмножество операторов и функций языка C++. Архитектурной концепцией памяти такой машины является модель памяти языка-носителя. Для C++ это адресная модель памяти с произвольным доступом с использованием адресных указателей. Типичная структура программы ля языка C++ выглядит следующим образом:

Файлы включений и директивы препроцессора

include <файл1.h>

…

include <файлN.h>

#define (определение констант, и пр. структур) формальные объявления необходимых функций объявления глобальных переменных

Основная программа

тип main(список формальных параметров)

{

объявления локальных переменных тело программы, состоящее из операторов ввода-вывода, кодовых слов и вызовов необходимых функций

}

Определение функций имена, которых объявлены в головной части программы

тип функции имя функции (список формальных параметров)

{

тело функции

}.

Язык C – это существенно функциональный язык. Т.е. основной программной единицей (квантом вычислений) в C является функция. Поэтому программа на языке C – это фактически набор вызовов необходимых функций. C – это слаботипизованный язык. С точки зрения декомпозиции задачи это означает следующее:

4

−любая задача должна быть представлена набором достаточно мелких (в том числе и математически) функциональных шагов;

−эти шаги необходимо оформить в виде функций языка и поместить в библиотечные модули (h - файлы), которые формируются по принципу межфункциональной связности;

−использование статических структур данных в программе должно быть ограничено;

−обмен данными между программными единицами должен осуществляться динамически (посредством указателей);

−следует помнить, что любая функция пользователя в C имеет практически те же свойства что и встроенные функции.

Язык Pascal

Язык программирования Pascal был изобретен Николаусом Виртом в 70-x годах для начального обучения программированию. Концепция языка вызвала широкий интерес в сообществе пользователей. Поэтому язык получил значительное распространение как альтернатива языку программирования BASIK.

Популярности языка способствовали инструментальные среды, производимые фирмой Borland International, такие как Turbo Pascal и Delphi. В основе концепции языка лежит понятие процедура и составной оператор. Все программные модули в Pascalе имеют смысл составных операторов. Функции также используются, но как вспомогательные программные единицы. Характерной особенностью языка Pascal является жесткая типизация. Т.е. на первом этапе компиляции программы производится проверка соответствия типов переменных входящих в выражения. Принудительное преобразование типов в выражения в языке отсутствует. Однако, как и язык C Pascal допускает конструирование типов данных пользователя. Другими словами язык Pascal предлагает альтернативный взгляд на технологию объектно-ориентированного программирования. Это взгляд со стороны использования автономных программных модулей – процедур.

Типичная программа на языке Pascal имеет следующий вид:

Указание на вид программной единицы (Program, Unit и т.д.) Файлы включений (библиотеки)

Объявления процедур и функций

Procedure Имя_процедуры(список формальных параметров) объявления формальных переменных;

begin

тело процедуры end;

Function Имя_функции(список формальных параметров): тип возвращаемого значения; объявления формальных переменных;

begin

тело функции end;

Основная программа

объявления формальных переменных; begin

тело программы end;

Язык Pascal это типизованный, процедурный язык программирования. В нем обязательны объявления используемых переменных вместе с их типами. Т.е. основной программной единицей (квантом вычислений) в Pascal-е является процедура. Поэтому

5

программа на языке Pascal – это фактически набор вызовов необходимых процедур. С точки зрения декомпозиции задачи это означает следующее:

−любая задача должна быть представлена набором достаточно крупных (в том числе и математически) функциональных шагов;

−эти шаги необходимо размещать в модулях (units), которые формируются исходя из общих свойств используемых процедур в смысле отношения к классу;

−в качестве структур данных обычно используются статические структуры данных;

−обмен данными между программными единицами должен осуществляться посредством передачи имен параметров в процедуры;

−переменные и константы, используемые в программе, имеют жестко заданный тип.

Методические указания по выполнению заданий

В рамках лабораторной работы необходимо выполнить не менее пяти заданий на языках программирования C++, Pascal, Forth. Задания на программирование выбираются преподавателем. По выполнению лабораторной работы подготавливается отчет.

Задания выполняются по следующему плану:

9выполняется постановка задачи;

9строится математическая модель;

9разрабатывается алгоритм и производится его неформальное описание;

9строится опорный граф алгоритма (блок-схема);

9разрабатывается проект программы с определением замкнутых программных единиц и необходимых структур данных;

9разрабатывается и документируется программа для решения поставленной задачи;

9производится тестирование разработанной программы;

9выполняется сравнительный анализ и оценка эффективности работы программ на различных языках программирования;

Пример (выполнение задания в соответствии с вышеизложенным планом).

Задача. Создать программу перевода десятичных чисел в троичную систему счисления.

1.Постановка задачи.

a.На вход программы поступают целые положительные числа от 0 до 4294967296, т. е. не более 10 десятичных разрядов. На выходе выдается то же самое число в троичном виде. В троичной записи должны присутствовать только символы 0, 1, 2.

2.Математическая модель

a.Для построения математической модели рассмотрим пример. Переведем в троичную систему счисления десятичное число 27. Воспользуемся распространенным способом деления. Разделим 27:3=9 -> остаток 0 (нулевой разряд); 9:3=3 -> остаток 0 (первый разряд); 3:3=1<3 (второй разряд). В итоге получим число в троичной системе счисления – 100.

3.Описание алгоритма.

a.Исходное число делим на основание системы счисления (3).

b.Запоминаем частное на место исходного числа.

c.Запоминаем остаток.

6

d.Если частное больше или равно основанию, то переходим к п. a иначе переходим к пункту e.

e.Выводим последнее частное и получившиеся остатки.

f.Заканчиваем алгоритм.

4.Опорный граф (блок схема) алгоритма.

Начало

Вводим исходное число a и основание системы счисления b

a >= b

нет Вывод a нет

j:=i to 1

Вывод x[j]

Конец

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

6.Текст программы на языке C++ будет выглядеть следующим образом:

//Программа для перевода заданного числа в троичную систему счисления

#include "stdafx.h"//Подключение системной библиотеки;

#include <stdio.h>//Подключение библиотеки стандартного ввода-вывода; #include <conio.h>//Подключение библиотеки консольного ввода-вывода; #include <iostream.h>//Подключение библиотеки потокового ввода-вывода;

/*Объявления глобальных переменных и необходимых функций*/

int a,i,j,x[30]; //a - исходное число для перевода в троичную систему счисления;

//i, j - служебные переменные, используемые в циклах в

качестве счетчиков;

//x[10] - массив, в элементах которого будут храниться разряды троичного числа;

int b=3; // b - константа, основание троичной системы счисления;

7

void main(void)

{

/*Блок ввода исходной информации (число a для перевода в троичную систему)*/

cout<<"Введите исходное число для перевода в троичную систему счисления a = "; cin>>a;

/*Блок перевода исходного числа в троичную систему счисления*/

i=0;

while (a>=b)

{

i++;

x[i]=a%b;

a=a/b;

}

/*Блок вывода результата (Исходное число в троичной системе)*/

x[i+1]=a;

cout<<"Исходное число в троичной системе счисления a = "; for(j=i+1; j>=1; j--)

cout<<x[j]; cout<<endl;

}

Текст программы на языке Pascal выглядит следующим образом:

{Программа для перевода заданного числа в троичную систему счисления}

program Translate;

uses crt; {Подключение библиотеки ввода-вывода} var

i, j: integer; {i, j - служебные переменные, используемые в циклах в качестве счетчиков}

x: array[1..30] of integer; { x[10] - массив, в элементах которого будут храниться разряды троичного числа }

a; longint; { a - исходное число для перевода в троичную систему счисления } const

b: integer=3; begin

{Блок ввода исходной информации (число a для перевода в троичную систему)}

write(‘Введите исходное число для перевода в троичную систему счисления a =’); readln(a);

{Блок перевода исходного числа в троичную систему счисления}

i:=0;

while a>=b

8

begin

i:=i+1; x[i]:=a mod b; a:=a div b;

end;

{Блок вывода результата (Исходное число в троичной системе)}

x[i+1]:=a;

write(‘Исходное число в троичной системе счисления a = '); for j:=i+1 downto 1

write(x[j]); writeln;

readkey; {Пауза перед выходом из программы} end.

7.Для проверки работоспособности по запросу (после запуска программы) введем число 27. Программа должна выдать в результате 1000.

8.Ввиду простоты программы она одинаково эффективно выполняется для обоих языков программирования.

Задания к лабораторной работе

1.Ознакомится с приведенными выше примерами, и проверить их работоспособность.

2.Выполнить одно из приведенных ниже заданий (по выбору преподавателя) в порядке указанном в данном методическом указании.

3.Ответить на контрольные вопросы и защитить работу перед преподавателем.

Варианты заданий для самостоятельной работы

4.Вычислить среднее арифметическое трех заданных чисел.

5.Вычислить среднее геометрическое трех заданных чисел.

6.Задано трехзначное число. Определить среднюю цифру числа.

7.Задано трехзначное число. Определить сумму всех цифр числа.

8.Задано трехзначное число. Вычислить произведение его цифр.

9.Задано четырехзначное число. Определить сумму его крайних цифр.

10.Задано четырехзначное число. Получить новое число, выписывая цифры исходного числа в обратном порядке. Например, 1234->3421, 1033->3301.

11.Задано четырехзначное число. Определить сумму его средних цифр.

12.Заданы два целых числа X и Y. Поменять их значения местами, не используя дополнительную переменную.

13.Заданы два целых числа X и Y. Поменять их значения местами, используя для этого дополнительную переменную.

14.Заданы координаты двух точек. Найти расстояние между ними.

15.Заданы три числа. Определить площадь треугольника, считая заданные числа его сторонами.

16.Треугольник задан координатами своих вершин. Определить площадь треугольника.

17.Заданы три числа. Считая их сторонами треугольника, найти углы этого треугольника.

18.Заданы координаты трех точек. Определить периметр треугольника, вершинами которого являются заданные точки.

19.Заданы три числа. Считая их сторонами треугольника, найти радиус окружности, вписанной в него.

9

20.Прямая линия задана своими коэффициентами. Определить угол наклона этой прямой к оси OX.

21.Заданы координаты двух точек. Определить коэффициенты прямой, проходящей через эти точки.

22.Задано трехзначное число. Напечатать значение TRUE, если какая-либо его цифра встречается более одного раза, и FALSE - иначе.

23.Задано трехзначное число. Напечатать значение TRUE, если оно симметрично

(например, 323, 111, 595), и FALSE - иначе.

24.Задано трехзначное число. Напечатать значение TRUE, если все его цифры упорядочены по возрастанию, и FALSE - иначе.

25.Задано четырехзначное число. Если сумма двух первых цифр равна сумме двух последних цифр, вывести значение TRUE, - иначе вывести значение FALSE.

26.Задано четырехзначное число. Вывести значение TRUE, если оно делится на сумму своих цифр, и FALSE - иначе.

27.Заданы радиус, координаты центра окружности и координаты некоторой произвольной точки. Вывести на экран значение TRUE, если точка принадлежит заданной окружности, и FALSE - иначе.

28.Задано четырехзначное число. Напечатать значение TRUE, если сумма двух крайних цифр равна сумме двух средних, и FALSE - иначе.

29.Заданы площади квадрата и круга. Напечатать значение TRUE, если квадрат поместится в круг, и FALSE - иначе.

Контрольные вопросы

1.Изложить основные принципы методики программирования.

2.Предложить свои определения понятий эффективности и корректности.

3.Дать определение языка программирования и программы.

4.Дать определение вычислительной структуры и привести примеры вычислительных структур.

5.Дать определение алгоритма. Привести примеры алгоритмов.

6.Является ли корректным определение алгоритма, приведенное в методическом указании?

7.Для задачи предложенной преподавателем разработать и защитить вычислительные структуры и алгоритм.

8.Описать типичную структуру программы.

9.Перечислить и характеризовать типичные элементы языков программирования.

10.Привести примеры структуры программ для различных языков программирования.

11.Каковы архитектурные особенности используемых Вами языков программирования?

10