Построение и разработка алгоритмов

Размещено на http://www.allbest.ru/

Практическая работа

Тема: Построение и разработка алгоритмов



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

Студент должен знать:

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

уметь:

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

Теоретическое обоснование.

Понятие алгоритма - фундаментальное понятие. Слово "алгоритм" происходит от имени выдающегося математика средневекового Востока Мухаммеда аль-Хорезми. Им были предложены приёмы выполнения арифметических вычислений с многозначными числами. Позже в Европе эти приёмы назвали алгоритмами от латинского написания имени аль-Хорезми. В наше время понятие алгоритма понимается шире, не ограничиваясь только арифметическими вычислениями.

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

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

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

Алгоритм - это:

· точное и полное описание метода решения задачи, составленное из инструкций;

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

· точное предписание, определяющее последовательность действий, обеспечивающих получение требуемого результата из исходных данных;

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

Алгоритм можно представить с помощью:

1. графического описания (блок-схемы);

2. словесного описания;

3. в виде таблицы;

4. последовательности формул;

5. алгоритмического языка.

В настоящее время четко определен перечень свойств алгоритма:

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

2. понятность - свойство, отражающее ориентацию составления алгоритма на исполнителя;

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

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

5. массовость - свойство, заключающееся в том, что алгоритм решает класс задач, различающихся только исходными данными, а не одну конкретную задачу.

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

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

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

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

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



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

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

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

1. Линейный алгоритм - это такой алгоритм, в котором все операции выполняются последовательно одна за другой.

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

3. Алгоритмы циклической структуры.

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

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

Задание 1. Определить площадь трапеции по введенным значениям оснований (a и b) и высоты (h)

Запись решения задачи на алгоритмическом языке:

алг трапеция

вещ a,b,h,s

нач

ввод f,b,h

s:=((a+b)/2)*h

вывод s

кон

Запись алгоритма в виде блок-схемы (рис. 1):

Рисунок 1. Блок-схема линейного алгоритма



Задание 2. Определить среднее арифметическое двух чисел, если a положительное и частное (a/b) в противном случае.

Запись решения задачи на алгоритмическом языке:

алг числа

вещ a,b,c

нач

ввод a,b

если a>0

то с:=(a+b)/2

иначе с:=a/b

все

вывод с

кон

Запись алгоритма в виде блок-схемы (рис. 2):

Рисунок 2. Блок-схема алгоритма с ветвлением



Задание 3. Составить алгоритм нахождения суммы целых чисел в диапазоне от 1 до 10.

Запись решения задачи на алгоритмическом языке:

алг сумма

вещ a,s

нач

S:=0;

A:=1;

нц

пока a<=10

S:=S+a;

A:=a+1;

кц

вывод S

кон

Запись алгоритма в виде блок-схемы (рис. 3):

Рисунок 3. Циклический алгоритм с предусловием



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

алг сумма

вещ a,s

нач

S:=0;

A:=1;

нц

S:=S+a;

A:=a+1;

пока a<=10

кц

вывод S

кон

Запись алгоритма в виде блок-схемы (рис. 4):

Рисунок 4. Циклический алгоритм с постусловием

Ход работы:

1. Изучить теоретическое обоснование.

2. Выполнить практические задания.

3. Оформить отчет.

4. Ответить на контрольные вопросы.

Практические задания:

Задание №1. Составить алгоритм приготовления напитка на выбор. Нарисовать блок схему

Исходные данные:

1) чайник с чаем;

2) кофейник с кофе;

3) молочник с молоком;

4) чашка;

5) ложка;

6) сахарница с сахаром.

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

Алгоритм решения задачи:

	Способ 1	Способ 2	Способ 3
1 шаг
2 шаг
3 шаг
4 шаг

Обозначения: 1м- один мальчик, 2м - два мальчика, 1в - один взрослый.

Задание №3. Задан треугольник со сторонами a, b и c. Составить блок-схему алгоритма вычисления радиуса описанной окружности.

Решение. Опишем алгоритм решения данного задания на словесном уровне.

1. Входные данные: стороны а, b, с треугольника АВС. Переменная S используется для площади треугольника, р - для полупериметра треугольника, R - для радиуса описанной окружности.

2. Для вычисления используются формулы:

- полупериметр треугольника;

- формула Герона для вычисления площади треугольника;

- радиус описанной окружности треугольника.

3. Вывод R.

Задание №4. Составить блок-схему вычисления функции знака

где x - заданное вещественное число.

Решение. Опишем алгоритм решения данного задания на словесном уровне.

1. Входные данные: переменная х.

2. Проверяется введенное значение переменной х. В зависимости от введенного значения функция F принимает одно из значений: 0, 1 или -1. При вводе неверного значения (буква, слово) программа выдает сообщение «это слово».

3. Вывод значения.

Задание №5. Составить блок-схему вычисления и вывода на печать значения функции при значении x, изменяющемся от 0 до 3 с шагом 0,1. Значение a вводится с клавиатуры при выполнении программы.

Решение. Опишем алгоритм решения данного задания на словесном уровне.

1. Входные данные: переменная a.

2. Перед первым выполнением цикла необходимо задать необходимо, задать начальное значение аргумента х, равное 0.

3. Вычислить значение y и вывести его на печать.

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

5. Чтобы процесс не был бесконечным, необходимо задать условие повторения (х?3) или окончания цикла (х>3).

Контрольные вопросы.

1. Что такое алгоритм?

2. Свойства алгоритма.

3. Способы записи алгоритма.

4. Основные элементы блок-схемы.

5. Виды алгоритмов.

6. Отличительные особенности алгоритмов с предусловием и постусловием.

Содержание отчета:

1. Название и цель работы.

2. Результат выполнения практических заданий.

3. Ответы на контрольные вопросы.



Литература

Основные источники (ОИ):

Таблица 2б

Номер п/п	Автор	Наименование	Издательство, год издания
ОИ1	И. И. Сергеева	Информатика Режим доступа: http://znanium.com/ bookread2.php?id=517652	НИЦ ИНФРА-М, 2016
ОИ2	М. С. Цветкова	Информатика. [Текст]: Учебное пособие для студ. учреждений среднего профессионального образования	М.: Академия, 2017

Дополнительные источники (ДИ):

Таблица 2в

№ п/п	Автор	Наименование	Издательство, год издания
ДИ 1	В. Д. Колдаев	Сборник задач и упражнений по информатике Режим доступа: http://znanium.com/ bookread2.php?id=504814	ИНФРА-М, 2015
ДИ 2	Е. А. Колмыкова	Информатика. [Текст]: Учебное пособие для студ. учреждений среднего профессионального образования	М.: Академия, 2014
ДИ 3	Н. Г. Плотникова	Информатика и информационно-коммуникационные технологии (ИКТ) Режим доступа: http://znanium.com/ bookread2.php?id=433676	ИНФРА-М, 2014
ДИ4	Р. Ю Царев	Программные и аппаратные средства информатики Режим доступа: http://znanium.com/ bookread2.php?id=550017	Краснояр.: СФУ, 2015

Размещено на Allbest.ru

...