close

Вход

Забыли?

вход по аккаунту

- (филиал) ВолгГТУ

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ВОЛЖСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)
ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО
УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
КАФЕДРА «ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ»
Д.Н. Лясин, Фадеева М.В.
Основы алгоритмизации.
Методические указания
Волгоград 2014
УДК 004.056
Издается по решению редакционно-издательского совета
Волгоградского государственного технического университета
Лясин, Д.Н. Фадеева М.В.. Основы алгоритмизации.
[Электронный ресурс]: методические указания / Д.Н. Лясин, М.В. Фадеева
//Сборник «Методические указания» Выпуск.-Электрон. текстовые
дан.(1файл:207 Kb) – Волжский: ВПИ (филиал) ВолгГТУ,2014.Систем.требования:Windows 95 и выше; ПК с процессором 486+; CD-ROM.
Содержатся сведения, необходимые для получения навыков алгоритмической
подготовки решения практических задач на компьютере. Дано определение алгоритма
и описание его свойств, рассмотрен порядок разработки алгоритмов, Приведена
классификация типовых алгоритмов с примерами их реализации. Даны практические
примеры решения задач на составление алгоритмов и их пошаговой трассировки. Для
самостоятельного выполнения предложены варианты заданий, которые помогут
практическому освоению материала.
Предназначены для студентов, обучающихся по направлению 230100 "Информатика и вычислительная техника" и направлению 231000 "Программная инженерия"
всех форм обучения в рамках курса «Основы программирования»
Библиогр.: 5 назв.
Издается по решению редакционно-издательского совета Волгоградского государственного технического университета
©
©
Волгоградский государственный
технический университет, 2014
Волжский политехнический институт, 2014
Лабораторная работа №1
Основы алгоритмизации.
Цель: ознакомиться с основными принципами алгоритмизации
вычислительных процессов, получить практические навыки в составлении
алгоритмов решения практических задач.
1. Основные сведения
Понятие алгоритма.
Одним из фундаментальных понятий в информатике является понятие
алгоритма. Алгоритм - описанная на некотором языке точная конечная
система правил, определяющая содержание и порядок действий
над некоторыми объектами, строгое выполнение которых дает решение
поставленной задачи. Или: алгоритм — это точный набор инструкций,
описывающих последовательность действий исполнителя для достижения
результата решения задачи за конечное время.
Понятие алгоритма, являющееся фундаментальным в математике и
информатике, возникло задолго до появления средств вычислительной
техники. Слово «алгоритм» появилось в средние века, когда европейцы
познакомились со способами выполнения арифметических действий в
десятичной системе счисления, описанными узбекским математиком
Муххамедом бен Аль-Хорезми. Слово алгоритм - есть результат европейского
произношения слов Аль-Хорезми. Первоначально под алгоритмом понимали
способ выполнения арифметических действий над десятичными числами. В
дальнейшем это понятие стали использовать для обозначения любой
последовательности действий, приводящей к решению поставленной задачи.
Любой алгоритм существует не сам по себе, а предназначен для
определенного
исполнителя
(человека,
робота,
компьютера,
языка программирования и т.д.). Значение слова «алгоритм» очень схоже со
значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта
или процесса,
алгоритм
характеризуется
следующими
свойствами:
дискретностью,
массовостью,
определенностью,
результативностью,
формальностью.
Свойства алгоритма.
Дискретность
(
разрывность)
это
свойство
алгоритма,
характеризующее его структуру: каждый алгоритм состоит из отдельных
законченных действий, говорят «Делится на шаги».
Массовость
применимость
алгоритма
ко
всем
задачам рассматриваемого типа, при любых исходных данных. Например,
алгоритм решения квадратного уравнения в области действительных чисел
должен содержать все возможные исходы решения, т.е., рассмотрев значения
дискриминанта, алгоритм находит либо два различных корня уравнения, либо
два равных, либо делает вывод о том, что действительных корней нет.
Понятность — алгоритм для исполнителя должен включать только те
команды, которые ему (исполнителю) доступны, которые входят в его систему
команд.
Определенность (детерминированность, точность) - свойство алгоритма,
указывающее на то, что каждый шаг алгоритма должен быть строго определен
и не допускать различных толкований. Также строго должен быть определен
порядок выполнения отдельных шагов.
Результативность - свойство, состоящее в том, что любой алгоритм
должен завершаться за конечное (может быть очень большое) число
шагов. Формальность - это свойство указывает на то, что любой исполнитель,
способный воспринимать и выполнять инструкции алгоритма, действует
формально, т.е. отвлекается от содержания поставленной задачи и лишь
строго выполняет инструкции. Рассуждать «что, как и почему?» должен
разработчик алгоритма, а исполнитель формально (не думая) поочередно
исполняет предложенные команды и получает необходимый результат.
Выполняя алгоритм, исполнитель может не вникать в смысл того, что он
делает, и вместе с тем получать нужный результат. В таком случае говорят,
что исполнитель действует формально, т. е. отвлекается от содержания
поставленной задачи и только строго выполняет некоторые правила,
инструкции. В этом случае исполнение алгоритма можно поручить не
человеку, а машине. Действительно, простейшие операции, на которые при
создании алгоритма расчленяется процесс решения задачи, может реализовать
и машина, специально созданная для выполнения отдельных команд
алгоритма и выполняющая их в последовательности, указанной в алгоритме.
Это положение и лежит в основе работы автоматических устройств,
автоматизации деятельности человека.
Пример:
Рассмотрим процесс создания алгоритма на примере нахождения корня
квадратного уравнения и проверим наличие его основных свойств.
Пусть есть квадратное уравнение: ax2 + bx + c = 0.
1.
Ввести коэффициенты уравнения a, b, c с клавиатуры.
2.
Если коэффициент a равен 0, перейти к шагу 8.
3.
Вычислить значение дискриминанта:
2
D = b – 4ac
4.
Если D<0 перейти к шагу 17.
5. Вычислить корни уравнения:
6.
7.
8.
9.
Вывести значения корней x1, x2 на экран.
Перейти к шагу 18.
Если b=0, перейти к шагу 12.
Вычислить x=-c/b.
10.
Вывести на экран значение корня x.
11.
Перейти к шагу 18.
12.
Если с=0, перейти к шагу 15.
13.
Вывести на экран сообщение “Нет решений”.
14.
Перейти к шагу 18.
15.
Вывести на экран сообщение “Бесконечное количество корней”.
16.
Перейти к шагу 18.
17.
Вывести на экран сообщение “Нет действительных корней”.
18.
Закончить.
Каждое указание алгоритма предписывает исполнителю выполнить одно
конкретное законченное действие (дискретность). Этот алгоритм может
применяться не зависимо от входных данных, рассматривается как
положительный, так и отрицательный дискриминант (массовость). Каждая
команда – это простое логическое или арифметическое действие (понятность
Предписания алгоритма надо выполнять последовательно, одно за другим, в
соответствии с указанным порядком их записи (определенность). Выполнение
всех
предписаний
гарантирует
правильное
решение
задачи
(результативность).
Способы записи алгоритмов.
Выделяют три наиболее распространенные на практике способа записи
алгоритмов:
• словесный (запись на естественном языке);
• графический (запись с использованием графических символов);
• программный (тексты на языках программирования).
Словесный способ – способ записи алгоритма на естественном языке.
Данный способ очень удобен, если нужно приближенно описать суть
алгоритма. Однако при словесном описании не всегда удается ясно и точно
выразить логику действий.
В качестве примера словесного способа записи алгоритма рассмотрим
алгоритм нахождения площади прямоугольника S=a*b, где S – площадь
прямоугольника; а, b – длины его сторон.
Очевидно, что a, b должны быть заданы заранее, иначе задачу решить
невозможно.
Словестный способ записи алгоритма выглядит так:
1.
Начало алгоритма.
2.
Задать численное значение стороны a.
3.
Задать численное значение стороны b.
4.
Вычислить площадь S прямоугольника по формуле S=a*b.
5.
Вывести результат вычислений.
6.
Конец алгоритма.
Выше рассмотренный пример нахождения корня квадратного уравнения
также есть способ записи алгоритма на естественном языке (словесный
способ). Достоинством подобного способа представления алгоритма является
относительная свобода языковых средств при описании. Его недостатком
является громоздкость алгоритма в подобной форме записи, трудности чтения
алгоритма, а также внесения в него изменений.
Графический способ. Для более наглядного представления алгоритма
используется графический способ. Существует несколько способов
графического описания алгоритмов. Наиболее широко используемым на
практике графическим описанием алгоритмов является использование блоксхем. Несомненное достоинство блок схем – наглядность и простота записи
алгоритма.
Схема — графическое представление определения, анализа или метода
решения задачи, в котором используются символы для отображения операций,
данных, потока, оборудования и т. д. (ГОСТ 19.701-90).
Правила оформления блок-схем можно посмотреть в ГОСТ 19.701-90.
Схемы алгоритмов, программ, данных и систем. Условные обозначения и
правила выполнения.
ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения.
ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные
графические.
Каждому действию алгоритма соответствует геометрическая фигура
(блочный символ). Перечень наиболее часто употребляемых символов
приведен в таблице ниже.
Таблица 1. Графические элементы представления различных блоков алгоритма
Название символа
Терминатор
Обозначение
Пояснения
Начало и конец программы
Процесс
Выполнение одной или
нескольких
операций,
обработка данных любого
вида (изменение значения
данных,
формы
представления,
расположения).
Внутри
фигуры
записывают
непосредственно
сами
операции
Решение
Отображает решение или
функцию переключательного
типа с одним входом и двумя
или более альтернативными
выходами, из которых только
один может быть выбран
после вычисления условий,
определенных внутри этого
элемента
Ввод-вывод
Ввод данных с клавиатуры
или вывод на экран
Циклический процесс
Начало и конец цикла −
операции,
выполняемые
внутри цикла, размещаются
между ними.
Условия
цикла
и
приращения
записываются
внутри символа начала или
конца цикла − в зависимости
от типа организации цикла.
Предопределенный
Обращение
к
подпрограмме или функции
процесс
Комментарии
Соединитель
Используется для более
подробного описания шага,
процесса
или
группы
процессов.
Описание
помещается
со
стороны
квадрат-ной
скобки
и
охватывается ей по всей
высоте. Пунктирная линия
идет
к
описываемому
элементу,
либо
группе
элементов
Символ отображает выход
в часть схемы и вход из
другой части этой схемы.
Используется для обрыва
линии и продолжения ее в
другом месте (пример: раз-
деление
блок-схемы,
не
помещающейся на листе).
Соответствующие
соединительные
символы
должны
иметь
одно
уникальное обозначение.
Соединяют
элементы
схемы
для
указания
последовательности
выполняемых действий
Соединительные
линии
Пример графического алгоритма нахождения площади прямоугольника будет
выглядеть так:
начало
Ввести
длину и
ширину: а, в
S=a*b
Вывести S
конец
Программный способ. Рассмотренные выше способы удобны для
программиста, но не приемлемы для ЭВМ, поскольку они не могут быть
однозначно поняты. Программный способ – это запись алгоритма на языке
программирования. Язык программирования – это знаковая система,
предназначенная для описания процессов решения задач и их реализации на
ЭВМ. Реализация означает, что описания могут быть введены в ЭВМ и
однозначно ею поняты. К языкам программирования относятся языки команд
или машинные языки и языки высокого уровня.
Алгоритм нахождения корня квадратного уравнения
программным способом на языке С будет выглядеть так:
# include <conio.h>
#include<stdio.h>
int main()
{ int a, b,s;
scanf(“%d %d”, &a, &b);
s=a*b;
printf(“Площадь прямоугольника %d”, s);
getch();
return 0;
}
описанный
Правила построения алгоритма
Чтобы алгоритм выполнил свое предназначение, его необходимо строить
по определенным правилам. Поэтому нужно говорить все же не о свойствах
алгоритма, а о правилах построения алгоритма, или о требованиях,
предъявляемых к алгоритму.
Первое правило — при построении алгоритма, прежде всего, необходимо
задать множество объектов, с которыми будет работать алгоритм.
Формализованное (закодированное) представление этих объектов носит
название данных. Алгоритм приступает к работе с некоторым набором
данных, которые называются входными, и в результата своей работы выдает
данные, которые называются выходными. Таким образом, алгоритм
преобразует входные данные в выходные. Пока мы не имеем
формализованных входных данных, мы не можем построить алгоритм.
Второе правило — для работы алгоритма требуется память. В памяти
размещаются входные данные, с которыми алгоритм начинает работать,
промежуточные данные и выходные данные, которые являются результатом
работы алгоритма. Память является дискретной, т. е. состоящей из отдельных
ячеек. Поименованная ячейка памяти носит название переменной. В теории
алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы
можем предоставить алгоритму любой необходимый для работы объем
памяти.
Третье правило — дискретность. Алгоритм строится из отдельных шагов
(действий, операций, команд). Точнее — из множества шагов.
Четвертое правило — детерминированность. После каждого шага
необходимо указывать, какой шаг выполняется следующим, либо давать
команду остановки.
Пятое правило — сходимость (результативность). Алгоритм должен
завершать работу после конечного числа шагов. При этом необходимо
указать, что считать результатом работы алгоритма.
Виды алгоритмов.
Алгоритмы в зависимости от цели, начальных условий задачи, путей ее
решения, определения действий исполнителя подразделяются следующим
образом:
Линейный алгоритм (линейная структура) – это такой алгоритм, в котором
все действия выполняются последовательно друг за другом и только один
раз. Схема представляет собой последовательность блоков, которые
располагаются сверху вниз в порядке их выполнения. Первичные и
промежуточные данные не оказывают влияния на направление процесса
вычисления. В блок-схеме линейный алгоритм обозначается следующим
образом:
Действие 1
Действие 2
Действие 3
Рассмотрим построение линейного алгоритма на конкретных примерах.
Пример 1. Зная длины двух сторон прямоугольника, вычислить его
площадь и периметр.
Пусть a, b - длины сторон прямоугольника. Необходимо найти S площадь треугольника, P - периметр.
Решение:
Входные данные: a, b.
Выходные данные: S, P.
Для большей наглядности приведем пример словесного представления
алгоритма с графическим.
1. Начало
начало
1
Ввести длины сторон
прямоугольника a, b
2.
2
3. Посчитать периметр
прямоугольника P=(a+b)*2
Вычислить площадь
прямоугольника S = a*b
4.
Вывести значения P и S
на экран
5.
Ввод a, b
p=(a+b)*2
3
S = a*b
4
Вывод P, S
6. Закончить
конец
Выполним трассировку этого алгоритма при следующих входных
значениях a=10, b=5
№ шага № блока a
b
p
S
Примечание
1
1
10 5
Вводим значения переменных
2
2
30
Вычисляем периметр
3
3
50
Вычисляем площадь
4
4
Выводим значения P и Sна экран
Конечно, для строго линейных алгоритмов нет необходимости выполнять
трассировку- ход вычислительного процесса здесь строго детерминирован,
но для разветвляющихся и циклических процессов этот прием может стать
важным инструментом для понимания работы алгоритма и поиска ошибок в
нем.
Проверить работоспособность алгоритма можно, выполнив его по шагам,
задавшись некоторыми входными значениями. Выполняя каждый блок
алгоритма, необходимо фиксировать значения выражений, формируемых в
этом блоке, изменения значений переменных, выполнение или невыполнение
условий переходов (для разветвляющихся и циклических алгоритмов). Для
удобства анализа отслеживание хода алгоритма можно записывать в
трассировочную таблицу, в которой необходимо фиксировать номер шага
алгоритма, какой блок графической схемы выполнялся на этом шаге
(предварительно все блоки в схеме необходимо перенумеровать), значения
переменных и выражений, изменяющихся на данном шаге. Построим
трассировочную таблицу для алгоритма поиска площади и периметра
прямоугольника.
Пример 2.
Известны плотность и геометрические размеры цилиндрического слитка,
полученного в металлургической лаборатории. Найти объем, массу и
площадь основания слитка.
Решение:
Входные данные: r - радиус основания цилиндра, h - высота цилиндра, plплотность материала слитка.
Выходные данные: m - масса слитка, V - объем, S - площадь основания.
Блок-схема:
начало
Ввести входные
данныеr, h,pl
Вычислить площадь
основания S= Вычислить объем слитка
V= Вычислить массу слитка
m=pl*V
Вывести выходные
данные на экранM,S,V
конец
Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно
условие, в результате проверки которого ЭВМ обеспечивает переход на один
из двух возможных шагов.
В блок-схеме разветвляющийся алгоритм обозначается следующим
образом:
нет
да
условие
Действие 1
Действие 2
а) полное ветвление
да
условие
нет
Действие 1
б) неполное ветвление:
Пример 3.
Даны целые числа x, y. Определить, принадлежит ли точка с
координатами x, y кругу радиуса r.
Решение:
Входные данные: r - радиус окружности, x, y – координаты точки
Выходные данные: Вывод надписи на экран: входит- не входит.
Для большей наглядности приведем пример словесного представления
алгоритма с графическим.
1. Начало
начало
2. Ввести радиус окружности и
r, x, y
координаты точки: r, x, y.
3. Проверить,
выполняется
условие: ли
нет
3.1 Если условие выполняется, то
на экран выводится надпись: входит
да
входит
Не входит
3.2 Если условие не выполняется, то на экран выводится
надпись: не входит
конец
4. Конец
Эта задача подразумевает использование полного ветвления, т.к. есть
предписания действий и в случае когда условие выполняется, и в случае
когда условие не выполняется. В следующем примере рассмотрим неполное
ветвление.
Пример 4.
Дано число а. Если оно четное, то разделить его на 2. Вывести число а
на экран. Входные данные: число а. Выходные данные: число а.
1. Начало
начало
2. Ввести число а.
3. Проверить, является ли число
четным: аmod2 0?
Ввод а
нет
да
a mod 2=0
3.1 Если условие выполняется, то
а=а/2
а=а/2
4. Вывести число а.
Вывод а
5. Конец.
конец
В некоторых задачах ветвление представлено как множественный выбор.
Это отражено в следующем примере.
Пример 5.
Вычислить значение функции в точке:
, если 0
F(x)=sin, если 1
0, если 2
Решение:
Входные данные: число k , параметр функции x.
Выходные данные: значение функции F в точке x при определенном k.
Блок-схема:
начало
Ввести х, k
k
0
1
!"#
2
F=0
Вывод F
конец
Пример 6.
Даны три различных числа: a, b, c. Определить самое наибольшее и
самое наименьшее из них.
Решение:
Входные данные: числа: a, b, c.
Выходные данные: значения наибольшего числа и наименьшего числа.
Блок-схема:
начало
1
нет
нет
нет
10
6
2
a>c и a>b
нет
b>c
a наибольшее
b наименьшее
a>b
11
да
да
да
c наибольшее
a наименьшее
a, b, c
c наибольшее
b наименьшее
да
3
b>c
4
a наибольшее
с наименьшее
5
12
нет
да
7
a>c
B наибольшее
a наименьшее
9
b наибольшее
c наименьшее
8
конец
Выполним трассировку этого алгоритма для различных a b и с.
1. a=3, b=2, c=6
№ шага № блока a
b
c
Примечание
1
1
3
2
6
Вводим значения переменных
2
2
a>b и a>c = ложь (Не выполняется 2е условие)
3
6
b>c = ложь
4
10
a>b =истина
12
Выводится
«с-наибольшее,
bнаименьшее»
2. a=5, b=5, c=4
№ шага № блока a
1
1
5
2
2
3
4
12
b
5
c
4
6
7
Примечание
Вводим значения переменных
a>b и a>c = ложь (Не выполняется 1е условие)
b>c = истина
a>с =истина
Выводится
«b-наибольшее,
cнаименьшее»
Циклический
алгоритм —
алгоритм,
предусматривающий
многократное повторение одного и того же действия (одних и тех же
операций) Над новыми исходными данными. К циклическим алгоритмам
сводится большинство методов вычислений, перебора вариантов. Цикл
программы — последовательность команд (серия, тело цикла), которая
может выполняться многократно (для новых исходных данных) до
удовлетворения некоторому условию.
Циклические алгоритмы в свою очередь можно разбить на два вида:
явные (когда заранее известно количество повторений) и неявные (когда
заранее количество повторений неизвестно, концом цикла является
выполнение условия).
Неявные циклические алгоритмы также можно разделить еще на два
вида: с пред условием (сначала проверяется условие, если оно выполняется,
делается повторение цикла) и с пост условием (сначала делается повторение
цикла, а потом проверяется условие и если оно выполняется, то происходит
следующее повторение цикла).
В блок- схеме явный циклический алгоритм представляется
следующим образом:
Начало цикла
тело цикла
Конец цикла
Неявный цикл в блок – схеме обозначается следующим образом:
Цикл с постусловем
Цикл с предусловием
нет
условие
да
Тело цикла
Тело цикла
да
условие
нет
Рассмотрим пример с использованием явного цикла.
Пример 7.
Дана последовательность, каждый член которой вычисляется по
правилу: $ 1, % 2$ ,…,& 2&'% . Вычислить первые 20 членов
последовательности.
Решение:
Так как нам заранее известно количество повторений (по условию 20
нужно вычислять x), то будем использовать явный цикл.
Входные данные: число $ 1. Выходные данные: значения &
Снова рассмотрим словесную и графическую запись алгоритма для
большей наглядности:
1. Начало
Началоо
2. Присвоить $ 1
1
X0=1
3. Вывести x0
2
Вывод X0
4. Повторять 19 раз:
4.1 & 2&'%
3
i=1..19
4
Xi=2*Xi-1
4.2 вывести на печать &
4.4. Переход к следующей итерации
5
Вывод Xi
6
i=i+1
5. Конец
Конец
Пример 8.
Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый
следующий день он увеличивал дневную норму на 50% от нормы
предыдущего дня. Через сколько дней спортсмен пробежит суммарный путь
60 км?
Решение:
В данном случае заранее неизвестно сколько дней должен бегать
спортсмен, но известно что всего он должен пробежать 60 км. Значит, будет
использоваться неявный цикл, условием выхода из которого будет
суммарный путь >=60км.
Входные данные: нет
Выходные данные: kol-количество дней, необходимых для суммарного
пути >=60.
1. Начало.
начало
2. Ввести s, kol.
3. Посчитать сколько километров
пробежал за следующий день и
получить суммарный путь:
s=s+0.5s .
4. Защитать еще один день бега
kol=kol+1.
5. Если суммарный путь меньше
60, то повторить шаги 3-4, если
больше либо равно, то перейти
к пункту 6.
6. Вывести на экран kol.
s=10, kol=1
s+0.5s
s=s+0.5s
kol=kol+1.
нет
s>=60
да
kol
7. Конец.
конец
Пример 9.
Найти
сумму
элементов
последовательности
до
первого
отрицательного элемента. Элементы последовательности вводятся
пользователем.
Решение:
Входные данные: X- элементы последовательности.
Выходные данные: s – сумма элементов последовательности до первого
отрицательного.
Блок-схема:
начало
Вводим первый элемент
последовательности
Ввести первый
элемент X
Изначально сумма
элементов равно нулю.
s=0
нет
X>=0
да
s=s+X
Ввестиочередной
элемент X
Вывод суммы s
Пока очередной элемент
последовательности
больше либо равен нуля
Добавляем его к сумме
Вводим значение
следующего элемента на
экран
Когда введем
отрицательный элемент –
выйдем из цикла и
выведем значение суммы
на экран
конец
Пример 10.
Дана последовательность из 100 чисел. Определить, встречаются ли в
этой последовательности числа, кратные 13.
Решение:
Входные данные: Элементы последовательности.
Выходные данные: Срока ответа «Да, встречаются» или «Нет, не
встречаются»
Блок-схема:
начало
Изначально считаем, что
таких чисел нет
bFind=false
Повторяем 100 раз
I = 0 .. 99
Вводим очередное число с
клавиатуры
Ввод очередного
элемента X
X mod 13=0 и
bFind=false
Если число делится на 13 без
остатка и подобных числе еще
на встречалось
да
bFind=true
нет
Переходим к следующей
итерации
i=i+1
нет
Фиксируем, что такое число
найдено
да
bFind=true
Проверяем результат поиска
чисел
Выводим строку с
результатом поиска на экран
Вывод:
Нет, не, встречаются
Вывод:
Да, встречаются
конец
Комментарий к решению: переменная bFind логического типа фиксирует
результат поиска заданных чисел в последовательности: если она равна false,
значит среди введенных чисел не было ни одного, кратного 13. Если
найдется хотя бы один элемент, кратный 13, то переменная bFind
устанавливается в true. Первоначально устанавливаем эту переменную в
false, предполагая, что таких чисел нет. В процессе ввода элементов
последовательности проверяем каждый элемент на кратность 13 и если хотя
бы один элемент кратен 13 – переменную bFind устанавливаем в true. По
выходе из цикла результирующая строка выбирается на основе значения
bFind.
2. Порядок выполнения работы
1. Ознакомьтесь
с
теоретическими
основами
алгоритмизации
вычислительных процессов в настоящих указаниях и конспектах лекций.
2. Получите вариант задания у преподавателя.
3. Составьте алгоритм решения задачи согласно варианту задания,
оформите его в графической форме и словесной форме,.
4. Проверьте работоспособность вашего алгоритма, выполнив его
трассировку на нескольких наборах входных данных.
5. Составьте отчет по лабораторной работе.
6. Отчитайте работу преподавателю.
Содержание отчета
Отчет по лабораторной работе должен содержать следующие сведения:
- название и цель работы;
- вариант задания;
- графическую схему алгоритма решения задачи и его словесное
описание;
- трассировочную таблицу для разработанного алгоритма на некотором
наборе входных данных;
3. Пример выполнения лабораторной работы
Во введенном с клавиатуры натуральном числе подсчитать количество цифр
2 в его десятичной записи.
Пример вычислений:
Вводимое число: 23422
Ответ: 3
Начало
1
Ввод числа n
2
countOf2=0
нет
3
n ≠ 0
да
4
digit = nдаmod 10
да
5
digit=2
6
countOf2=countOf2+1
нет
7
n = n div 10
8
Вывод countOf2
Конец
Блок-схема алгоритма решения задачи
Трассировка алгоритма решения задачи
№ шага
№ блока
1
1
2
2
3
3
4
4
5
5
n
countOf2
digit
Примечание
Вводим n с клавиатуры
2342
0
2342 ≠ 0 – истина
2
Digit=2342 mod 10=2
2=2 - истина
6
6
7
7
8
3
9
4
10
5
11
7
12
3
13
4
14
5
15
7
16
3
17
4
18
5
19
6
20
7
21
3
0 ≠ 0 – ложь
22
8
Вывод 2
23
1
234
n=2342 div 10=234
242 ≠ 0 – истина
4
Digit=234 mod 10=4
4=2 -ложь
23
n=234 div 10=23
23 ≠ 0 – истина
3
Digit=23 mod 10=3
3=2 -ложь
2
n=23 div 10=2
2 ≠ 0 – истина
2
Digit=2 mod 10=2
2=2 - истина
2
0
n=2 div 10=0
Конец алгоритма
4. Варианты заданий к лабораторной работе.
Вариант№1
1. Даны n целых чисел. Определить, являются ли эти числа равными или
все они не меньше заданного А.
2. Дана последовательность чисел. Определить порядковый номер числа,
которое содержит наибольшую цифру в десятичной записи.
Вариант№2
1. Дана последовательность целых чисел, конец которой обозначен
нулем. Определить, кратны ли числа последовательности своему
порядковому номеру.
2. Дано число. Разделить цифры десятичной записи этого числа, стоящие
на нечётных местах на 3. Если не делятся без остатка, то оставить без
изменения.
Вариант№3
1. Дано n целых чисел. Найти количество отрицательных значений и
количество тех значений, которые больше первого из n чисел. Числа по
одному вводятся с клавиатуры.
2. Дана последовательность чисел. Посчитать сумму цифр десятичной
записи всех отрицательных чисел.
Вариант№4
1. Дана последовательность целых чисел, конец которой обозначен
нулем. Определить, все ли числа являются положительными или
положительные числа чередуются с отрицательными.
2. Дана последовательность чисел. Посчитать сумму цифр десятичной
записи всех чётных чисел.
Вариант№5
1. Дана последовательность целых чисел. Известно, что среди них
несколько раз встречаются
два подряд идущих нуля. Определить,
сколько раз встречается эта ситуация.
2. Дана последовательность чисел. Посчитать произведение цифр
десятичной записи последнего числа, кратного 5.
Вариант№6
1. Дана последовательность целых чисел до 0. Найти сумму целых чисел,
которые одновременно больше 20, меньше 100 и кратны 3.
2. Дана последовательность чисел. Посчитать произведение цифр
десятичной записи первого числа, кратного 3.
Вариант№7
1. Дана последовательность n целых чисел, где n- задано. Определить
,все ли числа попадают в заданный интервал [ x, y ].
2. Дано число. Посчитать сумму цифр в десятичной записи этого числа,
стоящих на чётных местах числа.
Вариант№8
1. Дана последовательность вещественных чисел. Определить, образуют
ли они возрастающую последовательность.
2. Дано число. Посчитать произведение тех цифр в десятичной записи
этого числа, которые кратны 3.
Вариант№9
1. Дана последовательность целых чисел. Определить количество чисел,
кратных разности текущего и предыдущего чисел.
2. Дано число. Посчитать разность между первой и последней цифрой
десятичной записи этого числа.
Вариант№10
1. Дана последовательность из 100 целых чисел. Определить количество
чисел в наиболее длинной подпоследовательности из подряд идущих
нулей.
2. Дано число. Разделить каждую цифру десятичной записи этого числа
на его порядковый номер. Полученное число напечатать.
Вариант№11
1. Дана последовательность целых чисел, конец которой обозначен
нулем. Определить, кратны ли числа последовательности своему
порядковому номеру.
2. Дано число. Разделить цифры в десятичной записи этого числа,
стоящие на нечётных местах на 3. Если не делятся без остатка, то
оставить без изменения.
Вариант№12
1. Дана последовательность вещественных чисел. Определить
порядковый номер первого отрицательного числа.
2. Дано число. Поменять местами соседние цифры в десятичной записи
этого числа.
Вариант№13
1. Дана последовательность целых чисел, среди которых есть два нуля.
Найти сумму чисел, расположенных между ними.
2. Дано число. Определить является ли сумма цифр десятичной записи
этого числа степенью числа 2.
Вариант№14
1. Дано натуральное число. Определить, является ли оно степенью целого
числа в диапазоне от 2 до 9.
2. Дано целое число. Определить, отсортированы ли по возрастанию
цифры в десятичной записи этого числа.
Вариант№15
1. Дана последовательность целых чисел. Определить, является ли она
сверхвозрастающей последовательностью
2. Дано целое число. Разложить это число на простые множители.
Вариант№16
1. Дана последовательность вещественных чисел, определить, являются
ли они возрастающими по величине дробной части.
2. Дано число. Определить, есть ли в десятичной записи этого числа
рядом стоящие одинаковые цифры.
Вариант№17
1. Дана последовательность целых чисел, определить, соблюдается ли в
этой последовательности принцип - четные числа на четных позициях,
нечетные – на нечетных.
2. Дано целое число. Определить, является ли десятичная запись этого
числа палиндромом (читается одинаково справа налево и слева
направо, например 43534).
Вариант№18
1. Дана последовательность
целых чисел, оканчивающаяся нулем.
Определить, является ли эта последовательность арифметической
прогрессией.
2. Дано целое число. Определить, одинаковы ли все цифры в десятичной
записи этого числа.
Вариант№19
1. Дана последовательность вещественных чисел. Найти и вывести на
экран все локальные минимумы – числа, меньшие предыдущего и
последующего.
2. Среди чисел от 10 до 1000,наяти и вывести на экран те, которые
меньше произведения цифр десятичной записи этого числа
Вариант№20
1. Даны два натуральных числа n и m. Среди чисел в диапазоне от n до m
найти то, у которого наибольшее количество делителей.
2. Среди чисел от 1 до 1000 найти все числа Армстронга. Число
Армстронга - натуральное число, которое в данной системе счисления
равно сумме своих цифр, возведённых в степень, равную количеству
его цифр (например, 153=13+53+33)
5. Контрольные вопросы
1.
Дайте определение алгоритма. В каких сферах человеческой
деятельности применимы алгоритмы?
2.
Какие свойства алгоритмов вам известны? Объясните на примере
разработанных вами алгоритмов суть этих принципов.
3.
Какие существуют формы записи алгоритмов? Опишите их
достоинства и недостатки. В каких случаях они применяются?
4.
Перечислите основные правила составления алгоритмов.
5.
Какие виды алгоритмических процессов вы знаете? Выделите их
в собственных алгоритмах.
6.
Что такое трассировка алгоритма? Для чего она применяется?
7.
Опишите алгоритм решения задачи из своего варианта задания.
6. Список литературы
1. Голицына О.Л., Попов И.И. Основы алгоритмизации и
программирования: учебное пособие. М.: Форум, 2008г. – 432с.
2. С. Скиена. Алгоритмы. Руководство по разработке. СПб.: БХВПетербург, 2011г. – 720с.
3. Т.Х. Кормен. Алгоритмы. Вводный курс. М.: Вильямс. 2014г. – 208с.
4. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы.
М.: Вильямс, 2010г.-720с.
5. Семакин И., Шестаков А. Основы алгоритмизации и
программирования. Практикум. М.: Академия, 2013г. – 144с.
Учебное издание
Дмитрий Николаевич Лясин
Марина Викторовна Фадеева
Основы алгоритмизации
Методические указания
План электронных изданий 2014 г. Поз. №
Подписано на « Выпуск в свет» . .12. Уч-изд. л. .
На магнитоносителе.
Волгоградский государственный технический университет.
400131, г. Волгоград, пр. Ленина, 28, корп. 1.
1/--страниц
Пожаловаться на содержимое документа