Informatika_Методичка 2 часть
.pdfМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФГБОУ ВПО «Омский государственный университет им. Ф.М. Достоевского» Институт математики и информационных технологий
Информатика
Практикум В двух частях Часть 2
Омск 2019
Информатика. Практикум. Часть 2 / Сост.: Н.С. Бахта, Е.В. Ушакова, Омск: ФГБОУ ВПО «ОмГУ им. Ф.М. Достоевского», 2019. с.
27
В методических указаниях по информатике приведены задания для лабораторных работ и варианты индивидуальных программ, рекомендации и требования к ним для студентов первого курса ИМИТ специальностей «Прикладная математика и информатика» и «Фундаментальная математика и механика». Указания могут быть использованы при проведении лабораторных работ по курсу «Информатика и вычислительная техника» для студентов естественных и экономических специальностей.
Содержание
Введение…………………………………………………………………..…………4
Индивидуальное задание №1………………………………………………………5
Индивидуальное задание №2………………………………………………………9
Индивидуальное задание №3………………...……………………………………13
Индивидуальное задание №4………...……………………………………………15
Рекомендуемая литература………………………………….......…………………27
3
Введение
В современных условиях специалист-математик сталкивается с необходимостью обращаться к помощи вычислительной техники, и все чаще компьютер помогает находить решение тех задач, которые до сих пор считались «чисто» математическими. Задачи же из области прикладной математики давно требуют написания программных комплексов.
Основная цель курса «Информатика» - научить студентов азам программирования, умению составлять алгоритмы для решения математических задач, используя для этого стандартные средства, создавать простейший человеко-машинный интерфейс. В процессе обучения студенты должны получить навыки конструирования программ из подпрограмм и модулей, оформляя их в соответствии с требованиями структурного, объектного и защитного программирования.
Методические указания содержат варианты заданий для индивидуальных программ, а также требования и рекомендации к их выполнению. Предлагаемые задачи подкрепляют теоретический материал курса «Информатика».
Также указания могут быть использованы при проведении лабораторных работ по курсу «Информатика и вычислительная техника» для студентов естественных и экономических специальностей.
4
ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ №1
Цель работы: развить навыки конструирования алгоритмов на основе методов расширения неиндуктивной функции, инварианта цикла и т.п. Закрепить опыт создания подпрограмм и их локального тестирования. Приобрести и развить навыки использования типизированных файлов для хранения обрабатываемой информации.
Содержание задания
Задание состоит из двух частей и выполняется парами. В рамках первой части задания каждому студенту нужно написать модуль, содержащий подпрограмму обработки последовательностей и программу-генератор, которая должна позволять создавать тестовые файлы для подпрограммы с разными параметрами. Написанное необходимо откомпилировать, протестировать и предъявить преподавателю.
Для второй части предоставить напарнику программу-генератор тестовых файлов, откомпилированный модуль с подпрограммой (lib-файл для среды Visual Studio) и полную спецификацию подпрограммы. Вторая часть задания заключается в тестировании подпрограммы своего напарника с помощью различных видов внешнего тестирования. Тестирующий должен написать программу, которая будет использовать предоставленный модуль, и вызывать подпрограмму вычисления, предварительно определив файл, с которым будет работать подпрограмма. По окончании тестирования показать преподавателю результаты и составленное о подпрограмме напарника мнение.
Рекомендации к программе
Требования к межпрограммному интерфейсу стандартны (см. индивидуальное задание №2 в первом семестре).
При написании тестирующих программ предлагается использовать наряду с вводом автоматическую генерацию тестовых данных для больших объемов информации. Например, длина тестируемой последовательности может вводиться с клавиатуры, а сама последовательность генерироваться автоматически. Генератор должен использовать датчик псевдослучайных чисел и закон распределения данных, необходимых для тестирования. Параметры закона могут вводиться с клавиатуры. Например, для задачи о средней длине слова можно задать вероятность разделителя, а множества разделителей и букв, их условные законы распределения выбрать произвольные. Несмотря на случайный характер, автоматически генерируемые тестовые данные должны учитывать не только спецификацию задачи, но и алгоритм ее решения, и его программную реализацию. Выполнение этих требований позволяет существенно сократить время тестирования. Однако не следует ограничиваться только случайными тестами, даже если они используют весьма сложные и разнообразные законы распределения, так как в основном производят
5
нормальные условия эксплуатации программ. Для обеспечения граничных испытаний и испытаний в исключительных ситуациях обычно используются контролируемые данные, вводимые из файлов, подготовленных вручную и/или функционально. При этом не следует забывать и о так называемых нулевых примерах, которые могут иметь место в реальных условиях эксплуатации программного обеспечения. В некоторых случаях в процессе испытаний в тестируемые программы вносятся изменения, обеспечивающие специальный характер поведения обрабатываемых данных. В заключение еще раз отметим, что ни какое тестирование не может гарантировать правильности программы, поэтому ее верификация другими методами остается актуальной.
Требования к первой части
1.Алгоритм вычисления реализован с помощью метода индуктивной функции.
2.Основная подпрограмма реализована как функция, возвращающая код завершения. Все возможные ошибки должны быть обработаны (в том числе недопустимые входные параметры, неверное содержимое файла и т.д.).
3.К подпрограмме есть полная спецификация в виде комментария под заголовком.
4.Программа-генератор тестовых файлов использует некоторые доступные для изменения при тестировании параметры, которые позволяют сгенерировать файл с заданными характеристиками. Например, если считается средняя длина символьного представления целого числа со знаком в последовательности символов, то в качестве параметров можно взять количество символов в файле, суммарную длину символьных представлений всех чисел и их количество.
Требования ко второй части
Тестирующая программа получает из командной строки имя текстового файла (text), в который будут записываться результаты; спрашивает у пользователя имя файла, из которого будет читаться последовательность; вызывает подпрограмму и выводит в заданный текстовый файл результаты ее работы (т.е. сведения о возникших ошибках, значения выходных параметров и т.д.) с необходимыми комментариями. При очередном запуске тестирующей программы, если текстовый файл задан в командной строке, то результаты нового запуска будут дописаны в него, в противном случае, будет создан новый файл, имя которого спрашивается с клавиатуры.
Применены все виды внешнего тестирования. При тестировании функциональности проверены особые случаи.
Результаты работы всех тестов представлены в текстовом файле.
Варианты задания
1. Дана последовательность символов, заданная в файле. Методом индуктивной функции определить число вхождений подпоследовательности,
6
заданной в строке символов. Все символы в строке различны.
2.Дана последовательность целых чисел, заданная в файле. Методом индуктивной функции определить число нестрогих локальных максимумов в последовательности.
3.Дана последовательность символов, заданная в файле. Методом индуктивной функции вычислить среднюю длину символьных представлений натуральных чисел, начинающихся с 9.
4.Дана последовательность вещественных чисел, заданная в файле. Методом индуктивной функции вычислить среднюю длину связных строго возрастающих подпоследовательностей.
5.Дана последовательность символов, заданная в файле. Методом индуктивной функции определить количество вхождений в последовательность цифры, которая встречается в последовательности максимальное число раз.
6.Дана последовательность символов, заданная в файле. Методом индуктивной функции определить среднюю длину связной подпоследовательности, состоящей из четного числа пробелов.
7.Дана последовательность вещественных чисел, заданная в файле. Методом индуктивной функции вычислить среднюю длину связных подпоследовательностей отрицательных чисел.
8.Дана последовательность символов, заданная в файле. Методом индуктивной функции определить среднюю длину подпоследовательностей, состоящих из четных цифр.
9.Дана последовательность символов, заданная в файле. Методом индуктивной функции вычислить значение средней длины целого числа со знаком.
10.Дана последовательность символов, заданная в файле. Методом индуктивной функции вычислить значение средней длины идентификатора.
11.Дана последовательность вещественных чисел, заданная в файле. Методом индуктивной функции при известном значении аргумента вычислить значение первой производной многочлена, коэффициенты которого записаны по убыванию степеней многочлена.
12.Дана последовательность символов, заданная в файле. Методом индуктивной функции вычислить значение средней длины связной подпоследовательности цифр.
7
13.Дана последовательность символов, заданная в файле. Методом индуктивной функции подсчитать количество различных символов.
14.Дана последовательность вещественных чисел, заданная в файле. Методом индуктивной функции при известном значении аргумента вычислить значение многочлена, коэффициенты которого записаны по убыванию степеней многочлена.
15.Дана последовательность целых чисел, заданная в файле. Методом индуктивной функции вычислить значение средней длины связной подпоследовательности чисел, кратных 5.
16.Дана последовательность целых чисел, заданная в файле. Методом индуктивной функции вычислить значение средней длины связных подпоследовательностей нечетных чисел.
8
ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ № 2
Цель работы: приобрести навыки построения табличных структур данных на основе методологии объектного программирования. Закрепить опыт конструирования алгоритмов методами расширения неиндуктивной функции, рекурсии, инварианта цикла и т.п. Развить и закрепить навыки разработки интерфейса «человек-компьютер».
Содержание задания
1.Составить подпрограмму, реализующую алгоритм обработки табличных данных, инкапсулированных в объектных типах данных.
2.Создать модуль, реализующий классы объектов одно- и двумерных таблиц элементов, используемых в подпрограмме типов.
3.Создать подпрограмму редактирования/просмотра одно- и двумерных таблиц, обеспечивающих ввод/вывод тестовых данных.
4.Составить программу, обеспечивающую тестирование разработанных подпрограмм.
Рекомендации к программе
1.Требования к межпрограммному интерфейсу стандартны. Реализация алгоритма должна быть максимально эффективна по времени и памяти. Выбор варианта реализации должен быть обоснован. Подпрограмма должна обрабатывать ошибки входной информации, адекватно реагировать на отсутствие требуемого решения, а возможно, и на его неоднозначность
2.Способ реализации классов табличных данных должен обеспечивать достаточную эффективность использования памяти (динамический класс памяти). Следует иметь в виду, что в объекте объявление полей приватными снижает скорость доступа к ним. Для повышения скорости обработки табличных данных больших размеров можно открыть доступ к полям, используемым при считывании и записи элементов таблицы. Однако это приводит к зависимости программ пользователей от реализации классов табличных объектов и допускается лишь при решении многомерных задач вычислительной математики и других критичных по времени задач обработки табличных данных.
3.Подпрограмма редактирования/просмотра может быть реализована как метод, как «дружественная функция» или как подпрограмма, расширяющая набор операций класса. Она может выполняться как в полноэкранном, так и в оконном режимах, обеспечивая обработку клавиш навигации, редактирования элементов таблицы и завершения работы. Текущее состояние должно отражаться в строке статуса состояния, а возможные действия в области помощи/диалога. Запуск обработки алгоритма не следует включать в число функций этой подпрограммы, так как алгоритмы обработки могут быть весьма разнообразны по используемым в качестве входных данным и, вообще, могут
9
оказаться никак не связанными с функциями ввода/вывода. В процессе развития редактора в него могут быть добавлены дополнительные функции (расширение набора клавиш навигации, запись/считывание с диска и т.п.).
Если в целях сокращения текста или каких-либо других целях Вы приняли решение о создании служебных подпрограмм редактора, то их следует локализовать в нём. Исключением являются такие служебные подпрограммы общего назначения, как опрос нажатой клавиши, ввод числа с контролем правильности и т.п.
4. При реализации алгоритмов сортировки, лучше всего для экономии времени использовать вспомогательный массив ключей, если возможно их использование, без обращения каждый раз к самой таблице.
Требования к программе
Основные:
1.Данные хранятся в виде объекта класса «матрица». Внутри класса данные хранятся в виде двумерного динамического массива, организованного в виде столбца указателей на строки или строки указателей на столбцы – в зависимости от алгоритма сортировки (за основу можно взять реализацию класса с семинарского занятия № 1 второго семестра). Класс должен быть описан в отдельном модуле и может использовать фатальную обработку ошибок.
2.Алгоритм сортировки оформлен в виде подпрограммы, свободной от операций ввода-вывода. Эта подпрограмма может быть реализована как метод класса, как дружественная функция или независимо. Параметры подпрограммы: указатель на объект (если не метод класса), функция, сравнивающая строки (столбцы) на упорядоченность (если невозможна сортировка по ключам). Подпрограмма адекватно реагирует на неверные входные данные и возвращает код завершения, если она не метод класса, или вызывает обработчик ошибок класса в противном случае.
3.Фактические размеры матрицы при создании указываются пользователем. Заполнение матрицы осуществляется тремя способами (по выбору пользователя): с клавиатуры (с помощью редактора матриц), случайным образом и из типизированного или двоичного (но не текстового!) файла с проверкой корректности его имени и содержимого (способ упаковки матрицы в файл такой же, как в задании № 3 в 1-м семестре).
4.Подпрограмма-редактор должна содержать минимальный набор операций (перемещение по матрице с помощью стрелок, редактирование элемента матрицы с проверкой правильности введенного числа, выход), внизу экрана должна быть строка состояния, которая содержит информацию о текущем элементе матрицы (его индексы в матрице и полное значение в научном формате), и подсказка по используемым клавишам. Вызов алгоритма сортировки в число функций редактора включать не следует! Редактор может быть написан не самостоятельно, но в его работе надо хорошо разбираться (при этом имеется в виду редактор, удовлетворяющий минимальным требованиям).
10