Программирование и основы алгоритмизации: Рабочая программа, задание на контрольную работу, задание на курсовое проектирование

Министерство образования Российской Федерации Государственное образовательное учреждение высшего профессионального образования СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра процессов управления и информационных систем

ПРОГРАММИРОВАНИЕ И ОСНОВЫ АЛГОРИТМИЗАЦИИ

Рабочая программа Задание на контрольную работу Задание на курсовое проектирование

Факультет информатики и систем управления Направление и специальность подготовки дипломированного специалиста: 651900 – автоматизация и управление 210100 - управление и информатика в технических системах Направление подготовки бакалавра 550200 - автоматизация и управление

Санкт-Петербург 2004

Утверждено редакционно-издательским советом университета УДК 62.52/07 Программирование и основы алгоритмизации: Рабочая программа, задание на контрольную работу, задание на курсовое проектирование. - СПб.: СЗТУ, 2004. – 25с. Рабочая программа составлена в соответствии с государственными образовательными стандартами высшего профессионального образования по направлению подготовки дипломированного специалиста 651900 – «Автоматизация и управление» (специальность 210100 - «Управление и информатика в технических системах») и направлению подготовки бакалавра 550200 – «Автоматизация и управление».

Рассмотрено на заседании кафедры процессов управления и информационных систем 17 апреля 2003 г., одобрено методической комиссией факультета информатики и систем управления 19 мая 2003 г. Рецензенты: Ю.А.Кораблев, канд.техн.наук., доц.каф. АПУ СанктПетербургского государственного электротехнического университета; Р.Р.Хамидуллин, канд.техн.наук, доц. каф. КТ и ПО СевероЗападного государственного заочного технического университета.

Составители: В.Л.Литвинов, канд. техн. наук, доц.; В.Л. Макаров, канд. техн. наук, доц.

© Северо-западный государственный заочный технический университет, 2004 2

1. ЦЕЛИ И ЗАДАЧИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ Изучение основ алгоритмизации и прикладного программирования (с использованием языка С++) и методов построения алгоритмов и структур данных, используемых при решении прикладных задач в различных предметных областях с применением ЭВМ. В результате изучения дисциплины обучаемые должны: - уметь согласованно решать задачи разработки эффективных моделей данных и алгоритмов их обработки при создании прикладного программного обеспечения, а также получать программные реализации полученных решений на универсальном алгоритмическом языке высокого уровня; - знать основные принципы и методологию разработки прикладного программного обеспечения, типовые способы организации программных данных, а также типовые подходы к построению программных алгоритмов; - знать синтаксис и семантику универсального алгоритмического языка программирования высокого уровня; - иметь навыки решения на персональных ЭВМ простейших задач программной обработки данных; - иметь навыки использования инструментальных программных средств в процессе разработки и сопровождения программных продуктов; - иметь представление о тенденциях и направлениях развития современных технологий программирования и обработки данных. Изучение дисциплины опирается на методы информатики и математической логики. 2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 2.1. Содержание дисциплины по ГОС Основные виды, этапы проектирования и жизненный цикл программных продуктов; синтаксис и семантика алгоритмического языка программирования; структурное и модульное программирование; типизация и структуризация программных данных; статические и динамические данные; потоки вводавывода; файлы; проектирование программных алгоритмов (основные принципы и подходы); классы алгоритмов; методы частных целей, подъемы ветвей и границ, эвристика; рекурсия и итерация; сортировка и поиск; методы и средства объектно-ориентированного программирования; стандарты на разработку прикладных программных средств; документирование, сопровождение и эксплуатация программных средств. 3

2.2. Рабочая программа (объем дисциплины 130 часов) 2.2.1. Основы алгоритмизации и программирования [1] , c.3 - 44; [2] , c.3 – 9; [3], c.4 - 22 Основные этапы решения задач на ЭВМ. Понятие алгоритма. Методы формального описания алгоритмов. Схемы алгоритмов. Основные характеристики алгоритмов и этапы их разработки. Базовые разновидности программных алгоритмов. Принципы алгоритмизации. Разветвленные и циклические алгоритмы. Сложные циклы. Алгоритмы с массивами. Взаимосвязь алгоритмов, моделей данных и постановок задач. Алгоритм и его программная реализация. Понятие языка программирования. Основные парадигмы программирования – процедурное, логическое, функциональное, объектно-ориентированное программирование. Основные классификационные признаки и характеристики языков программирования. Синтаксис и семантика языка. Понятие алгоритмического языка программирования и наиболее распространенные представители универсальных алгоритмических языков высокого уровня. Система программирования и инструментальные средства поддержки основных этапов проектирования прикладных программных продуктов с использованием алгоритмического языка программирования. Функциональное содержание процессов компиляции (трансляции, интерпретации) и построения загрузочных модулей, отладочных операций и тестирования. Вопросы для самопроверки 1. Перечислите основные этапы процесса решения задачи на ЭВМ. 2. Приведите примеры прямых, разветвленных и циклических алгоритмов. 3. Укажите область использования циклических алгоритмов с неизвестным числом повторений. 4. Приведите примеры циклических алгоритмов со сложными циклами. 5. Дайте определение массива. 6. Как определить адрес элемента в двумерном массиве? 7. В чем разница между компилятором и интерпретатором? 8. Как происходит компиляция исходного кода программы? 9. В чем состоит назначение компоновщика?

4

2.2.2. Структурное программирование 2.2.2.1. Общая характеристика языка С++ [1], c.7 – 39 История создания С++. Место языка С++ в общей иерархии алгоритмических языков программирования. Реализация языка для различных вычислительных платформ и операционных сред. Интегрированная среда программирования системы Borland C++. Вопросы для самопроверки 1. Почему С++ стал стандартом в области разработки программных продуктов? 2. Перечислите основные возможности интегрированной среды программирования Borland C++. 3. Дайте характеристику основным компонентам среды программирования. 4. Перечислите элементы главного меню и опишите их назначение. 2.2.2.2. Структура программы на языке С++ [1], c.26 – 28; [2], c. 10 – 11; [3], c.22 – 28 Понятия программы, модуля, программной единицы. Общая структура программы. Пользовательские и библиотечные функции. Заголовочные файлы. Препроцессор и его основные директивы. Комментарии. Вопросы для самопроверки 1. Перечислите основные составляющие, входящие в структуру программы на языке С++. 2. Наличие какой функции является обязательным условием в любой программе на языке С++? 3. В чем состоит назначение препроцессора? 4. Что такое функция и каково ее назначение? 5. Какую роль в программе выполняют библиотечные функции? 6. Какие типы комментариев вы знаете, и чем они отличаются друг от друга? 7. Могут ли комментарии занимать несколько строк? 2.2.2.3. Основные элементы языка С++ [1], c.15 – 26; [2], c.17 – 24; [3], c. 29 – 33 Алфавит языка. Идентификаторы. Ключевые слова и символы. Знаки операций. Синтаксис описания констант и переменных. Основные типы данных. 5

Вопросы для самопроверки 1. 2. 3. 4. 5. 6. 7.

Какие наборы знаков образуют алфавит языка? Какие правила необходимо выполнять при написании идентификаторов? Дайте определение константы и переменной. Перечислите основные типы данных. В чем разница между целочисленными и вещественными переменными? В чем особенности символьной переменной? Почему необходимо объявлять переменные?

2.2.2.4. Операции и выражения [1], c.28 – 37; [2], c.26 – 34; [3], c.34 – 42 Арифметические операции. Операции инкрементации и декрементации. Логические операции и операции отношения. Операция условия (?:). Операция присваивания. Операция sizeof. Приоритет операций. Назначение выражений. Примеры выражений. Вопросы для самопроверки 1. 2. 3. 4. 5. 6. 7. 8. 9.

Какой операции соответствует символ %? В чем разница между операциями инкремента и декремента? Укажите на отличие префиксной и постфиксной форм записи операций. Перечислите основные операции отношения. Что является результатом любой операции отношения? Приведите пример практической реализации операции условия. Перечислите особенности операции присваивания в языке С++. Что такое выражение? Каково значение выражения 201 % 4?

2.2.2.5. Операторы управления [1], c.38 – 49; [2], c.35 – 44; [3], c.42 – 56 Основные виды операторов – операторы циклов, условных и безусловных переходов, оператор выбора. Вспомогательные операторы. Простейшие операторы консольного ввода – вывода. Вопросы для самопроверки 1. Перечислите операторы циклов, используемых в языке С++. 2. В чем разница между операторами циклов do while и while? 3. Запишите общую структуру оператора цикла for. 6

4. Приведите пример использования оператора for для “убывающего” цикла. 5. Как осуществить принудительный выход из цикла, организованного оператором for ? 6. Запишите общую структуру оператора switch . 7. Запишите возможные структуры оператора условного перехода if. Приведите конкретные примеры таких структур. 8. В чем состоят особенности использования операторов ввода – вывода cin и cout в языке С++?. 2.2.2.6. Указатели, ссылки, массивы [1], c.51 – 58; [2], c.46 – 59; [3], c.64-79 Использование указателей как средства хранения адреса. Имена указателей. Операции над указателями. Оператор разыменования. Использование оператора адреса (&) при работе со ссылками. Возвращение значений с помощью ссылок. Понятие массива. Синтаксис описания массивов. Обращение к элементам массива. Инициализация массивов. Массивы и указатели. Двумерные и одномерные массивы. Ввод и вывод массивов. Вопросы для самопроверки 1. Какой оператор используется для получения адреса переменной? 2. Какой оператор позволяет получить значение, записанное по адресу, содержащемуся в указателе? 3. В чем разница между адресом, который хранится в указателе, и значением, записанным по этому адресу? 4. В чем различие между оператором разыменования и оператором получения адреса? 5. Покажите разницу между ссылкой и указателем. 6. Как обратиться к первому и последнему элементу массива? 7. Сколько элементов содержится в массиве В[5][5][4]? 2.2.2.7. Типы данных, определяемые пользователем [1], c.65 – 71 Переименование типов (typedef). Перечисления (enum). Структуры (struct). Объединения (union). Вопросы для самопроверки 1. В каких случаях целесообразно использовать ключевое слово typedef для переименования типов? 2. Покажите структуру описания переменной перечисляемого типа. 7

3. 4. 5. 6. 7.

Приведите примеры использования переменных перечисляемого типа. Чем отличается структура от массива? Как провести инициализацию элементов структуры? Как осуществляется доступ к элементам структуры? Чем отличаются объединения от структур? 2.2.3. Модульное программирование

2.2.3.1. Функции [1], c.72 – 88; [2], c.62 – 70; [3], c.57 – 63 Объявление и определение функций. Вызов функций. Формальные и фактические параметры. Механизм передачи параметров по значению и по адресу. Перегрузка функций. Глобальные и локальные переменные. Область видимости и время жизни объектов. Классы памяти. Понятие рекурсии. Вопросы для самопроверки 1. В чем разница между объявлением прототипа и определением функции? 2. Должны ли имена параметров, указанные в определении и вызове функции , соответствовать друг другу ? 3. Как следует объявлять функцию, если она не возвращает значения? 4. Что такое локальная переменная? 5. Что такое область видимости? 6. Что такое перегрузка функции? 7. Что такое рекурсия? 8. Когда следует использовать глобальные переменные? 9. К какому классу памяти будет относиться переменная по умолчанию? 2.2.3.2. Динамические данные [1], c.114 – 126; [3], c.84 – 86 Модели памяти. Статические и динамические данные. Механизмы выделения, перераспределения и очистки динамической памяти. Функции, поддерживающие основные операции с динамической памятью. Операторы new и delete. Динамические структуры данных. Линейные списки, стеки, очереди, бинарные деревья . Вопросы для самопроверки 1. 2. 3. 4.

Что такое динамические данные? Каким образом выделяется память под динамические данные? Перечислите основные особенности динамической памяти. Что возвращает оператор new после выделения участка динамической памяти? 8

5. Каково назначение оператора delete? 6. Перечислите основные операции с динамическими структурами данных. 7. В чем особенности однонаправленных и двунаправленных линейных списков? 8. Как осуществляется выборка элементов данных в стеке? 9. Опишите организацию движения данных в очереди. 10. Укажите преимущества динамической структуры данных в виде бинарного дерева по сравнению со списками. 2.2.3.3. Файлы и потоки [1], c.265 – 284; [3], c.87 – 95 Описание и внутреннее представление файлов. Текстовые и бинарные файлы. Базовые операции над файлами. Режимы доступа. Позиционирование в файле. Библиотечные функции работы с файлами. Понятие потока. Стандартные потоки в С++. Функции работы с потоками. Вопросы для самопроверки 1. Как различаются файлы по способу доступа? 2. Перечислите основные классы для работы с файлами из стандартной библиотеки. 3. С помощью какого оператора осуществляется открытие потока и связывание его с файлом? 4. С помощью каких операторов осуществляется вывод данных из файла? 5. С помощью каких операторов осуществляется ввод данных в файл? 6. Что такое манипуляторы потоков? 7. Какую операцию выполняет манипулятор потока setw? 8. Какой манипулятор потока осуществляет форматирование действительных чисел? 9. Каково назначение флагов формата? 2.2.4. Объектно – ориентированное программирование 2.2.4.1. Краткая характеристика объектно-ориентированного подхода в языке С++ [1], c.173 – 177 Основные концепции объектно-ориентированного подхода. Инкапсуляция, полиморфизм, наследование. История и современные тенденции развития объектно-ориентированного подхода в программировании. Специфика проектирования прикладного программного обеспечения с использованием объектных моделей. Обзор языков объектно9

ориентированного программирования (ООП). Совмещение свойств процедурного и объектно-ориентированного языка программирования в С++. Особенности реализации концепций ООП в С++. Вопросы для самопроверки 1. Перечислите основные свойства объектно–ориентированного программирования (ООП). 2. Раскройте смысл понятия – инкапсуляция класса. 3. Какую роль в ООП играет наследование? 4. Что такое полиморфизм? 2.2.4.2. Основные сведения о классах в С++ [1], c.178 – 189; [3], c.103 – 122 Понятие класса. Механизм классов в общем процессе типообразования в С++. Специфика класса. Класс и объекты класса. Свойства и методы класса. Права доступа к членам класса (public, private, protected). Класс и базовые структуры struct и union. Общие правила синтаксиса описания класса. Декларации и реализации методов класса. Обращение к свойствам и методам класса. Взаимодействие методов и свойств класса. Класс и внешние функции. Дружественные (friend) функции и классы. Inline-функции и их использование в классах. Конструкторы и деструкторы. Особые случаи реализации и использования конструкторов и деструкторов. Вопросы для самопроверки 1. Какое ключевое слово начинает определение класса? 2. Что понимается под элементами класса? 3. С помощью какой операции осуществляется доступ к элементам класса в сочетании с объектом класса? 4. С помощью какой операции осуществляется доступ к элементам класса в сочетании с указателем на объект класса? 5. Какая функция используется для присваивания значений закрытым данным - элементам класса? 6. Какова разница между открытыми ( public ) и закрытыми (private) данными – членами? 7. Могут ли функции – члены быть закрытыми? 8. Могут ли переменные – члены быть закрытыми? 9. Нужно ли объявление класса завершать точкой с запятой? 10. Какая функция вызывается для выполнения инициализации класса? 11. Какой конструктор используется по умолчанию? 12. Каково назначение деструктора? 10

13. Когда вызывается конструктор копирования? 14. Для каких целей используются дружественные функции? 2.2.4.3. Перегрузка операций [1], c.189 –197 Общие правила описания и использования перегруженных операций. Особые случаи перегрузки операций – индексирования, вызова функции, операций new и delete, присваивания и др. Присваивание, копирование в инициализации и побитовое копирование. Перегрузка префиксных и постфиксных форм операций. Семантические ограничения на перегрузку операций. Использование friend-функций при перегрузке операций. Порядок явного и неявного вызова перегружающих функций в программе. Перегруженные операции в образовании выражений. Полиморфная перегрузка операций. Перегрузка и операции преобразования типов. Перегрузка потоковых операций. Вопросы для самопроверки 1. 2. 3. 4. 5.

Какие операции в языке С++ не могут быть перегружены? Перечислите способы определения функции – операции. Приведите структуру построения функции – операции. Чем отличается перегрузка унарных и бинарных операций? Могут ли быть перегружены операции инкремента и декремента в префиксной форме?

2.2.4.4. Наследование [1], c.200 – 210 Общий порядок наследования. Базовые и производные классы. Иерархии классов. Виды наследования. Частичное и полное наследование. Виртуальное наследование. Наследование и механизмы доступа к членам классов. Виртуальные методы. Правила преобразования и совместимости указателей на базовые и производные классы. Абстрактные классы. Взаимодействие иерархий классов с дружественными функциями и классами. Множественное наследование. Стандартные библиотеки классов С++. Вопросы для самопроверки 1. Какие возможности предоставляет наследование при разработке программного обеспечения? 2. Дайте определение базового класса. 11

3. Может ли производный класс иметь доступ к закрытым элементам базового класса? 4. Как осуществляется доступ к элементам базовых классов? 5. Как определяется простое наследование? 6. Что содержит таблица виртуальных методов? 7. В чем состоят особенности вызова виртуального метода? 8. Дайте определение абстрактного класса. 9. Когда используется множественное наследование? 2.2.4.5. Шаблоны [1], c.211 – 221 Понятие шаблона в С++. Параметризация типов. Шаблоны функций и классов. Синтаксис описания шаблонов. Явное и неявное определение экземпляров шаблона. Шаблоны и обычные реализации функций и пользовательских типов данных. Семантические ограничения на реализации шаблонов. Использование шаблонов для параметризации классов. Шаблоны и наследование. Шаблоны в реализации методов класса. Обращения к шаблонам. Шаблоны и перегруженные операции. Специфика работы конструкторов и деструкторов в шаблонах. Альтернативы шаблонов в С – макросы declare и implement. Стандартные библиотеки шаблонов. Вопросы для самопроверки 1. Укажите основное назначение шаблонов. 2. C какого ключевого слова должно начинаться описание шаблона функции? 3. Чем отличается описание шаблона класса от традиционного описания класса? 4. Какое ключевое слово должно стоять перед каждым формальным параметром типа в описании шаблона функции? 5. Перечислите основные правила описания шаблонов. 6. В чем заключаются преимущества шаблонов перед макросами? 7. Какой механизм будет использоваться компилятором при вызове функций, если они образованы из одного шаблона функции и имеют одинаковые имена?

12

2.3. Тематический план лекций для студентов очно- заочной формы обучения (16 часов) 1. Основы алгоритмизации и программирования 2. Общая характеристика языка С++ Основные элементы языка С++ 3. Операции и выражения. Операторы управления 4. Указатели, ссылки, массивы 5. Функции 6. Файлы и потоки 7. Основы ООП

2 часа 2 -«-«2 -«-«2 -«-«2 -«-«2 -«-«4часа

2.4. Перечень тем практических занятий (4 часа) 1. 2. 3. 4.

Динамические данные Работа с массивами Организация ввода – вывода Функции и указатели

1час 1 -«-«1 -«-«1 -«-«-

2.5. Перечень тем лабораторных работ (28 часов) 1. 2. 3. 4.

Программная реализация линейных алгоритмов Программная реализация разветвленных алгоритмов Программная реализация алгоритмов с массивами Программная реализация алгоритмов с использованием функций и указателей 5. Программная реализация динамических типов данных 6. Программная реализация операций файлового ввода - вывода 7. Программная реализация алгоритмов с использованием классов и структур

4 часа 4 -«-«4 -«-«4 -«-«4 -«-«4 -«-«4 -«-«-

3. БИБЛИОГАФИЧЕСКИЙ СПИСОК Основной: 1. Павловская Т.А. С/С++: Программирование на языке высокого уровня. Учебник. – СПб.: Питер, 2001. 2. Шумова Е.О. Программирование на языке высокого уровня: Учеб. пособие. – СПб.: CЗТУ, 2001. 3. Макаров В.Л. Программирование и основы алгоритмизации: Учеб. пособие. – СПб.: СЗТУ, 2003.

13

Дополнительный: 4. Березин Б.И., Березин С.Б. Начальный курс С и С++. – М: Диалог – Мифи,1997. 5. Джесс Либерти. Освой самостоятельно С++ за 21 день. - М.: Издательский Дом “Вильямс”, 2001. 6. Неформальное введение в С++ и Turbo Vision. – Галерея “Петрополь”, 1992 . 7. Петухова Н.М. Вычислительная техника и программирование. Конспект лекций.- Л.: СЗПИ , 1991. 4. ЗАДАНИЕ НА КОНТРОЛЬНУЮ РАБОТУ В соответствии с учебным планом по данной дисциплине каждый студент должен выполнить в первом семестре одну контрольную работу. Контрольная работа состоит из трех задач, которые выбираются из приведенного перечня по табл. 1. Номера задач указаны в таблице по значению последней цифры шифра студента. Задачи 1. Составить блок- схему алгоритма и программу вычисления длины окружности и площади круга. 2. Составить блок- схему алгоритма и программу вычисления функции Y = EXP(-2X) при X > 0 и Y = EXP(2X) при X < 0. 3. Составить блок- схему алгоритма и программу вычисления вещественных корней квадратного уравнения AX*X + BX + C = 0. 4. Составить блок- схему алгоритма и программу вычисления функции Y = SQRT(X*X + 3) + LOG10( ABS(X - 2.3)) при X>= 3 и Y = ((X*X + 3)^2 + LOG10( ABS(X - 2.3)) при X < 3. 5. Составить блок- схему алгоритма и программу вычисления функции Y = X^2/(A + B) при изменении X от 1 до 10 с шагом 2 . 6. Составить блок- схему алгоритма и программу вычисления следующей суммы ряда 10

S = ∑ Xn / n ! , n=0

14

используя соотношения Y = Y * X/n и S = S + Y при начальных значениях (n=0) Y=1, S=1. 7. Составить блок- схему алгоритма и программу вычисления функции Y = √ x с точностью d по формуле YI+1 = 0.5(X/Yi+Yi) и начальном значении Y0 = x. 8. Составить блок- схему алгоритма и программу вычисления функции Y = X*Z/(A+B) при изменении X от 1 до 10 с шагом 2 и Z от 1 до 4 с шагом 0.5. 9. Составить блок- схему алгоритма и программу вычисления массива Y[10] по элементам массива X[10], если Yi = ( Xi+a ) / √( Xi 2 + 1 ). 10. Составить блок- схему алгоритма и программу вычисления массива Y[3][2] по элементам массива X[3][2], если Yi,j = ( Xij + a ) / √Xi ,j2 + 1 ) . 11. Составить блок- схему алгоритма и программу вычисления количества положительных, отрицательных и нулевых элементов массива А[10]. 12. Составить блок- схему алгоритма и программу вычисления количества положительных, отрицательных и нулевых элементов массива В[2][3]. 13. Составить блок-схему алгоритма и программу вычисления выражения C=n! / (m!*(n-m)! с использованием функции вычисления факториала P=K! = 1*2*3*...*(K-1)*K. Обращение к функции производить при К = n, K = m, K = nm. 14. Составить блок-схему алгоритма и программу нахождения квадранта точки с заранее неизвестными координатами. 15. . Составить блок- схему алгоритма и программу вывода на печать положительных элементов массива А[2][3]. 16. Вычисление минимального компонента двумерного массива Y[2][3] с использованием функции. 17. Составить блок- схему алгоритма и программу вычисления степенного полинома Y=a1 x1 n + a2 xn-1 +… + an x + an+1 по схеме Горнера. 18. Составить блок-схему алгоритма и программу нахождения наибольшего значения функции Y = | a | EXP (ax – x2) при изменении аргумента x от 0 до a с шагом h . 19. Составить блок- схему алгоритма и программу нахождения наименьшего элемента массива А[10] и его порядкового номера. 20. Составить блок- схему алгоритма и программу упорядочивания элементов массива A[10] по убыванию. 21. Составить программу вычисления значений функций по формулам: 15

y = (d 4 + d 2 +1) / 2(c 4 + c 2 + 1) + √(a 4 + a 2 +1) z = (b 4 + b 2 +1) 4 + (b 4 + b 2 + 1) 2 +1, c использованием оператора функции fanc(x) = x 4 + x 2 + 1. 22. Составить блок- схему алгоритма и программу игры угадай число от 1 до 1000. 23. Составить блок- схему алгоритма и программу вычисления минимальной компоненты вектора Y[5] с использованием функции. 24. Дан вещественный массив а[5]. Занести в массив данные с помощью указателей. Определить сумму и количество положительных элементов. Вывести на экран полученный массив и адреса его элементов, а также найденные сумму и количество. Составить блок- схему алгоритма и программу для решения данной задачи. 25.Решить задачу 7, используя операторы цикла DO ... WHILE. 26. Составить блок- схему алгоритма и программу возведения произвольного числа в степень n. 27. Для двумерного массива a[3][4], используя указатели, сформировать вещественный массив b[4] по следующему правилу: b[j] равен значению минимального элемента j-го столбца массива a[3][4] при изменении j от 0 до 3.Вывести на печать исходный и расчетный массивы. Составить блок- схему алгоритма и программу для решения данной задачи. 28. Составить блок- схему алгоритма и программу вычисления произведения двух произвольных матриц с использованием функций и указателей. 29. Даны целые массивы A[5], B[5]. Для каждого массива определить максимальный элемент и его индекс. В программе должны быть функции: - ввода исходных массивов; - поиска максимального значения и его индекса; - вывода исходных массивов и результатов. 30. Составить блок- схему алгоритма и программу сортировки вектора произвольной размерности с целочисленными параметрами по возрастанию и убыванию с использованием функций.

шифр Nзадачи Nзадачи Nзадачи

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

Таблица 1 9 0 10 9

11

12

12

14

15

16

17

18

19

21

22

23

24

25

26

27

28

29

16

20 30

5. ЗАДАНИЕ НА КУРСОВОЕ ПРОЕКТИРОВАНИЕ В процессе изучения курса студенты должны выполнить курсовой проект, задание на который составлено в 10 вариантах. Свой вариант студент выбирает по последней цифре шифра. В табл. 2 приведены варианты градуировочной таблицы термопар, снятые в условиях помех. В ней приняты следующие обозначения: Y - измеряемая величина, X - выход термопары, Emax - максимально-допустимая ошибка аппроксимации. В соответствии с вариантом задания необходимо: 1. Составить алгоритм аппроксимации табличной функции степенным регрессионным полиномом M-го порядка, используя метод наименьших квадратов. 2. На базе заданных функций перемножения и обращения матриц umat() и omat() разработать программу, реализующую предложенный алгоритм на языке C++. 3. С помощью программы определить порядок и коэффициенты регрессионного полинома, аппроксимирующего градуировочную табл. 2 с заданной степенью точности. 4. Используя алгоритм схемы Горнера, разработать программу вычисления полученного степенного полинома. 6. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОГО ПРОЕКТА Задание на курсовую работу связано с аналитической градуировкой датчиков, сопряженных с управляющей вычислительной машиной (УВМ). Функциональная зависимость между измеряемой величиной Y и выходным сигналом датчика X в общем случае определяется зависимостью: X = F(Y). Для задач контроля и управления необходимо знать истинное значение измеряемой величины Y. При известном значении X, Y может быть найден как: Y =(F)-1(X)=f(X).

17

Если датчик имеет линейную характеристику X = a Y + b, то определить Y легко: X-b Y = ───────. a В случае же нелинейной зависимости функция f(X) может быть выражена (аппроксимирована) нелинейными функциями или задаваться в табличном виде. При табличном способе значения измеряемой величины задаются с постоянным шагом ΔY, называемым шагом таблицы: ΔY =Y2-Y1 = Y3-Y2 =……= Yn - Yn-1. Пусть Xu - очередное измерение, причем Xi0 < Xu< Xi+1, тогда: Xu - Xi Y =Yi +ΔY ──────────────. Xi+1 - Xi Недостатком табличной записи является необходимость занесения всей таблицы в память ЭВМ и существенная зависимость точности вычислений от шага таблицы ΔY. Одним из наиболее рациональных методов определения Y является аппроксимация функции f(X) степенными полиномами, причем в условиях помех для этих целей используются регрессионные полиномы. Полином P(X) задается в виде: P(X) = a0 +a1 X + a2 X2 +…….+ am Xm,

(1)

где a0 , a1 ,..., am - неизвестные коэффициенты. Для i-го эксперимента равенство (1) запишется в виде: P(X ) = a0 + a1 Xi + a2 Xi2 + ... + am Xim . Для N экспериментов получим систему целесообразно представить в векторной форме:

18

уравнений,

(2) которую

P(X1) P(X2) . . P(Xi) . . . P(XN)

1 1

X12 .... X22 ....

X1 X2

X1m X 2m

............................ =

1

Xi2 ....

Xi

a0 a1 .

Xim

............................ 1

XN2 ....

XN

XNm

. aj

,

(3)

. am,

где i = 1,2,3,...,N; j = 1,2,...., m + 1 или в более компактном виде: P = X A.

(4)

Для выражений типа (4) нахождение вектора неизвестных коэффициентов А основано на принципе наименьших квадратов, который сводится к выбору вектора А из условия минимума суммы квадратов ошибок, характеризующих расхождение между экспериментальными точками и аппроксимирующим полиномом, т.е. min { E2 = (Y - X A)2 }.

(5)

Для получения минимума необходимо взять частную производную от выражения (5) по вектору А и приравнять ее нулю: dE ──── = - 2 XT Y+2 XT X A = 0, dA

(6)

откуда: XT X A = XT Y .

(7)

Для определения вектора А необходимо обе части выражения (7) умножить на обратную матрицу (XT X)-1 . В результате получим:

19

A = ( XT X )-1 XTY.

(8)

Выражение (8) определяет алгоритм вычисления коэффициентов степенного регрессионного полинома, который обеспечивает минимальное значение среднеквадратичной ошибки аппроксимации функции, заданной дискретными значениями переменных X и Y в таблице. Рассмотрим работу этого алгоритма на простейшем примере. Пусть дискретные значения переменных X и Y определяются значениями: Y │ X ─────┼────── 0 │ 0,5 │ 0,5 │ 2,5 │ 1 │ 6 .

Аппроксимируем заданную табличную функцию простейшим полиномом вида P(X) = a0 + a1X и выделим основные этапы расчета: 1. В соответствии с выражением (2) формируем матрицу X , размерности 3х2 │ 1 │ 1 │ 1

X =

0,5 │ 2,5 │ 6 │.

2. Получаем транспонированную матрицу X

T

1

1

1

0,5

2,5

6,0

= .

3. Вычисляем произведения XTX и XTY T

1

1

1

0,5

2,5

6

1

1

1

0,5

2,5

6

X X =

XT Y =

*

*

1 1 1 0 0,5 1

20

0,5 2,5 6 =

3 = 9

1 ,5 7,25

9

.

42,25

4. Вычисляем обратную матрицу T

(X X)

-1

3 =

-1

9

9

42,25

0,934

=

-0,196

-0,196

0,065

.

5. Вычисляем вектор коэффициентов T

A=(X X)

-1

T

0,934

-0,196

-0,196

0,065

X Y =

1,5 *

- 0,02 =

7,25

0,17725

.

Таким образом, аппроксимирующий полином будет иметь вид: P (X) = -0,02 +

0,17725 X.

Для оценки ошибки аппроксимации воспользуемся выражением: E =

N ∑ ei2 /(N+1), i=1

(9)

где ei2 - квадратичная ошибка i-го измерения, вычисляемая как: ei

2

= ( Yi -

m+1 ∑ Xij-1 *aj-1 )2 j=1

,

i = 1,2,...,N

или в векторной форме: Е2 = (Y - X A)2 .

Если рассчитанная по (9) ошибка аппроксимации окажется больше допустимой ошибки Emax, то следует увеличить степень полинома до выполнения неравенства Emax <= E. При этом следует иметь ввиду, что повышать степень полинома можно только до тех пор, пока m+1 <= N. Вычисление степенных полиномов на ЭВМ обычно осуществляется по формуле Горнера, которая для полинома m-го порядка записывается в виде: Y = P(X) = (...((a1X + a2)X + a3)X+...+ am)X+ am+1.

(10)

Алгоритм вычисления, построенный по выражению (10), сокращает время вычисления, так как возведение переменной X в любую степень заменяется расчетом по рекуррентной формуле:

21

Y = akX + ak+1, где k = 1, 2,..., m. Коэффициенты полинома сводятся в массив, включающий (m+1) элемент. Начальное значение переменной Y, задаваемое перед циклом, должно быть равно коэффициенту a1 при X в старшей степени, а параметр цикла должен изменяться от 2 до m+1. Следует отметить, что при использовании алгоритма (10), степенной полином (1) следует переписать в виде: P(X) = a1Xm + a2Xm-1 + a3Xm-2 + ... + amX + am+1. Таблица 2 №

Y

1 2

0 100

3

400

4

500

5

600

Emax

Допустимая СКО аппроксимации

Варианты Х 1

2

3

4

5

6

7

8

9

0

0 9.0 5 34. 05 43. 00 48. 55

0 8.1 5 33. 65 42. 65 48. 00

0 6.9 5 31. 49 40. 16 49. 05

0 6.0 5 33. 05 42. 00 47. 65

0 6.1 9 32. 49 41. 75 46. 25

0 4.5 5 31. 55 41. 00 45. 95

0 3.9 9 30. 05 39. 55 44. 60

0 3.5 5 29. 25 38. 95 43. 35

0 3.05 28.2 55 37.7 5 43.0 5

0 10. 15 34. 95 43. 75 50. 10

4

2

1

4

1

0.5

0.5

4

2

3

22

ПРИЛОЖЕНИЕ Функция обращения матрицы void omat(float A[10][10],int N) float s,r; int i,j,k; for(i=0;iabs(s)) { s=r;j=i; } } if(j!=k) { for (i=k-1;i<2*N;i++) { r=A[k][i]; A[k][i]=A[j][i];A[j][i]=r; } } for(j=k+1;j
A[i][j]=A[i][j]-A[k][j]*r; } } } for(j=N;j=0;i--) { s=A[i][j]; for(k=i+1;k
24

СОДЕРЖАНИЕ 1. Цели и задачи изучения дисциплины……………………………………… 3 2. Содержание дисциплины…………………………………………………… 3 3. Библиографический список………………………………………………….13 4. Задание на контрольную работу …………………………………………….14 5. Задание на курсовое проектирование ………………………………….……16 6. Методические указания к выполнению курсового проекта …………...…..17 7. Приложение .………………………………………………………………….23

Редактор М.Ю. Комарова Сводный темплан 2004 г. Лицензия ЛР № 020308 от 14.02.97 Санитарно-эпидемиологическое заключение № 78.01.07.953.П.005641.11.03 от 21.11.2003 г.

Подписано в печать Формат 60х84 1/16 Б. Кн.-журн. П.л. 1,5. Б.л. 0,75. РТП РИО СЗТУ. Тираж Заказ Северо-Западный государственный заочный технический университет РИО СЗТУ, член Издательско-полиграфической ассоциации вузов Санкт-Петербурга 191186 Санкт-Петербург, ул. Миллионная, д.5 25