Программирование на языках выского уровня, алгоритмические языки 2007
| [Скачать с сервера (290.8 Kb) - бесплатно] | 15.05.2009, 23:21 |
|
Файл doc, содержащий ВСЕ лекции по курсу "Программирование на ЯВУ". ФРАГМЕНТЫ ИЗ ЛЕКЦИЙСОДЕРЖАНИЕ
РАЗРАБОТКА (ПРОЕКТИРОВАНИЕ) ОДНОМОДУЛЬНЫХ ПРОГРАММНаписание хороших программ требует ума, вкуса и терпения. Б. СтрауструпКритерии качества программы и ее разработкиКритерии качества программы с точки зрения пользователя:
Пример «некачественной» программы. Данная программа полностью работо-способна, но понять, что она делает, а главное как – практически невозможно. #include "stdafx.h" int _tmain(int argc, _TCHAR* argv[]) { float a1, a2; int a3= 0; do { printf("Введите координату X "); scanf("%f", &a1); printf("\nВведите координату Y "); scanf("%f", &a2); if(a1 > 0){ if(a2==0) printf("\nТочка попала на полуось +X"); else if(a2>0) printf("\nТочка попала в I квадрант"); else printf("\nТочка попала в IV квадрант"); } else { if(a1 < 0) if(a2 >0)printf("\nТочка попала во II квадрант"); else if(a2==0) printf("\nТочка попала на полуось -X"); else printf("\nТочка попала в III квадрант"); else if(a2>0) printf("\nТочка попала на полуось +Y"); else if(a2<0) {printf("\nТочка попала на полуось -Y");} else printf("\nТочка попала в начало координат"); } printf("\n\nБудете еще работать (1 - Да, 0 - Нет) ? "); scanf("%d", &a3); } while(a3 == 1); return 0;} Пример «качественной» программы. Эта программа решает туже задачу, что и предыдущая программа, но имеет «правильное» решение и форматирование. #include "stdafx.h" // Определение положения точек на координатной плоскости int _tmain(int argc, _TCHAR* argv[]) { float x, y; // координаты точки int IsContinue= 0; // признак продолжения работы (1 - да, 0 - нет) // Определение местонахождения точек do { // Ввод координат для очередной точки printf("Введите координату X "); scanf("%f", &x); printf("\nВведите координату Y "); scanf("%f", &y); if((x > 0)&&(y == 0)) // точка попадает на полуось +X { printf("\nТочка попала на полуось +X"); } if((x > 0)&&(y > 0)) // точка попадает в I квадрант { printf("\nТочка попала в I квадрант"); } if((x == 0)&&(y > 0)) // точка попадает на полуось +Y { printf("\nТочка попала на полуось +Y"); } if((x < 0)&&(y > 0)) // точка попадает во II квадрант { printf("\nТочка попала во II квадрант"); } if((x < 0)&&(y == 0)) // точка попадает на полуось -X { printf("\nТочка попала на полуось -X"); } if((x < 0)&&(y < 0)) // точка попадает в III квадрант { printf("\nТочка попала в III квадрант"); } if((x == 0)&&(y < 0)) // точка попадает на полуось -Y { printf("\nТочка попала на полуось -Y"); } if((x > 0)&&(y < 0)) // точка попадает в IV квадрант { printf("\nТочка попала в IV квадрант"); } if((x == 0)&&(y == 0)) // точка пападает в цент координат { printf("\nТочка попала в начало координат"); } // Определение возможности продолжения работы printf("\n\nБудете еще работать (1 - Да, 0 - Нет) ? "); scanf("%d", &IsContinue); } while(IsContinue == 1); return 0; } Если вы еще не догадались, что делает программа, то скажу, что программа определяет положение точки на координатной плоскости. Понятие алгоритма. Свойства алгоритма «Внутренняя» простота или сложность программы определяется ее алгорит-мом. Алгоритм – это предписание в виде конечной последовательности дискретных шагов, которое задает процесс преобразования исходной информации в результат. Не любая последовательность действий считается алгоритмом. Алгоритм должен обладать массовостью, дискретностью, определенностью и результативно-стью. Массовость – применимость алгоритма ко всем задачам рассматриваемого класса при любых исходных данных. Дискретность – свойство алгоритма, означающее, что процесс преобразова-ния исходных данных в результат должен делиться на отдельные законченные эле-ментарные шаги. Каждый такой шаг должен использовать данные, полученные на предыдущем шаге, и выдавать промежуточные результаты, которые будут исполь-зованы последующими шагами. Определенность – свойство алгоритма, состоящее в том, что каждое входящее в него действие должно быть строго определено и не допускать различных толко-ваний. Так же строго должен быть определен и порядок выполнения отдельных действий. Результативность – алгоритм всегда должен завершаться за конечное число шагов, приводя к определенному результату. Алгоритмы существуют не только в программировании, они используются нами и в повседневной жизни. Рецепт приготовления пирога и инструкция по на-стройке телевизора являются примерами алгоритмов из повседневной жизни. Для составления «хорошего» алгоритма программы рекомендуется следую-щая последовательность шагов:
Постановка задачи На этом этапе программист определяет, что должна делать будущая про-грамма. В результате должна быть получена внешняя спецификация программы, включающая в себя выход, вход и главную функцию программы, а также схему диалога пользователя с программой. В разделе «выходные данные» должны быть отражены результаты работы программы (список «расчетных» величин), способ их представления (вывод на эк-ран или в файл) и ограничения на получаемые результаты (диапазоны получаемых значений, их тип). В разделе «входные данные» перечисляются исходные данные, необходимые для решения задачи. Описание данного раздела выполняется аналогично разделу «выходные данные». В разделе «главная функция» указывается действие, которое выполняет про-грамма для преобразования входных данных в выходные. Главная функция про-граммы должна представляться одним предложением, содержащим либо глагол, либо отглагольное существительное. Кроме того, в главной функции программы должны быть отражены ограничения на решения задачи, например, «упорядочивание массива по возрастанию методом пузырька». Последним разделом внешней спецификации программы является «схема диалога» пользователя с программой. В нем приводится пример диалога в том виде, в котором он будет выглядеть на экране. Внешнюю спецификацию можно считать хорошей, если из нее понятно, что должна делать программа, и нет неоднозначностей в ее толковании. Внешняя спецификация программы, рассчитывающей корни квадратного уравнения. Выходные данные: действительные корни квадратного уравнения (вещественные числа) и сообщения (см. диалог). Варианты сообщений: «Корни квадратного уравнения x1= ... и x2= ...», «Корень квадратного уравнения x= ...», «Нет действительных корней квадратного уравнения», «Корень линейного уравнения x= ...», «x – любое число», «Уравнение задано неверно». Значения по модулю кор-ней квадратного уравнения не могут превышать 32000. Входные данные: коэффициенты квадратного уравнения a, b, c (вещественные числа) (см. диалог). Значения по модулю коэффициентов квадратного уравнения не могут превышать 32000. Главная функция: расчет корней квадратного уравнения . Диалог: Расчет корней квадратного уравнения. Введите коэффициент a = 1 Введите коэффициент b = -11 Введите коэффициент c = 30 Корни квадратного уравнения x1= 6 и x2= 5 Полученная внешняя спецификация программы имеет важную роль не только для программиста, но и для будущего пользователя (заказчика) программы: она позволяем удостовериться ему в том, что учтены все его пожелания и потребности. При наличии разногласий между пользователем и программистом вырабатывается взаимоприемлемый вариант внешней спецификации. Разработка тестовых примеров Зная, что должна делать программа, программист должен придумать (или по-заимствовать из книг, Internet, у друзей и т.д.) идею решения задачи. Генерация идеи решения задачи сродни сочинению стихов или доказательству теорем, а пото-му трудно дать какие-либо конкретные рекомендации – многое зависит от опыта и способностей программиста. Однако создаваемая идея должна учитывать возмож-ности компьютера, а точнее языка программирования. После генерации идеи, ее необходимо проверить (протестировать) на конкретных примерах (тестах), придать ей реализацию в виде конкретных шагов. При этом возможны три случая:
Важным вопросом является количество примеров (тестов), на которых необходимо осуществлять проверку идеи решения. Ответ на этот вопрос таков – количество тестов должно быть не менее количества вариантов решения задачи. Иногда в набор тестов включают дополнительные примеры, решение которых сводится к уже существующим, но это не очевидно. Составление набора тестов является нетривиальной задачей (как и генерация идеи решения), а потому трудно дать какие-либо конкретные рекомендации. В общем случае следует начинать решать задачу с наиболее очевидного случая, а затем, анализируя его, пытаться придумывать контрпримеры. Теперь перейдем к тому, как тестируется идея решения задачи. Тест должен включать в себя следующие разделы: – исходные данные: представляются набором переменных и их значений; – действия, приводящие к решению задачи, и результаты этих действий. Каждое действие записываются в виде предложения на русском языке или математического выражения. В действиях обязательно должны быть указаны переменные, над которыми эти действия выполняются. Результаты действий представляются значениями переменных; – обобщение – это набор действий без конкретных значений переменных; – условие применимости – условие, определяющее случаи, когда данное обобщение применимо для решения задачи. Замечание. В сложных задачах рекомендуется использовать принцип декомпозиции: сначала задача разбивается на небольшое количество подзадач, а затем каждая из подзадач тестируется отдельно. Так продолжается до тех пор, пока зада-ча не будет сведена к элементарным действиям. Замечание. Тестовые примеры создаются как для правильных, так и непра-вильных (ошибочных) входных данных, если они могут возникать в процессе рабо-ты программы. Разработка структуры данных На этом этапе определяется состав переменных, которые будут использовать-ся в программе. Состав переменных формируется на основе анализа обобщений тестовых примеров. Для каждой переменной указывается ее имя, тип, диапазон возможных значений и описание, отражающее назначение переменной. Вся эта ин-формация может быть представлена в виде таблицы: Имя Тип Описание … … … При разработке структуры данных необходимо следовать следующим правилам: 1. Имя переменной должно быть мнемоническим, т.е. нести смысл. Лучше все-го если имя будет соответствовать предметной области, в которой решается задача. Например: a, b, c, D, x1, x2, x – стандартные обозначения переменных при решении квадратного уравнения; Price, Total – цена и общая сумма при расчете за покупку. 2. Не используйте одну переменную для хранения разной по смыслу информации. Например, использование переменной b для хранения коэффициента квадратного уравнения и дискриминанта не допускается. 3. Старайтесь указывать тип переменной безотносительно к языку программирования, так как алгоритм должен быть универсальным и не зависеть (по возможности) от языка программирования. 4. Если вы не можете придумать описание переменной, то, скорее всего, либо вы не до конца представляете, как работает алгоритм, либо переменная не нужна вообще. При описании переменной не допускается использование выражений следующего типа: «вспомогательная переменная», «временная переменная» и т.п. Замечание. Если программист создает свои собственные типы данных, то каждый тип данных описывается в виде отдельной таблицы. Составление алгоритмаКто ясно мыслит, тот ясно излагает. Народная мудростьСоставление алгоритма начинается с представления программы в виде одного «общего» действия (фактически в виде главной функции программы). Затем это действие «разбивается» на ряд более «мелких» действий, каждое из которых подвергается дальнейшему «разбиению» и т.д. Этот процесс декомпозиции продолжа-ется до тех пор, пока программа не будет представлена в виде элементарных дейст-вий. Действие считается элементарным, если оно может быть представлено в виде простого оператора языка программирования. Описанный процесс декомпозиции достаточно жестко регламентирован. Дру-гими словами порядок декомпозиции, количество действий, на которые разбивается «укрупненное» действие, а также порядок выполнения «мелких» действий задаются алгоритмическими структурами. В Приложении 1 представлены шесть базовых алгоритмических структур: СЛЕДОВАНИЕ, АЛЬТЕРНАТИВА, ВЫБОР, ЦИКЛ С ПРЕ-ДУСЛОВИЕМ, ЦИКЛ С ПОСТУСЛОВИЕМ, ПАРАМЕТРИЧЕСКИЙ ЦИКЛ. По сути, алгоритм представляет собой набор вложенных друг в друга алгоритмических структур, а процесс декомпозиции как последовательное решение все более «мелких» за-дач. Рассматриваемые алгоритмические структуры обладают одним входом/одним выходом и дискретностью. Наличие одного входа и одного выхода упрощает понимание и отладку алгоритма. Дискретность позволяет рассматривать алгоритм как последовательность задач, которые можно решать независимо. Единственным связующим звеном между этими задачами являются входные и выходные данные, со-став которых всегда определяется на более верхнем уровне. Возможно несколько способов представления алгоритмической структуры, а следовательно и алгоритма: в словесной форме, в виде блок-схем и на языке программирования (см. Приложение 1). Каждый из способов имеет свои достоинства и недостатки. Словесный алгоритм более близок к естественному языку и потому более понятен начинающим программистам. Алгоритм в виде блок-схем более нагляден и содержит информацию о входных и выходных данных, что позволяет лег-ко тестировать алгоритм. Однако этот способ представления значительно отличается от естественного языка. Представление алгоритма на языке программирования собственно является кодом программы (см. ниже). Так как язык программирования сильно отличается от естественного языка, то из текста программы очень трудно понять идею алгоритма. Все указанные способы представления могут быть преобразованы один в другой. Для начинающих программистов следует использовать все три способа представления в следующем порядке: словесный алгоритм, блок-схемы и программа. Критерием качества алгоритма является его ясность и понятность. Будем при-держиваться следующего положения «кто ясно мыслит, тот ясно излагает». ....... Тестирование (трассировка) алгоритма Основной задачей данного этапа является проверка работоспособности алгоритма и исправление ошибок. Идея тестирования заключается в ручном выполнении алгоритма по шагам. Для проверки работоспособности алгоритма используют-ся тестовые примеры: из них берутся исходные данные и контролируются значения промежуточных и конечных данных. Тестирование алгоритма происходит дискретно, т.е. каждая алгоритмическая структура тестируется отдельно. При этом должно выполняться следующее требование: каждая ветвь алгоритма должна быть протестирована хотя бы один раз, а цикл не менее трех раз. В результате тестирования могут быть выявлены следующие ошибки:
................... ................... ТИПЫ ДАННЫХ, ОПРЕДЕЛЯЕМЫЕ ПОЛЬЗОВАТЕЛЕМ В реальных задачах информация, которую требуется обрабатывать, может иметь достаточно сложную структуру. Для ее адекватного представления используются типы данных, построенные на основе простых типов данных, а также массивов и указателей. Язык Си позволяет программисту определять свои типы данных и правила работы с ними. Структуры Структура – это тип данных, состоящий из фиксированного числа компонентов разного типа. Компоненты структуры называют полями структуры. Пример: // Хранение информации о рейтинге студентов //------------------------------------------------------------------ // Правильный подход //------------------------------------------------------------------ // Студент с точки зрения деканата (объявляем новый тип данных) struct TStudent { char FIO[56]; // ФИО char Group[10]; // название группы, например, ИВТ-160 int Year; // курс float Rating; // рейтинг }; // Создаем массив для хранения информации о рейтинге студентов struct TStudent Students[100]; //------------------------------------------------------------------ // Неверный подход //------------------------------------------------------------------ // Создаем массивы для хранения информации о рейтинге студентов char FIO[100]; char Group[100]; int Year[100]; float Rating[100]; Над структурами возможны следующие операции: – объявление; – инициализация; – присваивание (=); – выбор поля структуры (. , ->). Объявление структуры: Объявление структуры включает в себя описание нового типа данных и переменной этого типа. Замечание. В качестве поля структуры может быть задана другая структура. Пример: // Структура, задающая позицию точки в трехмерной системе // координат struct TPosition { int x; int y; int z; }; // Структура, задающая сферу в трехмерной системе координат struct TSphere { struct TPosition Center; // центр сферы int Radius; // радиус сферы int Color; // цвет сферы }; // Объявляем указатель на структуру данных struct TStudent *Student; struct TSphere *Sphere; Замечание. Размер структуры не обязательно равен сумме ее элементов (может быть больше). Инициализация структуры: // Создаем студента struct TStudent Ivanov= {"Иванов А. А.”, "ИВТ-160”, 1, 20.6}; // Создаем студентов struct TStudent Students[2]= {{"Иванов А. А.”, "ИВТ-160”, 1, 20.6}, {"Петров Б. Б.”, "ИВТ-160”, 1, 17.5}}; Присваивание структуры: Присваивание возможно для переменных одного и того же структурного типа, при этом происходит поэлементное копирование данных. Пример: // В результате первый и второй элемент массива становятся равными Students[1]= Ivanov; Доступ к полям структуры: Доступ к полям структуры осуществляется с помощью оператора выбора. При этом имеется два варианта написания данного оператора: ., ->. Второй вариант используется при работе с указателем на структуру. Пример: struct TStudent Ivanov; struct TStudent *Student; // Записываем информацию о студенте strcpy(Ivanov.FIO, "Иванов А. А.”); strcpy(Ivanov.Group, "ИВТ-160”); Ivanov.Year= 1; Ivanov.Rating= 16.5; Student= &Ivanov; Student->Rating= 20.6; // аналогично (*Student).Rating= 20.6; Пример: struct TSphere Sphere; // Записываем информацию о сфере // Задаем центр координат Sphere.Centre.x= 10; Sphere.Centre.y= 20; Sphere.Centre.z= 0; // Задаем остальные свойства сферы Sphere.Radius= 300; Sphere.Color= 145; Структуру можно передавать в функцию и возвращать в качестве значения функции. Замечание. Если в структуру данных входит массив и структура передается в функцию по значению, то и массив передается по значению, т.е. создается копия массива. и т.д.
Добавил: COBA (15.05.2009) | Категория: Програм-е на ЯВУ Просмотров: 5510 | Загрузок: 1380 | Рейтинг: 5.0/2 | Теги: | |
| Комментарии (1) | |
|
| |
super