Методические указания к курсовому проектированию Одобрено редакционно-издательским советом института icon

Методические указания к курсовому проектированию Одобрено редакционно-издательским советом института



Смотрите также:
  1   2


ПРОГРАММНАЯ ИНЖЕНЕРИЯ


Методические указания

к курсовому проектированию


Одобрено редакционно-издательским советом института


УДК 681.3

ББК 32.973.26-018.2.75


Методические указания к курсовому проектированию по дисциплине «Программная инженерия»/ Составитель: Михайлюк


Содержатся основные сведения, необходимые для выполнения курсовой работы по дисциплине «Программная инженерия». Методические указания разработаны с использованием учебной и специальной научно-технической литературы по программированию на языках С/С++, а также с использованием методических материалов по курсовому проектированию. Практическое применение иллюстрируется различными примерами. Обсуждается методика выполнения курсовой работы. Приведены перечни заданий на выполнение курсовой работы. Дополнительно в приложениях приводятся необходимые сведения и материалы, необходимые для оформления и защиты работы.


Рецензент: канд. ф.-м.. наук, программист С++ ООО Боронд Фонтан, С.В.Сизов


СОДЕРЖАНИЕ


^ ПРИЛОЖЕНИЕ 3 47

Введение

Учебный план предполагает изучение дисциплины «Программная инженерия» и выполнение курсовой работы по данной дисциплине.

Тематика курсовой работы связана с программированием определенной задачи в среде быстрой разработки приложений Qt Designer распространяющиеся по лицензии GNU. Выбор С++ в качестве языка программирования не случаен. Благодаря своим широким возможностям для решения различного рода задач, он является прекрасным языком для обучения программированию.

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

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

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

^ 1. Цели и задачи

Целью курсового проектирования по дисциплине «Программная инженерия» является формирование у студентов опыта проектирования простейшего интерфейса средствами быстрой разработки приложений Qt designer.

К задачам курсового проектирования относятся:

  • закрепление, углубление, расширение и систематизация знаний, полученных при изучении дисциплин «Информатика», «Математика», а также приобретение практических навыков решения комплексных задач;

  • приобретение опыта аналитической и расчетной работы, развитие умений работы со специальной литературой и иными информационными источниками;

  • формирование умений формулировать логически обоснованные выводы, предложения и рекомендации по результатам выполненной работы;

  • формирование умения грамотно подготовить презентацию защищаемой работы;

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

  • развитие у студента системного мышления, а также профессиональной устной и письменной речи.

В результате выполнения курсовой работы студент должен научиться:

  • создавать программу в среде Qt designer в соответствии с основными этапами ее разработки;

  • грамотно формировать математическую модель с использованием соответствующих математических методов;

  • строить схему алгоритма работы программы в соответствии с требованиями ГОСТ 19.701-90 ЕСПД;

  • грамотно тестировать программу;

  • анализировать результаты работы программы и делать выводы.

^ 2. Содержание курсовой работы

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

В ходе курсового проектирования студент должен:

  1. Выполнить постановку задачи в соответствии с вариантом задания;

  2. Используя методы математического анализа, создать математическую модель решения поставленной задачи;

  3. Сделать схему алгоритма решения задачи с учетом требований ГОСТ;

  4. Написать программу на языке С++, реализующую представленную математическую модель в соответствии со схемой алгоритма;

  5. Протестировать все ветви работы программы и проанализировать полученные результаты;

  6. Написать руководство пользователя;

  7. Сделать выводы по работе в целом.

^ 3. Задание на выполнение курсовой работы

Тематика заданий на курсовую работу по дисциплине «Программная инженерия»:

  • Расчет функций (первая задана с помощью ряда Тейлора, корень второго уравнения необходимо найти при помощи метода Ньютона);

  • Расчет интеграла методом Симпсона;

  • Расчет интеграла методом Гаусса;

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

  • Расчет интеграла методом трапеций;

  • Решение систем линейных уравнений методом Гаусса;

  • Решение систем линейных уравнений методом Крамера;

  • Решение систем линейных уравнений методом Зейделя;

  • Решение систем уравнений методом Ньютона;

  • Решение уравнений методом половинного деления, секущих, Ньютона, хорд;

  • Сортировка методом простых вставок;

  • Сортировка методом бинарных вставок;

  • Сортировка методом слияния;

  • Сортировка методом выбора;

  • Сортировка методом пузырька;

  • Моделирование броуновского движения;

  • Изображение электронных часов;

  • Моделирование движения футбольного мяча после удара;

помощью ряда Тейлора, задана при по дисциплине "ат факультета.ель обязан письменно (в форме докладной записки двух плановых к^ 4. Правила оформления пояснительной записки

Курсовая работа оформляется в соответствии с требованиями государственных и межгосударственных стандартов, действующих на территории Российской Федерации.

Текст пояснительной записки набирается на компьютере.

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

Титульный лист оформляется в соответствии с требованиями ^ СТП УГАТУ. Пример оформления представлен в приложении 1.

Требования к оформлению текста: шрифт – Times New Roman, 14 pt., интервал полуторный, выравнивание по ширине, красная строка 1,25 см, поля страницы: верхнее, нижнее – 2 см, левое – 3 см, правое – 1,5 см. Названия разделов и заголовков – жирным шрифтом, с интервалом 6 пт.

Формулы – выделяются курсивом, выравнивание по центру, справа в круглых скобках проставляется нумерация. При необходимости можно использовать встроенный в MS Office Word редактор формул MS Equation.

Рисунки и схемы должны быть четкими, выравнивание по центру. Подрисуночная подпись также выравнивается по центру. Формат подрисуночной подписи:

^ Рисунок 1 – Результаты работы программы для функции y = f(x)

Таблицы форматируются аналогичным образом.

Список литературы должен быть оформлен в соответствии с требованиями ГОСТ 7.1 – 2003 Библиографическое описание документа. Общие требования и правила составления. В случае, если в качестве библиографических источников используются электронные издания или ресурсы Интернета, их необходимо оформить в соответствии с требованиями ГОСТ 7.82 – 2001. Библиографическая запись. Библиографическое описание электронных ресурсов. Общие требования и правила составления, примеры оформления электронных источников приведены в приложении к стандарту. Ссылки на рисунки, таблицы и используемые источники обязательно должны располагаться в тексте пояснительной записки.

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

  1. Титульный лист.

  2. Содержание.

  3. Задание на курсовую работу (см. приложение 2)

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

  5. Математическая модель решения задачи.

  6. Схема алгоритма решения задачи.

  7. Исходный текст программы.

  8. Руководство пользователя.

  9. Результаты работы (для различных вариантов).

  10. Тестовые примеры.

  11. Выводы по курсовой работе

  12. Список использованной литературы

^ 5. Методика выполнения курсовой работы

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

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

Задача формулируется на естественном языке. Постановка задачи включает определение сути задачи, ее ис­ходных данных, совокупности критериев оценки качества процесса обработки данных и состава результатов.

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

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

5.2. Математическая модель решения задачи

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

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

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

В вычислительных задачах необходимо выполнить расчеты в соответствии с вариантом задания, основываясь на описанной методике. Это делается для того, чтобы в дальнейшем на этапе тестирования сравнить результат, выдаваемый программой с данными, полученными в ходе расчетов. Зачастую в силу логических или технических ошибок результат работы программы может отличаться от расчетного, поэтому необходимо удостовериться, что программа «посчитала правильно». В дальнейшем это поможет избежать неправильных выводов. Расчеты могут проводиться как вручную, так и с использованием специализированных пакетов: MS Excel, MathCad, Matlab и др.

5.3. Схема алгоритма решения задачи

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

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

Для записи алгоритмов может использоваться естественный язык или формальный язык с ограниченным словарем (часто на основе английского языка), промежуточный между естественным языком и языком программирования.

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

Схема работы программы должна строиться в соответствии с требованиями ^ ГОСТ 19.701 – 90 (ИСО 5807 – 85) Схемы алгоритмов, программ, данных и систем.

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

Основные элементы схемы представлены в таблице ниже (табл.1).

Таблица 1 – Некоторые обозначения, используемые в схемах алгоритмов

Символ

Название

Описание





Данные

Отображает данные, носитель которых не определен. Используется для ввода-вывода данных







Процесс

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






^ Предопределенный процесс

Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме).






Подготовка

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






Решение

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


Продолжение таблицы 1

Символ

Название

Описание





Линия

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





Соединитель

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






Терминатор

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






Комментарий

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





Пропуск

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


Некоторые правила применения символов (выдержки из ГОСТ 19.701-90)

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

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

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

Некоторые правила выполнения соединений

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

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

3. Две или более входящие линии могут объединяться в одну исходящую. В этом случае место объединения должно быть смещено.

В данных методических указаниях приведены только некоторые символы, правила и рекомендации по построению блок-схем. Предполагается, что студенты будут работать с ГОСТ 19.701-90 самостоятельно.

В качестве инструментария для построения схем алгоритмов могут быть выбраны: MS Word, MS Visio, а также специализированные редакторы блок-схем (они доступны для свободного скачивания из сети Интернет).

Пример выполнения схемы алгоритма приведен на рис.1.












нет


Определение размера экрана MX и MY

да































Определение масштаба по X -MSX



















нет




да








































Рисунок 1 – Схема алгоритма программы


5.4. Исходный текст программы

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

Программа должна однозначно отображать алгоритм решения задачи.

Разработка программы включает:

  1. подготовку тестовых исходных данных;

  2. написание текста программы на алгоритмическом языке;

  3. перенос программ и данных на машинные носители компьютера;

  4. отладку и тестирование программы.

Исходные данные представлены в задании.

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

Отладка - это поиск и исправление ошибок программы и алгоритма. Ошиб­ки в программе могут быть синтаксические (формальные) и семантические (смысловые, ошибки алгоритма, логические ошибки). Синтаксические ошибки обнаруживают специальные опции системы программирования. Обнаружить и испра­вить их достаточно просто. Семантические ошибки вызваны неправильным пониманием или неверной формализацией задачи. Для выявления этих ошибок используют, например, поэтапное выполнение программы и контроль получен­ных, заранее известных, результатов, которые определяют, например, из расче­тов более простым методом. Еще одним из методов является трассировка, которая позволяет проследить ход выполнения программы пооператорно.

Из опыта разработки программных систем определено, что число ошибок программирования (в тексте программы) составляет около 7% от всего числа ошибок во время разработки. "Тяжесть" их исправления оценивается в 1%. Относительное число ошибок, внесенных за счет неточностей постановки за­дачи и неправильного построения алгоритма, составляет около 83%, а "тя­жесть" их устранения - 95%.

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

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

Обязательным после листинга программы должен быть список используемых идентификаторов с пояснением каждого из них, как показано на рис.3.


Используемые идентификаторы:

A1,B1 – конец и начало интервала интегрирования;

MX,MY – размер экрана в пикселях;

MX01, MX05,MX09,MX01,MY005,MY05,MY01,MY09 – наиболее часто встречающиеся значения экрана в пикселях;

MSX, MSY – масштабы по осям;

ST ,ST1– строки для вывода на экран;

X,Y,Y1 – переменные для формирования надписей значений по осям;

A,B,C,D,I – вспомогательные переменные;

S – значение интеграла;

F(x) – функция вычисления заданной функции.



Рисунок 3 – Список используемых идентификаторов


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

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

Результаты тестирования должны быть представлены в разделе «Тестовые примеры». Тестирование программы должно быть проведено по всем возможным веткам программы. Тесты должны проводиться на максимально возможном наборе допустимых данных. Любая программа должна содержать проверку корректности данных и иметь возможность повторного ввода или корректного выхода при невозможности ввести достоверные данные или при многократном вводе ошибочных данных.


^ 5.5. Руководство пользователя

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

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

Руководство пользователя должно быть организовано таким образом, чтобы любому человеку, не знакомому со средой быстрой разработки приложений Qt designer, программой и методом, реализуемым ею, были понятны действия, которые от него требуется выполнить.

^ Примерный план написания руководства пользователя:

1. Действия при запуске программы (какой файл должен быть запущен, какие действия должны при этом выполняться).

2. Структура программы (какие окна есть, как между ними переключаться, структура меню и назначение его элементов).

3. Каким образом осуществляется ввод данных.

4. Как запустить автоматический расчет (или запустить программу на выполнение в случае моделирования какой-либо ситуации).

5. Какая информация выводится на экран.

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

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

Примечание: Обратите внимание, что при работе возможно сделать «снимок» экрана нажатием клавиши Print Screen (или сочетания клавиш ALT+Print Screen). Для того чтобы снять скриншот с экрана при работе с приложениями MS DOS, нужно эмулировать сеанс MS DOS с помощью программы DOSBox, которая позволяет запускать любые dos-приложения в операционной системе Windows XP. Если запустить свою программу из DOSBox, тогда снять скриншот с экрана можно простым нажатием клавиши Print Screen.

Фрагмент руководства пользователя приведен на рис.4.


Для работы с программой необходимо два раза щелкнуть на значок исполнимого (EXE) файла.

На первой, графической странице будет выведен график заданной функции, оси с разметкой, название функцию

Внизу экрана сообщение Press ESC to continue.

При нажатии клавиши ESC программа перейдет на вторую страницу в текстовый режим и выведет запрос на количество шагов интегрирования.

Тестовые примеры показали, что программа способна обработать

1 000 000 шагов интегрирования.

Результатом работы программы будет вывод сообщения о значении интеграла.

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



Рисунок 4 – Фрагмент руководства пользователя.


5.6. Результаты работы программы для различных вариантов

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

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

Таким образом, имея 3 различных варианта исходных данных и результатов работы программы, можно провести анализ полученной информации. Как изменится результат работы программы при изменении входных параметров? Почему?

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

Таблица 2 – Примерная форма таблицы для представления результатов работы программы

^ Входные данные

Вариант 1

Вариант 2

Вариант 3

а – верхняя граница

1

25

0

b – нижняя граница

10

30

50

n – количество отрезков разбиения

10

20

30

^ Результаты расчета

Вариант 1

Вариант 2

Вариант 3

dискомое значение интеграла

2,465

2,786

2,985


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

5.7. Тестовые примеры для всех ветвей работы программы (как для корректной, так и для некорректной работы)

В любой программе должна быть предусмотрена защита от некорректных действий пользователя, а также обработка иных ошибок (например, ошибок инициализации генератора случайных чисел). Иначе, в случае задания пользователем некорректных параметров или при возникновении иных исключительных ситуаций, программа будет «вылетать». Обработка ошибок предполагает выдачу пользователю рекомендаций по их устранению. Например, если областью определения функции является область [0;+∞], а пользователь в качестве границы интервала вводит отрицательное число, ему должна быть выведена подсказка вида: «Число принадлежит отрезку [0;+∞]!!!».

Некоторые случаи, когда нужно прописывать обработку ошибок:

1. Нижняя граница интервала, на котором определена функция, должна быть меньше верхней.

2. Число отрезков разбиения должно быть больше 0.

В данном разделе необходимо протестировать все ветви работы программы на наличие возможных ошибок:

1. Ввод данных (попытаться определить все ошибки, которые возникнут при вводе исходных данных пользователем).

2. Решение.

3. Вывод результатов (необходимо предусмотреть обработку ошибок).

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

5.8. Выводы по курсовой работе

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

1) Какова была задача проектирования? Была ли она решена и достигнуты ли основные цели?

2) Какие новые знания и навыки вы получили в процессе курсового проектирования?

3) Полезен ли для вас опыт данной работы и где могут быть применены полученные знания?

^ 6. График выполнения курсовой работы

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

Примерный план график приведен в таблице 3 (его графическое представление показано на рис. 6).

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

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

Таблица 3 – План-график выполнения курсовой работы

п/п

Наименование этапа работ

Процент к общей трудоемкости

^ Срок предъявления консультанту

1

2

3

4

1.

Получение и уточнение задания

1%

7 нед.

2.

Постановка задачи и математическое моделирование

10%

8 нед.

3.

Создание блок-схемы алгоритма программы

25%

9-10 нед.

4.

Программирование и отладка

30%

11-12 нед.

5.

Создание руководства пользователя

8%

13 нед.

6.

Анализ результатов работы программы

15%

14 нед.

7.

Оформление пояснительной записки, подготовка к защите

10%

15 нед.

8.

Защита

1%

16-17 нед.




Итого

100%







Рисунок 6 – График выполнения курсовой работы

^ 7. Процедура защиты курсовой работы

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

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

В ходе защиты курсовой работы оцениваются:

  • правильность и работоспособность программы, полнота ее функциональных возможностей, интерфейс пользователя;

  • знание среды программирования и основ алгоритмизации, степень владения материалом;

  • аккуратность оформления пояснительной записки;

  • соответствие материалов работы требованиям ГОСТ;

  • понимание использованных математических методов;

  • изложение материалов в устном докладе и презентации.




  1. Варианты заданий на выполнение курсовой работы

Вариант А

Разработать программу вывода на экран результаты двух функций на интервале от Хнач до Хкон с шагом dx. Первая функция задана с помощью ряда Тейлора (А), ее вычисление должно выполняться с точностью ε. Значение параметра b и начальное приближение для второй функции вводится с клавиатуры. Результаты работы должны различаться цветами.

Найти корень второго уравнения (Б) с помощью метода Ньютона. Функции представлены в таблице 4.

Интерфейс должен занимать большую часть виджета, сопровождаться заголовком, содержать наименования и градации (X, Y); масштабироваться в зависимости от исходных данных. При любых допустимых значениях исходных данных изображение должно помещаться на виджете. Программа не должна опираться на конкретные значения разрешения экрана.

Предусмотреть проверку корректности данных.

Таблица 4 – Задания для варианта А

№ варианта

Функция

1

2

1

А

|x|<∞

Б

z(x) = arcsin(x) + b

2

А

|x|<∞

Б

z(x) = e-x + b

3

А

x>1

Б

z(x) = arctg(x) + b

4

А

|x|>1

Б



5

А

|x|≤1

Б

z(x) = arctg(x) + b

6

А

| x|>1

Б

z(x) = arctg(x) + b

7

А

x<-1

Б

z(x) = arctg(x) + b

8

А

|x|<∞

Б



9

А

|x|<∞

Б

z(x) = cos(x) + b

10

А

|x|<

Б




Вариант B

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

^ Исходные данные: интервал, количество разбиений отрезка, начальная точка.

Результат: значение интеграла.

Решение.

Предусмотреть проверку корректности данных.

Таблица 5 – Задания для варианта В

варианта

Функция для интегрирования

^ Интервал интегрирования

1



[1;25]

2



[1;16]

3

y = (3·tg(x) + 2) / (x2 + 4x + 1)

[0;15]

4

y = ln( x) (x – 10)-2

[1;15]

5

y = 2cos(x) / (1 + x2)

[0;22]

6

y = е –sin(x) ·cos(sin(x))

[0;20]

7

y = tg(xx–1 + cos(x)

[1;20]

8

y = cos(2sin(x))

[1;15]

9

y = ln(1 + cos(x))

[1;10]

10

y = ln(x)·(x+1)–1

[1;25]



Вариант С

Разработать программу нахождения значения определенного интеграла с помощью метода Симпсона. Функция для интегрирования и интервал интегрирования приведены в таблице 6.

^ Исходные данные: интервал, количество разбиений отрезка, начальная точка.

Результат: значение интеграла.

Решение.

Предусмотреть проверку корректности данных.


Таблица 6 – Задания для варианта С

варианта

Функция для интегрирования

^ Интервал интегрирования

1

y = х–1·cos(x) + 2x

[1;25]

2

y = x –1 ln(x+1)

[1;25]

3



[π/2;π]

4

y = log3 x (x+x2)–1

[1;25]

5

y = ln x (x+x2)–1

[1;25]

6

y = ln x (x + 10)–1

[1;25]

7

y = ln x sin(x)

[1;25]

8

y = ln x cos(x)

[1;25]

9

y = log10 x (x+1)–1

[1;25]

10

y = tg x (x+1)–1

[1;25]


Вариант D

Разработать программу нахождения значения определенного интеграла с помощью метода Гаусса. Функция для интегрирования и интервал интегрирования приведены в таблице 7.

^ Исходные данные: интервал, количество разбиений отрезка, начальная точка.

Результат: значение интеграла.

Решение.

Предусмотреть проверку корректности данных.

Таблица 7 – Задания для варианта D

№ варианта

Функция для интегрирования

Интервал интегрирования

1

2

3

1

y = е cos(x) cos(2x)

[0;12]

2

y = cos(x) / (1+x)

[0;12]

3

y = е – cos(x) cos(sin(x))

[0;2π]

4

y = cos(x 2 +x + 1)

[0;30]

5

y = x·sin(x) / (1+x2)

[0;22]

6

y = (1+x)tg(x) / (1 + x2)

[0;22]

7

y = sin(x) ·x–1+ cos(x)

[1;25]

8

y = lg x ·(x +10)–1

[1;25]

9

y = cos(x)·(x +1)–1 + 2x

[1;25]

10

y = log2 x (x+1)–1

[1;25]

Вариант E

Разработать программу нахождения значения определенного интеграла с помощью метода средних прямоугольников. Функция для интегрирования и интервал интегрирования приведены в таблице 8.

^ Исходные данные: интервал, количество разбиений отрезка, начальная точка.

Результат: значение интеграла, график заданной функции.

Решение.

Предусмотреть проверку корректности данных.

Таблица 8 – Задания для варианта Е

№ варианта

Функция для интегрирования

Интервал интегрирования

1



(1;20]

2



[0;π/2]

3

y = tg(x) (x – 10)–1

[1;20]

4

y = (x + sin(x))/(1+cos(x))

[0;π/4]

5

y = (1 + x2)sin(x) / (1 + x–2)

[0;20]

6

y = х cos(x) + 2x

[1;25]

7

y = ln (x)·(x+10)–2

[1;20]

8

y = x2sin(x) / (1+ x2)

[0;20]

9

y = (x – 1)2 – sin(2x)

[0;25]

10

y = x3cos(x) – 2x2+ x +1

[0;20]

Вариант F

Разработать программу решения систем линейных уравнений. Применяемый метод и порядок системы указаны в таблице 9.

^ Исходные данные: порядок системы, матрица коэффициентов при неизвестных, матрица свободных членов.

Результат: решение системы, графическая визуализация решения для систем порядка N = 2.

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

Предусмотреть проверку корректности данных.

Таблица 9 – Задания для варианта F

№ варианта

Используемый метод

Порядок системы

(по умолчанию)

1-3

Метод Крамера

N≤10

4-6

Метод Гаусса

N≤10

7-10

Метод Зейделя

N≤10


Вариант G

Разработать программу сортировки с помощью метода, указанного в таблице 10.

Создать меню с командами: File, Animate, About, Exit.

Команда Animate запрещена – сообщение об ошибке: не открыт файл для чтения. Команда Exit завершает приложение. Команда About открывает окно с информацией о разработчике. Для выбора файла исходных данных (команда File) использовать объект. Из выбранного файла читаются исходные данные для сортировки (сформировать самостоятельно не менее трех файлов различной длины с данными целого типа).

После чтения данных разрешается команда Animate.

При выборе команды Animate в главном окне приложения отображается результат сортировки в виде столбиковой диаграммы. Каждый элемент представляется столбиком соответствующего размера. На каждом шаге алгоритма два элемента меняются местами. Окно должно содержать заголовок. Изображение должно занимать весь виджет.

Таблица 10 – Задания для варианта G

№ варианта

Метод сортировки

1,6

Метод простых вставок

2,7

Метод бинарных вставок

3,8

Метод слияния

4,9

Метод выбора

5,10

Метод пузырька


Вариант H

С точностью ε = 10 –12 найти каждый из корней уравнения, представленного в таблице 8, используя соответствующий метод.

Таблица 11 – Задания для варианта H

№ варианта

Уравнение

Метод

1

2

3

1



метод простых итераций

2

метод половинного деления

3

метод хорд

4

метод секущих

5

метод Ньютона

6



метод простых итераций

7

метод половинного деления

8

метод хорд

9

метод секущих

10

метод Ньютона


Вариант J

Дана система уравнений и начальная точка.

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

Таблица 12 – Задания для варианта I

№ варианта

Система уравнений

Начальная точка

Точность

Метод

1



x0 = 2,

y0 = -0,5

ε = 10 –12

Метод Ньютона

2



x0 = 2,

y0 = -0,5

ε = 10 –12

Метод градиентного спуска

3



х0 = 3,

у0 = 3

ε = 10 –6

Метод Ньютона

4



х0 = 3,

у0 = 3

ε = 10 –6

Метод градиентного спуска


Вариант J1 (повышенный уровень « на отлично!!!»)


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


  1. Используйте одномерный массив для решения следующей задачи. Компания платит своим продавцам на комиссионной основе. Продавцы получают 2000 рублей в неделю плюс 9 процентов от валовой продажи за эту неделю. Например, продавец, валовая продажа которого за неделю составила 50000 рублей, получает 2000 рублей плюс 9 процентов от 50000 рублей, или всего 6500 рублей. Напишите программу (используя массив счетчиков), которая определяет, сколько продавцов получили заработную плату в каждом из следующих диапазонов (примем допущение, что зарплата каждого продавца округляется до целого значения):

2000-2999

3000-3999

4000-4999

5000-5999

6000-6999

7000-7999

8000-8999

9000-9999

10000 и более

Результат получайте в таблице.

  1. Напишите программу, моделирующую бросание двух костей. Программа должна использовать rand для бросания первой кости и затем снова rand для метания второй кости. Затем должна подсчитываться сумма двух значений. Замечание: поскольку каждая кость может показать целое значение от 1 до 6, то сумма двух чисел может варьироваться от 2 до 12 с наиболее частым значением суммы 7 и наименее частыми значениями 2 и 12. Рисунок показывает 36 возможных комбинаций двух костей. Ваша программа должна выбрасывать две кости 36000 раз. Используйте одномерный массив, чтобы подсчитывать, сколько раз выпадает каждая возможная сумма. Напечатайте результат в табулированном формате. Определите приемлемость полученных результатов: поскольку существует шесть возможных способов выпадения 7, приблизительно в одной шестой части всех случаев бросания должно выпадать 7.



  1. (Система резервирования билетов авиакомпании) Небольшая авиакомпания купила компьютеры для своей новой автоматизированной системы резервирования. Вас попросили запрограммировать новую систему. Вы должны написать программу выделения мест на каждый полет единственного самолета (вместимость: 10 мест).

Ваша программа должна отображать следующее меню альтернатив:

^ Введите, пожалуйста, 1 для "курящих"

Введите, пожалуйста, 2 для "некурящих"

Если клиент ввел 1, ваша программа должна выделять место в салоне для курящих (места 1-5). Если клиент ввел 2 , ваша программа должна выделять место в салоне для некурящих (места 6-10). Ваша программа должна также напечатать посадочный талон, указывающий номер места клиента и тип салона в самолете – для курящих или некурящих. Используйте одномерный массив для представления схемы расположения мест в самолете. Присвойте всем элементам массива нулевые начальные значения, чтобы показать, что все места свободны. Как только место выделено пассажиру, устанавливайте соответствующие элементы массива в состояние 1, чтобы показать, что место уже занято. Ваша программа, конечно, никогда не должна выделять уже занятые места. Если салон для курящих заполнен, ваша программа должна спросить у клиента, приемлем ли для него салон для некурящих. Если да, то сделайте выделение соответствующего места. Если нет, то напечатайте сообщение «Следующий полет состоится через три часа».

  1. Используйте двумерный массив для решения следующей задачи. Компания имеет четырех продавцов (их номера с 1 по 4), которые продают 5 разных продуктов (их номера с 1 по 5). Раз в день каждый продавец заносит в регистрационную карточку (отдельную для каждого типа проданных продуктов) следующие сведения:

Номер продавца.

Номер продукта.

Общую выручку в долларах за проданный в этот день продукт.

Таким образом, каждый продавец заполняет от 0 до 5 карточек продажи в день. Допустим, что в наличии имеется информация обо всех регистрационных карточках за последний месяц. Напишите программу, которая считывает всю эту информацию о продажах за последний месяц и суммирует общую продажу по продуктам и по продавцам. Все итоги должны храниться в двумерном массиве sales. После обработки всей информации за последний месяц, напечатайте результат в табулированном формате, представляя в каждом столбце отдельного продавца и в каждой строке отдельный продукт. Общий итог каждой строки должен давать сумму продаж каждого продукта за последний месяц; общий итог каждого столбца должен давать сумму продаж каждого продавца за последний месяц. Ваши табулированные выходные данные должны включать эти итоги справа от суммируемых строк и внизу суммируемых столбцов.

  1. (Траектории черепахи) Язык Лого, особенно популярный среди пользователей персональных компьютеров, сделал известной идею траекторий черепахи. Представьте себе механическую черепаху, которая ползает по комнате под управлением программы на C++. Черепаха несет пишущее перо, которое может находиться в одной из двух позиций – нижней или верхней. Если перо в нижней позиции, черепаха вычерчивает траекторию движения, если в верхней, то черепаха передвигается свободно и ничего не вычерчивает. В этой задаче вы будете моделировать действия черепахи и создавать компьютеризованный эскиз пути.

Используйте массив floor размером 20 на 20 с нулевыми начальными условиями. Считывайте команды из содержащего их массива. Все время отмечайте текущую позицию черепахи и положение пера – нижнее или верхнее. Предполагайте, что черепаха всегда стартует из позиции 0, 0 на полу с верхним положением пера. Ваша программа должна подавать команды черепахе в соответствии со следующими обозначениями:

Команда

Значение

1

Перо вверху

2

Перо внизу

3

Поворот направо

4

Поворот налево

5,10

Передвижение вперед на 10 шагов (или на иное число шагов)

6

Печать массива 20 на 20

9

Конец данных (сигнальная метка)

Предположим, что черепаха находится где-то возле центра комнаты. Следующая «программа управления черепахой» начертила бы квадрат 12 на 1.2 и оставила бы перо в верхней позиции:

2

5,12

3

5, 12

3

5, 12

3

5, 12

1

6

9

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

  1. (Путешествие коня) Одной из наиболее интересных шахматных головоломок является задача о путешествии коня, впервые предложенная математиком Эйлером. Вопрос заключается в следующем: может ли шахматная фигура, называемая конем, обойти все 64 клетки шахматной доски, побывав на каждой из них только один раз. Рассмотрим эту интересную задачу более подробно.

Конь ходит Г-образно (на две клетки в каком-либо направлении и затем на одну клетку в перпендикулярном направлении). Таким образом, из клетки в середине пустой доски конь может сделать восемь разных ходов, (пронумерованных от 0 до 7) как показано на рисунке. Нарисуйте на листе бумаги шахматную доску 8 на 8 и попытайтесь выполнить путешествие коня вручную. Пометьте цифрой 1 первую клетку, куда вы ходите конем, цифрой 2 вторую, цифрой 3 третью и т.д. Перед началом путешествия определите, на сколько ходов вперед вы будете думать, памятуя о том, что полное путешествие состоит из 64 ходов. Как далеко вы уйдете? Что препятствует вашим планам?

Теперь разработайте программу передвижения коня по шахматной доске. Доску представим двумерным массивом board 8 на 8. Каждой клетке дадим нулевое начальное значение. Опишем каждый из восьми возможных ходов в терминах их горизонтальной и вертикальной компонент. Например, ход типа 0, как показано на рисунке, содержит перемещение на две клетки горизонтально направо и на одну клетку вертикально вверх. Ход 2 состоит из перемещения на одну клетку горизонтально налево и на две клетки вертикально вверх. Горизонтальные перемещения налево и вертикальные перемещения вверх будем отмечать отрицательными числами. Восемь ходов, которые могли бы быть описаны двумя одномерными массивами, horizontal и vertical, выглядят следующим образом:



horizontal[0] = 2

horizontal[1] = 1

horizontal[2] = -1

horizontal[3] = -2

horizontal[4] = -2

horizontal[5] = -1

horizontal[6] = 1

horizontal[7] = 2

vertical[0]=-1

vertical[1]=-2

vertical[2]=-2

vertical[3]=-1

vertical[4]=1

vertical[5]=2

vertical[6]=2

vertical[7]=1

Пусть переменные currentRow и currentColumn указывают строку и столбец текущей позиции коня. Чтобы сделать ход типа moveNumber, где moveNumber - число от 0 до 7, ваша программа использует операторы

currentRow += vertical[moveNumber];

currentColumn +=horizontal[moveNumber];

Введите счетчик, который изменяется от 1 до 64. Записывайте последний номер каждой клетки, на которую передвинулся конь. Помните, что для контроля каждого возможного хода конем нужно видеть, был ли уже конь на этой клетке. И, конечно, проверяйте каждый возможный ход, чтобы быть уверенным в том, что конь не вышел за пределы доски. Теперь напишите программу передвижения коня по доске. Запустите программу. Сколько ходов сделал конь?

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

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

Мы можем разработать «эвристику доступности» путем классификации каждой клетки в соответствии с ее доступностью (в терминах хода конем, конечно) и перемещения коня на наиболее недоступную клетку. Мы пометим двумерный массив accessibility числами, указывающими, со скольких клеток доступна каждая клетка. На пустой доске каждая центральная клетка оценивается как 8, а каждая угловая клетка как 2, остальные клетки имеют числа доступности 3, 4 или 6 в соответствии с таблицей



Теперь напишите вариант программы Путешествие Коня, используя эвристику доступности. В любом случае конь должен ходить на клетку с наименьшим числом доступности. В случае равенства чисел доступности для разных клеток конь может ходить на любую из них. Таким образом, путешествие можно начать в любом из четырех углов. (Замечание: По мере перемещения коня по доске ваша программа должна уменьшать числа доступности тем больше, чем больше клеток оказываются занятыми. Таким образом, в каждый данный момент путешествия число доступности каждой имеющейся в распоряжении клетки будет делаться равным количеству клеток, из которых можно пойти на данную клетку). Выполните эту версию вашей программы. Смогли ли вы совершить полное путешествие? Теперь модифицируйте программу для выполнения 64 путешествий, каждое из которых начинается со своей клетки шахматной доски. Сколько полных путешествий удалось сделать?

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

  1. (Восемь Ферзей) Другой шахматной головоломкой является задача о Восьми Ферзях: можно ли поставить на пустой шахматной доске восемь ферзей так, чтобы ни один из них не «атаковал» другого, т.е. никакие два ферзя не стояли бы на одном и том же столбце или на одной и той же строке или на одной и той же диагонали? Используйте размышления, приведенные в задаче 14, чтобы сформулировать эвристику для решения задачи о Восьми Ферзях. Запустите вашу программу. (Совет: можно присвоить значение каждой клетке шахматной доски, указывая, сколько клеток пустой шахматной доски «исключается», если ферзя поместить на эту клетку. Каждому углу должно быть присвоено значение 22) Как только эти «числа исключения» будут присвоены всем 64 клеткам, можно предложить эвристику: ставить каждого следующего ферзя на клетку с наименьшим числом исключения. Почему эта стратегия интуитивно привлекательна?



  1. (Решето Эратосфена) Простое число – это любое целое число, которое точно делится без остатка только само на себя и на 1. Решето Эратосфена – это способ нахождения простых чисел. Он работает следующим образом: Создайте массив, все элементы которого имеют начальные значения 1 (истина). Элементы массива с простыми индексами останутся равными 1. Все другие элементы массива в конечном счете установятся равными нулю. Начиная с индекса массива 2 (индекс 1 должен быть простым), каждый раз отыскивается элемент массива с единичным значением, циклически обрабатывается оставшаяся часть массива и устанавливается в нуль каждый элемент массива, чей индекс кратен индексу элемента с единичным значением. Для индекса 2 все элементы в массиве с большим чем 2 индексом и кратные 2 установятся равными нулю (индексы 4, 6, 8 и тому подобные); для индекса 3 все элементы с индексом свыше 3 и кратные 3, установятся равными нулю (индексы 6, 9, 12 и тому подобные) и т.д. Когда процесс закончится, элементы массива с единичным значением указывают, что их индексы – простые числа. Эти индексы могут быть напечатаны. Напишите программу, которая использует массив с 1000 элементами для определения и печати простых чисел между 1 и 999. Элемент 0 массива во внимание не принимайте.

  2. Говорят, что целое число является совершенным числом, если его сомножители, включая 1 (но не само число) в сумме дают это число. Например, 6 это совершенное число, так как 6 = 1 + 2 + 3. Напишите функцию perfect, которая определяет, является ли параметр number совершенным числом. Используйте эту функцию в программе, которая определяет и печатает все совершенные числа в диапазоне от 1 до 1000. Напечатайте сомножители каждого совершенного числа, чтобы убедиться, что число действительно совершенное. Исследуйте мощность вашего компьютера проверкой чисел, много больших 1000

  3. Напишите программу, моделирующую бросание монеты. Для каждого броска монеты программа должна печатать Орел или Решка. Промоделируйте с помощью этой программы бросание 100 раз и подсчитайте, сколько раз появилась каждая сторона монеты. Напечатайте результаты. Программа должна вызывать отдельную функцию flip, которая не принимает никаких аргументов и возвращает 0 для Орла и 1 для Решки. Замечание: если программа действительно моделирует бросание монеты, каждая сторона монеты должна появляться примерно в половине случаев.

  4. Последовательность чисел Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, 21,... начинается с 0 и 1 и имеет то свойство, что каждый последующий элемент является суммой двух предыдущих элементов. Напишите нерекурсивную функцию fibonacci(n), которая вычисляет n-е число Фибоначчи. Определите наибольшее число Фибоначчи, которое может быть напечатано в вашей системе. Модифицируйте программу в первой части так, чтобы использовать double вместо int при вычислении и возвращении значения числа Фибоначчи; используйте эту модифицированную программу для повторения второй части.

  5. (Ханойские башни). Каждый подающий надежды исследователь в области вычислений рано или поздно должен столкнуться с некоторыми классическими задачами и Ханойские Башни (см. рисунок) – одна из наиболее известных среди них. Легенда гласит, что в одном из монастырей Дальнего Востока монахи пытались переместить стопку дисков с одного колышка на другой. Начальная стопка имела 64 диска, нанизанных на один колышек так, что их размеры последовательно уменьшались к вершине. Монахи пытались переместить эту стопку с этого колышка на второй при условии, что при каждом перемещении можно брать только один диск и больший диск никогда не должен находиться над меньшим диском. Третий колышек предоставляет возможность временного размещения дисков. Считают, что когда монахи решат свою задачу, наступит конец света.



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

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

Переместить n - 1 дисков с колышка 1 на колышек 2, используя колышек 3 как место временного размещения.

Переместить последний диск (наибольший) с колышка 1 на колышек 3.

Переместить n - 1 дисков с колышка 2 на колышек 3, используя колышек 1 как место временного размещения.

Этот процесс завершается, когда последняя задача будет состоять из перемещения n = 1 дисков, т. е. окажется базовой задачей. Она соответствует тривиальному перемещению диска без использования места временного размещения.

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

Количество дисков, которое должно быть перемещено.

Колышек, на который эти диски нанизаны первоначально.

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

Колышек, используемый как место временного размещения.

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

1 → 3 (Это означает перемещение одного диска с колышка 1 на колышек 3)

1 → 2

3 → 2

1 → 3

2 → 1

2 →3

1 → 3

Представьте решение в виде таблицы, в которой колышки будут представлены столбцами таблицы (1, 3, 5), а соответствующие ячейки – дисками.

  1. Напишите программу, которая выполняет 1000 игр в крепе и отвечает на следующие вопросы: Сколько игр выиграно при первом бросании, при втором бросании, ... , при двадцатом бросании, после двадцатого бросания? Сколько игр проиграно при первом бросании, при втором бросании, ... , при двадцатом бросании, после двадцатого бросания? Каковы шансы на выигрыш в крепе? (Замечание: вы должны учесть, что крепе – одна из наиболее популярных игр в казино. Как вы думаете, что бы это значило?) Какова средняя продолжительность игры в крепе? Растут ли шансы выигрыша с увеличением продолжительности игры?

  2. (Путешествие коня: методы решения «в лоб») В задаче 6 подробно описано решение задачи о Путешествии Коня. Использованный подход, названный «эвристикой доступности», генерирует множество решений и работает эффективно. С возрастанием мощности компьютеров мы получаем возможность решать больше проблем за счет только мощности компьютера, не прибегая к изощренным алгоритмам. Назовем такой подход методом решения проблемы «в лоб» или жестким силовым вариантом. Используйте генерацию случайного числа для предоставления коню возможности ходить по шахматной доске случайным образом (конечно, только допустимыми для коня ходами). Ваша программа должна запускать путешествие и печатать окончательный вид шахматной доски. Насколько далеко смог пойти конь? Наиболее вероятно, что предыдущая программа совершит относительно короткое путешествие. Теперь модифицируйте вашу программу так, чтобы она сделала 1000 попыток путешествия. Используйте одномерный массив для регистрации количества путешествий каждой длины. По окончании 1000 попыток путешествия программа должна напечатать эту информацию в строгом табулированном формате. Каков наилучший результат? Наиболее вероятно, что предыдущая программа даст вам несколько «приличных», но не полных путешествий. Теперь «проигнорируйте все остановы» и просто позвольте вашей программе выполняться до получения полного путешествия. (Предупреждение: эта версия программы может выполняться часами даже на мощном компьютере). Снова заведите таблицу для регистрации количества путешествий каждой длины и напечатайте эту таблицу, как только будет выполнено первое полное путешествие. Сколько путешествие попыталась совершить программа перед выполнением полного путешествия? Сколько времени это заняло? Сравните жесткий силовой вариант Путешествия Коня с вариантом эвристики доступности. Какой из них требует более тщательного изучения проблемы? Разработка какого алгоритма более трудна? Какой из них требует более высокой мощности компьютера? Могли бы вы заранее быть уверенным в выполнении полного путешествия на основе эвристики доступности? Могли бы вы заранее быть уверенным в выполнении полного путешествия на основе жесткого силового подхода? Аргументируйте доводы за и против методов решения проблемы «в лоб» вообще.


Список литературы


1. ГОСТ 7.1 – 2009. Библиографическое описание документа. Общие требования и правила составления [текст] – взамен ГОСТ 7.1-84, ГОСТ 7.16-79, ГОСТ 7.18-79, ГОСТ 7.34-81, ГОСТ 7.40-82 – введ. 2009 – 07 – 01. – М.: Издательство стандартов, 2009. – 141с. – (Система стандартов по информации, библиотечному и издательскому делу).

2. ГОСТ 7.82 – 2001. Библиографическая запись. Библиографическое описание электронных ресурсов. Общие требования и правила составления [текст] – введ. 2002 – 07 – 01 – М.: Издательство стандартов, 2001. – 35с. – (Система стандартов по информации, библиотечному и издательскому делу).

3. ГОСТ 19.701 – 90 (ИСО 5807 – 85) Схемы алгоритмов, программ, данных и систем [текст]. – взамен ГОСТ 19.002-80, ГОСТ 19.003-80 – введ. 1992 – 01 – 01. – М.: Государственный стандарт союза ССР, 1990. – 22с.

4. Редактор блок-схем [Электронный ресурс]: содержится информация о редакторе блок-схем, доступна ссылка для скачивания. – Электрон. дан. – режим доступа: http://alglib.sources.ru/aboutbls.php

5. Образовательный математический сайт [Электронный ресурс]: содержится информация по математическим методам, банк задач, примеры, Internet-класс, статьи, обзоры. – Электрон. дан. – режим доступа: www.exponenta.ru.




страница1/2
Дата конвертации04.11.2013
Размер0,6 Mb.
ТипМетодические указания
  1   2
Разместите кнопку на своём сайте или блоге:
rud.exdat.com


База данных защищена авторским правом ©exdat 2000-2012
При копировании материала укажите ссылку
обратиться к администрации
Документы