 |
Тема: Составление алгоритмов решения задач.
|
|
|
|
ЛАБОРАТОРНАЯ РАБОТА №12 (4 ч)
Цель работы: Приобретение навыков в составлении алгоритмов решения задач, их визуализации и использования при разработке проектов на языке Visual Basic.
Решение задачи на ЭВМ должно включать:
1. Постановка задачи;
2. Анализ и исследование задачи, модели;
3. Разработка и анализ алгоритма (структурная схема);
4. Условные обозначения;
5. Написание и эксплуатация программы;
6. Тестирование и отладка;
7. Анализ результатов решения задачи;
8. Сопровождение программы;
9. Список использованной литературы.
Постановка задачи:
- формулировка условия задачи; - определение конечных целей решения задачи;
- определение формы выдачи результатов;
-описание данных (их типов, диапазонов величин и т.п. сводится в таблицу).
Анализ и исследование задачи, модели:
• анализ технических и программных средств; • разработка математической модели;
• разработка структур данных.
Построение модели - это формализация описания задачи с использованием математических, статистических, логических и др. методов, при которых существующие соотношения между величинами, определяющими результат, можно выразить с использованием математических формул и логических соотношений. Математическая формулировка и выбранный метод вычисления являются основой для определения последовательности действий, приводящих к искомому результату.
Разработка и анализ алгоритма:
• выбор метода проектирования алгоритма;
• выбор формы записи алгоритма (блок-схема, псевдокод и др.);
• выбор тестов и метода тестирования;
• проектирование алгоритма.
После того как построена модель решения задачи, можно приступить к разработке алгоритма её решения.
|
|
|
Алгоритмом решения задачи называется путь решения задачи, определённая последовательность действий, которую необходимо выполнить для достижения результата. Основной целью вычислительного процесса является исполнение алгоритма с заданными исходными данными и получение результата.
Данные в алгоритме - имена величин или идентификаторы, которые при исполнении алгоритма заменяются конкретными для данной задачи числовыми значениями.
Для записи алгоритмов могут быть использованы словесная запись, псевдокод, схемы алгоритмов и формальный способ записи.
Словесный способ содержит тщательно отобранный набор фраз, который не допускает лишних слов, повторений, неоднозначностей.
Псевдокод - язык записи структурированных алгоритмов, состоит из смеси языка высокого уровня и фраз языка исполнителя. Алгоритм, написанный на псевдокоде, можно легко преобразовать в программный код. Псевдокод позволяет легко разобраться в самом длинном и сложном алгоритме, поэтому чаще всего псевдокод используется для документирования программ.
Схема алгоритма - графическое представление метода решения задачи, в котором используются символы для отображения операций и данных. Алгоритм выражен последовательностью графических символов, выполняющих определённые функции, и наличием связей между ними.
| Процесс – действия, приводящие к изменению содержания, формы представления, либо расположения данных |
| Выбор продолжения процесса в зависимости от определенных условий. Имеет один вход и два альтернативных выхода (логический блок). |
| Цикл – повторение участка программного кода в зависимости от определенных условий |
| Использование подпрограммы |
| Подготовка данных для ввода или вывода |
| Вывод документа |
| Линии потока, определяющего связанность программных модулей |
| Межстраничный указатель |
| Узел пересечения потоков |
| Начало или завершение программы |
Рис. 1 Символы в схемах алгоритмов.
|
|
|
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл. Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
1. Базовая структура "следование". Образуется последовательностью действий, следующих одно за другим: 
2. Базовая структура "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:
· если—то; если—то—иначе; выбор; выбор—иначе.
1. если—то 2. если—то—иначе
Если условие то действия если условие то действия 1 иначе действия 2
3. выбор 4. выбор—иначеВыбор переменная Выбор переменная при условие 1: действия 1 при условие 1: действия 1 при условие 2: действия 2 при условие 2: действия 2........................ при условие N: действия N при условие N: действия N
иначе действия N+1
Примеры структуры ветвление
| алгоритмический язык | Язык блок-схем |
| если x > 0 то y:= sin(x) все | 
|
| если a > b то a:= 2*a; b:= 1 иначе b:= 2*b все | 
|
| выбор при n = 1: y:= sin(x) при n = 2: y:= cos(x) при n = 3: y:= 0 все | 
|
| выбор при a > 5: i:= i+1 при a = 0: j:= j+1 иначе i:= 10; j:=0 все | 
|
3. Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:
| алгоритмический язык | Язык блок-схем |
| Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. | |
| нц пока условие тело цикла (последовательность действий) кц | 
|
| Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. | |
| нц для i от i1до i2 тело цикла (последовательность действий) кц | 
|
Примеры структуры цикл
|
|
|
| алгоритмический язык | Язык блок-схем |
| нц пока i <= 5 S:= S+A[i] i:= i+1 кц | 
|
| нц для i от 1 до 5 X[i]:= i*i*i Y[i]:= X[i]/2 кц | 
|
Программирование, тестирование и отладка:
· выбор языка программирования;
· запись алгоритма на выбранном языке программирования;
· тестовые расчёты и анализ результатов тестирования.
После того как алгоритм разработан, его необходимо реализовать посредством языка программирования, то есть теперь можно определить обозначение исходных, промежуточных и выходных данных в программе, сформировать эскиз приложения (форму с отображением различных элементов управления) и приступить к написанию программы на языке Visual Basic.
Для понимания содержательной части решения задачи на ЭВМ, ход и порядок ее выполнения подробно рассмотрен ниже на примере. При рассмотрении примера выполнения даются необходимые пояснения и методические указания.
Например. Задание 1. 1. Постановка задачи. Даны пять попарно различных целых чисел: a,b,c,d,e. Упорядочить их по возрастанию, используя для этого не более 7 сравнений.
2. Анализ и исследование задачи, модели;
2.1. Теоретическая часть. Сортировка данных – это обработка информации, в результате которой элементы ее (записи) располагаются в определенной последовательности в зависимости от значения некоторых признаков элементов этой информации. Наиболее распространенным видом сортировки данных является упорядочение массива – расположение записей сортируемого массива данных в порядке монотонного изменения некоторого ключевого признака. Рассмотрим простейшие методы сортировки, к которым относят простой выбор и простой обмен.
В методе простого выбора выделяется наименьший (или наибольший) элемент массива и отделяется от остальных. Далее опять выделяется наименьший (или наибольший) из оставшихся и т. д. Например, расположить элементы последовательности А1, А2, …, АN в порядке убывания. Для этого найдем в массиве элемент с наибольшим значением и поменяем его местами с первым элементом. Далее те же действия выполним с остальными N – 1 элементами массива, затем N -2 элементами и т.д., пока не останется один элемент – последний, наименьший. Для получения результата необходимо N – 1 раз найти максимальное значение в массиве, длина которого будет уменьшаться с каждым шагом на 1.
|
|
|
Фрагмент программы для организации сортировки простым выбором:
Private Sub Command1_Click()
Dim i as Integer, j as Integer, k as Integer
For i = 1 To n: k = i: x = a(i)
For j = i + 1 To n: If a(j) > x Then: x = a(j): k = j: End If: Next j
a(k) = a(i): a(i) = x: Next i
For i = 1 To n: Print “ ”; a(i);: Next i
End Sub
В методе простого обмена если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока элементы не будут упорядочены. Алгоритм обменной сортировки (рис. 2.2, б) осуществляет максимально возможное количество сравнений, много раз приходится просматривать последовательность и выполнять много перестановок, поэтому его применяют, когда много равных элементов.
Фрагмент программы для организации сортировки простым обменом:
Private Sub Command1_Click()
For i = 2 To n: j = n
Do If a(j - 1) < a(j) Then: x = a(j - 1): a(j - 1) = a(j): a(j) = x: End If: j = j - 1
Loop While j >= 1
Next i
For i = 1 To n: List2.AddItem Str(Round(a(i), 2)): Next i
End Sub
3. Алгоритм ………… Учитывая вышесказанное о сортировках, воспользуемся алгоритмом нахождения максимального из трех величин, блок-схема которого представлена на рисунке 2. Алгоритм реализуем в функции пользователя. Функцию будем вызывать дважды, сначала для первых трех чисел, потом для выбранного максимума и оставшихся двух чисел.
Рис. 2. Блок-схема алгоритма нахождения максимального из 3 величин.
Рис 3. Схемы алгоритмов а) простого выбора, б) простого обмена
3. Условные обозначения.
Назначение переменных сведено в таблице 1. Таблица 1
| Имя | Назначение | Тип | Характеристика |
| mas() cont str1 f1 max i,j | Массив хранения данных Индекс массива Вводимое число Промежуточный максимум Окончательный максимум Индексы циклов | Integer Integer String Integer Integer Byte | Служебный Служебная Входная Служебная Служебная Служебная |
Разработку проекта начнем со скелета программы – объектов управления.
Таблица 2
| Элементы управления | Свойство | Значение |
| Form1 | Name Caption Height Top Width ScaleHeight ScaleMode ScaleWidth | Form1 Сортировка 3-Pixel |
| CommandButton 1 CommandButton 2 ListBox | Name Caption Height Left Top Width TabIndex Name Caption Height Left Top Width Name Height Left Top | Command1 Заполнить список Command1 Сортировать List1 |
5. Написание и эксплуатация программы;
Пример запуска приложения с кодом программы (рис. 4)
Рис. 4 Запуск приложения с кодом программы
6. Тестирование и отладка;
Тестовый пример…………………………………………………..
7. Анализ результатов решения задачи;………………..
|
|
|
Для анализа результатов выполнения программы составляется и заполняется таблица с несколькими контрольными примерами.
Таблица № – Результаты выполнения программы
| Входные данные | Результат |
8. Сопровождение программы;………………………..
- доработка программы для решения конкретных задач;
- составление документации к решённой задаче, математической модели, алгоритму, программе по их использованию.
В состав программы могут быть включены комментарии, т.е. тексты, поясняющие программу, но не влияющие на ход её выполнения. Комментарии в программе должны быть привязаны к номерам функциональных блоков.
9. Список использованной литературы:
1. Глушаков СВ., Клевцов А.Л., Теребилов С.А. Программирование на Visual Basic[Текст]. - Харьков: Фолио, 2002. -518 с.
2. Гарнаев A. Visual Basic 6 [Текст]: разработка приложений. -СПб.: БХВ-Петербург, 2007.-448 с.
3. Анциферова, В.И. Информатика [Текст]: методические указания к выполнению лабораторных работ для студентов специальности 150405 – Машины и оборудование лесного комплекса /Зольников В.К., Анциферова В.И, Муковников Н.М., Меерсон В.Э.; Фед. агентство по образованию, Гос. образовательное учреждение высш. проф. образования, Воронеж. гос. лесотехн. акад. – Воронеж, 2007. – 173 с.
4. Чевычелов Ю.А. Информатика. Операционная система Windows 98. Язык визуального программирования Visual Basic[Текст]. Учебное пособие / Ю.А. Чевычелов, Н. Ю. Юдина, В. Е. Межов. – Воронеж: ВГЛТА, 2004, 139 с.
5. Анциферова, В.И. Информатика [Текст]: методические указания к выполнению самостоятельных и контрольных работ студентами З/О 1, 2 курсов специальностей: 150200 (190601) - Автомобили и автомобильное хозяйство, 150200 (190601) - Автомобили и автомобильное хозяйство, ускоренная форма обучения. Фед. агентство по образованию, ГОУ ВПО «ВГЛТА» – Воронеж, 2008. – 51 с.
Пример выполнения задания (Анализ исходных данных) Задача. Площадь S и объем V обрезной доски, запиливаемой из необрезной доски, подгорбыленной доски рассчитываются по формулам 
, м2 , V = s*t, м3, где t = 0.25 м - толщина доски; b = 0.24 м - ширина необрезной доски в широком конце; h - длина необрезной доски, меняется от 4.5 м до 6 м через 0.25 м; L - длина обрезной доски, меняется от 2 м до 4.25 м через 0.25 м.
Анализ исходных данных. В рассматриваемом примере величины b, l, h и t являются исходными данными. Входными данными являются также не обозначенные буквами начальные и конечные длины необрезной и обрезной досок, а также величины их изменения (шаги). Объем обрезной доски V является выходной величиной. Роль площади обрезной доски S двойная: она одновременно является выходной величиной и входной для определения величины V, то есть промежуточной величиной. Для составления программы решения задачи на языке программирования высокого уровня Visual-Basic, всем переменным необходимо присвоить имена, согласно синтаксиса языка программирования.Результаты анализа исходных данных представляются в виде таблицы 3.
Таблица 3
| № | Наименование данных | Обозначение | Имя | Характерис- тика | Значение |
| Толщина доски | t | T | входная | 0.25 | |
| Ширина необрезной доски | b | B | входная | 0.24 | |
| Начальная длина необрезной доски | - | H1 | входная | 4.6 | |
| Конечная длина необрезной доски | - | H2 | входная | ||
| Шаг изменения длины необрезной доски | - | H3 | входная | 0.25 | |
| Текущая длина необрезной доски | - | H | входная служ. | - | |
| Начальная длина обрезной доски | - | L1 | входная | ||
| Конечная длина обрезной доски | - | L2 | входная | 4.25 | |
| Шаг изменения обрезной доски | - | L3 | входная | 0.25 | |
| Текущая длина обрезной доски | l | L | входная служ. | - | |
| Площадь обрезной доски | s | S | входная пром. | - | |
| Объем обрезной доски | v | V | выходная | - |
Затем производиться построение алгоритма и решение задачи с использованием операторов цикла, логических операторов и операторов ввода и вывода данных. Результатом работы является таблица результатов расчета и графики функций.
Упражнение 1. Выполните задания:
1. Составить алгоритм вычисления суммы кубов трех чисел.
2. Составить алгоритм вычисления среднего арифметического четырех чисел.
3. Составить алгоритм, позволяющий: вывести все элементы 3-х значного целого числа в обратном порядке.
4. Проверить, превышает ли 1000 произведение двух натуральных двузначных чисел, вводимых с клавиатуры.
5. Составить алгоритм, позволяющий: ввести целое число с клавиатуры, если оно положительное посчитать корень из него, иначе – возвести его в квадрат и вывести соответствующее сообщение на экран.
6. Составить алгоритм, позволяющий: ввести целое число с клавиатуры, если его значение меньше 200, - вывести на экран соответствующий числу - символ по кодам ACII.
7. Составить алгоритм, позволяющий: ввести два числа с клавиатуры и определить, какое из них больше их среднего арифметического.
8. Составить алгоритм программы, устанавливающей, одного ли знака два числа, вводимые с клавиатуры.
9. Составить алгоритм. Превышает ли площадь прямоугольника со сторонами a, b площадь круга радиуса r=(a+b)/4. Данные вводятся с клавиатуры.
10. Найти сумму десяти произвольных чисел. Результат обозначить через S.
11. Вычислить z=åI, где I меняется от m до n, m и n вводятся с клавиатуры.
12. Вычислить p=åi2 , где I меняется от m до n. N и m вводится с клавиатуры.
13. Каждое число вводить по очереди в переменную х. В цикле осуществлять ввод очередного значения х и выполнять операции сложения чисел и увеличения счетчика на 1.
14. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; из них найти минимальное; вывести соответствующее сообщение на экран.
Контрольные вопросы:
1. Что такое алгоритм? Перечислите базовые структуры алгоритмов, их разновидности, способы описания, условные обозначения для блоков алгоритма.
2. Перечислите Этапы решения задачи на ЭВМ. Объясните каждый этап.
3. Выполните контрольную работу.
Задания для контрольной работы:
15. Составить алгоритм, позволяющий: вывести все элементы 5-ти-значного целого числа в обратном порядке.
16. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; из них замените все 2 на 5; вывести первоначальные числа и полученные на экран.
17. Составить алгоритм, позволяющий: ввести целое число с клавиатуры, определить четное оно или нет и вывести соответствующее сообщение на экран.
18. Составить алгоритм, позволяющий: ввести два числа с клавиатуры и определить наибольшее из них.
19. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и сумму всех чисел из введенных, которые кратны 3-м или 5-ти; вывести соответствующее сообщение на экран.
20. Составить алгоритм, позволяющий: вывести все элементы 4-х-значного целого числа в обратном порядке.
21. Составить алгоритм, позволяющий: ввести два числа с клавиатуры и определить, какое из них делится на 3.
22. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; из них найти максимальное; вывести соответствующее сообщение на экран.
23. Составить алгоритм, позволяющий: ввести символьную переменную, если она равна ' Z ', вывести соответствующее сообщение на экран.
24. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и сумму всех четных чисел из введенных; вывести соответствующее сообщение на экран.
25. Составить алгоритм, позволяющий: ввести целое число с клавиатуры, определить отрицательное оно или нет и вывести соответствующее сообщение на экран.
26. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и произведение всех чисел из введенных, которые кратны 2-м и 4-ти; вывести соответствующее сообщение на экран.
27. Составить алгоритм, позволяющий: ввести целое число с клавиатуры, определить равно оно 0 или нет и вывести соответствующее сообщение на экран.
28. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и произведение всех кратных 7 чисел из введенных; вывести соответствующее сообщение на экран.
29. Составить алгоритм, позволяющий: ввести две символьные переменные, найти из них переменную с максимальным кодом по ASCII-таблице и вывести соответствующее сообщение на экран.
30. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и сумму всех отрицательных чисел из введенных; вывести соответствующее сообщение на экран.
31. Составить алгоритм, позволяющий: ввести целое число с клавиатуры, определить кратно ли оно 5 или нет и вывести соответствующее сообщение на экран.
32. Составить алгоритм, позволяющий: ввести два числа с клавиатуры, определить максимальное из их синусов и вывести соответствующее сообщение на экран.
33. Составить алгоритм, позволяющий: ввести символ с клавиатуры, если его код равен 65, вывести на экран символ.
34. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и произведение всех отрицательных чисел из введенных; вывести соответствующее сообщение на экран.
35. Составить алгоритм, позволяющий: вывести на экран значение произведения 10-ти следующих друг за другом чисел, начиная с цифры 5.
36. Составить алгоритм, позволяющий: ввести число с клавиатуры, если его значение больше 100, - вывести на экран соответствующий числу - символ по кодам ACII.
37. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и произведение всех положительных чисел из введенных; вывести соответствующее сообщение на экран.
38. Составить алгоритм, позволяющий: ввести два числа с клавиатуры, определить минимальное из их косинусов и вывести соответствующее сообщение на экран.
39. Составить алгоритм, позволяющий: ввести два числа с клавиатуры, определить максимальное из них по модулю и вывести соответствующее сообщение на экран.
40. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и сумму всех нечетных чисел из введенных; вывести соответствующее сообщение на экран.
41. Составить алгоритм, позволяющий: ввести 15 чисел с клавиатуры, вывести эти числа в следующем порядке: 1-я строка: 1-е, 4-е, 7-е, 10-е, 13-е, 2-я строка: 14-е, 11-е, 8-е, 5-е, 2-е.
42. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; посчитать количество и произведение всех нечетных чисел из введенных; вывести соответствующее сообщение на экран.
43. Составить алгоритм, позволяющий: ввести n чисел в одномерный массив с клавиатуры; ввести дополнительно с клавиатуры ещё одно (n+1)-е число; проверить наличие в массиве числа, равного дополнительному (n+1)-ому; вывести соответствующее сообщение на экран.
44. Составить алгоритм, позволяющий: ввести n чисел в одномерный массив с клавиатуры; суммировать все числа массива; вывести результат на экран.
45. Составить алгоритм, позволяющий: ввести n чисел с клавиатуры; из них найти наиболее близкое к нулю по модулю; вывести соответствующее сообщение на экран.
46. Составить алгоритм, позволяющий: вычислить скалярное произведение двух векторов. Координаты векторов Х(х1, х2,…, х10) и У(у1, у2,…, у10) определить, как два массива вещественных чисел.
47. Составить алгоритм, позволяющий: вычислить количество и сумму всех четных чисел, введенных с клавиатуры.
48. Составить алгоритм, позволяющий: вычислить количество и сумму всех нечетных чисел, введенных с клавиатуры.
49. Составить алгоритм, позволяющий: ввести два числа с клавиатуры, определить минимальное из их корней и вывести соответствующее сообщение на экран.
50. Составить алгоритм, позволяющий: вывести на экран 20 целых чисел х1, х2,…,х20, а затем получить последовательность чисел х20, х10, х19, х9,…, х11, х1, используя одномерный массив.
51. Составить алгоритм, позволяющий: ввести два числа с клавиатуры, определить максимальное из их кубов и вывести соответствующее сообщение на экран.
52. Составить алгоритм, позволяющий: ввести n чисел в одномерный массив с клавиатуры; ввести дополнительно с клавиатуры ещё одно (n+1)-е число; проверить наличие в массиве чисел, больше дополнительного (n+1)-ого; вывести соответствующее сообщение на экран.
53. Составить алгоритм, позволяющий: ввести фразу «СТРОКА СИМВОЛОВ», распечатать ее целиком и ее часть «СИМВОЛ». Для этой цели введем массив с именем ctroka, в котором ctroka[1]=’C’, ctroka[2]=’Т’,…, ctroka[14]=’О’, ctroka[15]=’В’.
|
|
|
