Отдельная инструкция в описании алгоритма

Основы алгоритмизации и технологии программирования

Понятие алгоритма и его свойства

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

       Алгоритм – описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение, поставленной задачи. Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» — человек из города Хорезми); в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.

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

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

        Дискретность (разрывность – противоположно непрерывности) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги».

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

    Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Прямо пойдешь – голову потеряешь, направо пойдешь – жену найдешь, налево пойдешь – разбогатеешь. Стоит Иван и думает, что дальше делать». Таких инструкций алгоритм содержать не может.

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

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

Способы описания алгоритмов

        Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

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

         Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем (рис. 1).

(1) Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат);

(2) Блок — процесс, предназначенный для описания отдельных действий;

(3) Блок — предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам);

(4) Блок — ввода/вывода с неопределенного носителя;

(5) Блок — ввод с клавиатуры;

(6) Блок — вывод на монитор;

(7) Блок — вывод на печатающее устройство;

(8) Блок – решение (проверка условия или условный блок);

(9) Блок, описывающий блок с параметром;

(10) Блок – границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»;

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

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

Основные алгоритмические конструкции

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

Линейная алгоритмическая конструкция

          Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i- гo действия (шага) выполняется (i+ 1)-е действие (шаг), если i-e действие – не конец алгоритма.

         Пример 1.

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

         Псевдокод:

Ввод двух чисел а, b .

Вычисляем сумму S = а + b .

Вывод S.

Конец.

Разветвляющаяся алгоритмическая конструкция

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

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

             Пример 2.

           Заданы три числа. Найти значение наименьшего из них Заданные числа обозначим: а, b, с; результирующее наименьшее – min. На рис. 5 представлена блок-схема алгоритма решения данной задачи.

Алгоритмическая конструкция «Цикл»

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

        Рассмотрим три типа циклических алгоритмов: ц uкл с параметром (который называют арифметическим циклом), цикл с предусловием и цикл с постусловием (их называют итерационными) .

Арифметический цикл

        В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение параметра равно N, на втором – N + h, на третьем – N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но такое, что дальнейшее его изменение приведет к значению, большему, чем К.

        Пример 3.

      Вывести 10 раз слово «Привет!».

       Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i=1 будет выведено первое слово, при i=2 будет выведено второе слова и т. д. Так как требуется вывести 10 слов, то последнее значение параметра i=10. В заданном примере требуется 10 раз повторить одно и то же действие: вывести слово «Привет!». Составим алгоритм, используя арифметический цикл, в котором правило изменения параметра i=1,10, 1. т. е. начальное значение параметра i=1; конечное значение i=10; шаг изменения h=1. На рис. 6 представлена блок-схема алгоритма решения данной задачи.

Цикл с предусловием

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

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

Цикл с постусловием

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

Рекурсивный алгоритм

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

Простые типы данных: переменные и константы

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

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

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

• необходимый объем памяти для ее хранения.

         Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от О до 255, что в двоичном коде (255₍₁₀₎=11111111₍₂₎) соответствует ячейке памяти длиной в 8 бит (или 1 байт).

          В описанных выше алгоритмах (примеры 1-3) все данные хранятся в виде переменных. Например, инструкция «Ввод двух чисел а, b » означает введение пользователем значений двух переменных, а инструкция «К=К + 1» означает увеличение значения переменной К на единицу.

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

         Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции «К=К+1» 1 есть константа, или для удобства обозначать идентификаторами: pi=3,1415926536. Только значение pi нельзя изменить, так как это константа, а не переменная.

Структурированные данные и алгоритмы их обработки

          Для повышения производительности и качества работы необходимо иметь данные, максимально приближенные к реальным аналогам. Тип данных, позволяющий хранить вместе под одним именем несколько переменных, называется структурированным. Каждый язык программирования имеет свои структурированные типы. Рассмотрим структуру, объединяющую элементы одного типа данных, — массив.

         Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами). В качестве иллюстрации можно представить шкаф, содержащий множество пронумерованных ящиков (совокупность — «Ящик № 1», «Ящик № 2», «Ящик № 3» и т.д.; «Ящик» — общее имя всех ее элементов). Доступ к содержимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы простого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их элементы.

           Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (а_i) и геометрическая (b_i) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив A (10)», это означает, что даны элементы: a ₁ , a ₂ , …, a ₁₀ . Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

               Пример 4.

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

          Обозначим индекс наибольшего элемента т. Будем считать, что первый элемент массива является наибольшим (т = 1). Сравним поочередно наибольший с остальными элементами массива. Если оказывается, что текущий элемент массива а _i (тот, c которым идет сравнение) больше выбранного нами наибольшего а_т, то считаем его наибольшим (т=i) (рис.10).

         Рассмотрим двумерный массив (шкаф с множеством ящиков, положение которых определяется двумя координатами – по горизонтали и по вертикали). В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса а _ij , первый индекс i определяет номер строки, в которой находится элемент (координата по горизонтали), а второй j – номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и М, определяющими число строк и столбцов соответственно (рис. 11).

          Ввод элементов двумерного массива осуществляется построчно, в свою очередь, ввод каждой строки производится поэлементно, тем самым определяется циклическая конструкция, реализующая вложение циклов. Внешний цикл определяет номер вводимой строки ( i ), внутренний – номер элемента по столбцу ( j ). На рис. 12 представлен алгоритм ввода матрицы A(MxN) .

            Пример 5.

        Задана матрица символов (100х100), представляющая собой карту ночного неба; звездам на карте соответствует символы «*». Определить: сколько звезд на карте?

          Алгоритм решения задачи достаточно прост, необходимо перебрать все элементы матрицы и посчитать, сколько среди них символов «*». Обозначим К переменную – счетчик. На рис 13. представлена блок-схема решения этой задачи.

1. ТО-201 16.11.2020

Алгоритм, его свойства, способы
описания.
Программный принцип работы
компьютера

2.

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

3.

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

Понятность — алгоритм должен быть записан на понятном для
исполнителя языке;
Конечность (результативность) — выполняемый алгоритм
должен приводиться к результату за конечное число шагов;
Дискретность- любой алгоритм должен состоять из конкретных
действий, следующих в определенном порядке;
Массовость- один и тот же алгоритм можно использовать с
различными исходными данными;
Детерминированность (определенность) – каждая команда
алгоритма (предписание, выдаваемое на каждом шагу) должна
быть понятна исполнителю, не оставлять места для ее
неоднозначного толкования и неопределенного исполнения.

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

1. С помощью рисунка (например, процесс подключения монитора);
2. На естественном языке – построчно, каждая команда – с новой
строки (последовательность проявления фотопленки,
последовательность склеивания поверхностей на тюбике с клеем и
т.д.);
3. Использование псевдокода – некоторую систему обозначений и
правил.
Псевдокод
занимает
промежуточное
место
между
естественным и формальным языками. Единого или формального
определения псевдокода не существует, поэтому возможны различные
псевдокоды, отличающиеся набором служебных слов и основных
(базовых) конструкций (например, школьный АЯ).
4. Графическое представление – блок-схема.

6. Блок- схема

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

7.

8. Основные типы алгоритмических структур:

Линейная
Разветвляющаяся
Циклическая

9. Линейный алгоритм

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

10. Разветвляющийся алгоритм

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

11.

Разветвляющийся алгоритм может быть в полной или
неполной форме
Неполная форма
Полная форма

12.

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

13. Циклические алгоритмы

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

14. Типы циклических алгоритмов:

Цикл с предусловием. Перед выполнением цикла проверяется условие
выполнения цикла. Если условие истинно, то цикл выполняется. При
ложности условия цикл заканчивается.
Цикл с постусловием. Условие продолжения цикла проверяется уже после
того, как выполнено тело цикла.
Основное различие: во втором случае цикл выполняется, по крайней мере,
один раз, а в первом – может получиться, что цикл вообще не выполняется.
Цикл с заданным числом повторений, когда указывается количество
повторений цикла. Это так называемые циклы со счетчиками (или
арифметические циклы).
Итерационный цикл используется, когда задана точность вычисления
результата. В таком цикла на каждом шаге (итерации) происходит
постепенное уточнение результата. В большинстве задач вычислительный
процесс, реализующий алгоритм, является комбинированным, т.е. он
содержит разветвления, является циклическим, или итерационным.
.

15.

Отметим разницу между понятиями «команда алгоритма» и
«шаг алгоритма». Команда — это отдельная инструкция в
описании алгоритма, а шаг алгоритма — это отдельное действие,
которое исполнитель выполнит по команде. В циклических
алгоритмах число шагов при выполнении алгоритма может быть
больше, чем число команд в алгоритме, за счет повторного
выполнения одних и тех же команд.
x1
… xn
условие 1
… условие n
формула 1
…
формула n

16.

Вычислить площадь и периметр прямоугольника
начало
Ввести a, b
S = a*b
Р = (a+b)*2
Вывести S, Р
конец

17. Вычисления значения гипотенузы прямоугольного треугольника, если известны значения его катетов

начало
Ввести a, b
с = √ a2+b2
Вывести с
конец

18. Вычислить функцию, заданную в зависимости от значения аргумента

начало
Х <1
Y = 2x+1
Y = 3x — 1
конец

19. Составить блок-схему определения значения функции у = √ х, при х – неотрицательном.

начало
Х >=0
у=√х
не сущ-ет
конец

20. Сумма чисел из промежутка от 5 до 10

начало
S=0
начало
А= 5 : S = 0
а от 5 до 10
a < 11
s=s+a
s=s+a
конец
конец

21. Произведение всех чисел из промежутка от 5 до 10

начало
S=1
а от 5 до 10
s=s*a
конец
начало
А= 5 : S = 1
a < 11
s=s*a
конец

22. Попробуйте сформулировать известную русскую пословицу по ее блок-схеме

Препятствие в виде
возвышенности
да
обход
умный?
нет
восхождение

23. Попробуйте сформулировать известную русскую пословицу по ее блок-схеме

да
нет
Лето?
да
Сани
Телега
Зима?
нет

24. Попробуйте сформулировать известную русскую пословицу по ее блок-схеме

I=0
I=I+1
I 7
нет
да
Отмерь
Отрежь

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

начало
ввод числа
да
нет
> 10
-4
да
+1
< 15
+3
нет
да
-2
-6
вывод числа
конец
>8
нет
-7

26. Составьте блок-схему по высказыванию

«Если мысль нельзя выразить
простыми словами, значит, она
ничтожна и надо ее отбросить.»

27. Составить блок-схему к задаче: В корзине имеются белые и черные шары. Нужно белые шары положить в белую коробку, а черные – в

черную.

28. Определить значение переменной a после выполнения фрагмента алгоритма

а:= 16
b:= 2
да
b:= 32
нет
b:= b*2
a:= a+2

29. Определить значение переменных х и у после выполнения фрагмента алгоритма

x:= 5
y:= 10
нет
x <10
да
да
x<y
нет
x:= x-5
y:= y+5
x:= x+1
y:= y-1

30. Определить значение переменной х после выполнения фрагмента алгоритма

х:= 136
у:= 72
да
х=у
нет
да
x>y
x:= x-y
нет
y:= y-x

31.

Определить значение переменной n после
выполнения фрагмента алгоритма
n:= 10
m:= 12
да
m<6
нет
m:= m – 2
n:= n*2

32.

Определить значения целочисленных переменных х и у
после выполнения фрагмента алгоритма
x:= 15
y:= 35
нет
x < 30
да
да
x>y
нет
x:= x+10
y:= y-10
x:= x-5
y:= y+5

33. Программный принцип работы компьютера

Компьютер – двуединая система, состоящая из
аппаратной части (технических устройств) и
информационной
части
(программного
обеспечения):
КОМПЬЮТЕР
АППАРАТУРА
= (hardware)
ПРОГРАММНОЕ
+ ОБЕСПЕЧЕНИЕ
(software)

34. Программное обеспечение (ПО)

ПО – это совокупность программ, хранящихся на
устройствах долговременной памяти компьютера и
предназначенных для массового использования.
Использование компьютера человеком происходит
по схеме:
ЗАДАЧА
ВЫБОР И
ИНИЦИАЛИЗАЦИЯ
ПРОГРАММЫ
РАБОТА

35. Программы и данные

Программное обеспечение – это не только собственно
программы, но и данные, с которыми работают эти
программы.
Данные и программы хранятся на дисках, в отдельных
файлах.
Часто объем данных во много раз превышает размер
программ.

36.

Программное обеспечение (ПО)
Системное ПО
Операционные системы:
— Однозадачные (MS DOS )
— Многозадачные (Unix,
Windows и др. )
Сервисные программы
Прикладное ПО
Текстовые редакторы
(MS Word, WordPad и др. )
Графические редакторы
(Adobe Rhotoshop, Corel
Draw, MS Paint и др. )
Электронные таблицы
(MS Excel и др. )
Среды разработки
Интегрированные
(Visual Studio, Eclipse,
XCode, RAD )
Поддерживающие только
конкретный язык
программирования
(Borland C++, DrJava,
Delphi )

37. Этапы решения задачи на компьютере

Работа по решению любой задачи с использованием компьютера
делится на следующие этапы:
1.Постановка задачи.
2.Формализация задачи (формальное математическое описание
алгоритма).
3.Построение алгоритма.
4.Составление программы на языке программирования.
5.Отладка и тестирование программы.
6.Проведение расчетов и анализ полученных результатов.
Часто эту последовательность называют технологической
цепочкой решения задачи на компьютере.

38.

Вся наша жизнь – это алгоритм
сложной структуры.
Надо стремиться к тому, чтобы
каждое наше действие было
обдуманным и приводило к
правильному, достойному
результату!

План урока:

Алгоритмы, которыми мы пользуемся

Исполнители, система команд исполнителя (СКИ)

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

Классификация алгоритмов

Виды записи алгоритмов

Пример алгоритма на Turbo Pascal

Начнем урок с простой задачи. Что нужно сделать, если хочется выпить чая?

Один человек сразу включает чайник, потом начинает искать чашки, заварку, сахар.

Второй действует согласно плану:

1. Проверить наличие заварки и сахара.
2. Если их нет, купить.
3. Если все есть, найти чашку, проверить ее чистоту.
4. Поставить чайник греться.
5. Ополоснуть чашку кипятком.
6. Насыпать заварку, залить кипятком.
7. Добавить сахар.

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

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

Алгоритмы, которыми мы пользуемся

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

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

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

• пошаговые кулинарные рецепты;
• мастер-классы по рукоделию;
• инструкции к оборудованию;
• план действия при ЧП.

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

Пример в виде красочной инструкции и сухой пошаговой рекомендации:

Работа за компьюетром                             Инструкция по настройке 

А в информатике без них не обойтись – именно на алгоритмах основано программирование.

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

Если действия однотипные, например, «набрать ковш воды и вылить» или «взять яблоко и проверить, есть ли червоточина», то его записывают 1 раз и повторяют конечное число раз.

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

Исполнители, система команд исполнителя (СКИ)

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

Исполнитель – субъект/объект, который может выполнить команды данного алгоритма.

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

Компьютер (ПК) – автоматизированный исполнитель команд. Алгоритмы программ для ПК пишут на языках программирования (С++, Basic, Pascal, Delphi, Ассемблер, Фортран).

Для каждого типа и уровня исполнителей существует своя система команд исполнителя (СКИ).

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

Независимо от того, разрабатывается ход приготовления яичницы или запуска космического корабля, они должны обладать 5 основными свойствами:

1. Детерминированность – все описания должны быть однозначными, понятными.

Понятность – процедура должна быть на языке, который понятен той категории исполнителей, для которых она пишется.

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

1. Дискретность – строгие команды, идущие в определенной последовательности.

Точность – команды должны быть конкретными, понятными, однозначными.

Пример непонятного и неточного задания мы помним из сказки: “Пойди туда, не знаю куда. Принеси то, не знаю что”.

1. Массовость – план действия подходит под аналогичные ситуации с разными исходными данными. То есть инструкция по приготовлению бутерброда с колбасой позволяет брать разный хлеб и мясопродукт или заменить его сыром.
2. Результативность – выполнение команд должно приводить к результату. Не должно быть ошибок. При использовании допустимых исходных параметров алгоритм должен давать правильный результат всегда.
3. Конечность – каждая команда и процедура в целом должны выполняться за конечное число шагов, то есть он не должен быть бесконечным, зацикленным.

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

Мытье рук:

• включить воду;
• намочить руки и мыло;
• выключить воду;
• намылить руки;
• включить воду.

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

Классификация алгоритмов

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

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

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

Чаще используют алгоритмы повторения с условием, так как идеальные условия встречаются редко.

Источник

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

Запишем схему линейного алгоритма (покупки чая):

1. Взять пакет и кошелек с деньгами.
2. Зайти в любой продуктовый маркет.
3. Выбрать нужный сорт чая.
4. Заплатить за товар.
5. Чай положить в пакет, пойти домой.

Для многих задач важно выполнение определенного условия.

Пример алгоритма ветвления – если нужного сорта нет, то процесс покупки чая усложняется:

1. Взять пакет и кошелек с деньгами.
2. Зайти в любой продуктовый маркет.
3. Посмотреть, есть ли чай «Элитный».
4. Если да, то узнать цену, отдать деньги.
5. Покупку положить в пакет, пойти домой.
6. Если нет, найти сорт «Белый, китайский», узнать цену, отдать деньги.
7. Упаковку положить в пакет, вернуться домой.
8. Если нет ни «Элитного», ни «Белого, китайского», то пойти в другой магазин и повторить все с пункта №3.

Эту же задачу можно описать при помощи циклического алгоритма, если есть повторение определенной операции.

Данный пример включает в себя ветвление «если» и повторение команд:

1. Взять пакет и кошелек с деньгами.
2. Зайти в любой продуктовый маркет.
3. Взять коробку с чаем в руки, посмотреть, это сорт «Элитный».
4. Если да, то узнать цену, заплатить.
5. Забрать покупку, вернуться домой.
6. Если нет, взять следующую упаковку и повторить пункты 3-6.
7. Если весь чай перебран, но «Элитного» нет, то пойти в другой магазин и повторить все с пункта №3.

Цикличные инструкции следует писать так, чтобы не было вечного цикла или зацикливания – бесконечного повторения операции без достижения результата.

Виды записи алгоритмов

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

Легче воспринимается такой план, если его дополнять картинками.

Источник

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

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

Блок-схема – графическая форма представления алгоритмов при помощи геометрических объектов и стрелок.

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

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

Пример алгоритма на Turbo Pascal

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

Для примера попробуем программирование линейных алгоритмов при помощи языка Turbo Pascal.

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

Меню Пуск → Все программы → Turbo Pascal

На экране монитора появится оболочка, которая позволяет освоить азы программирования и даже реализовывать непростые проекты.

Оболочка разработана под DOS, что объясняет необычную реализацию интерфейса.

Пишем самый простой алгоритм программы для выведения на экран слов приветствия.

На латинской раскладке набираем в синем окне такие команды:

program Test;

begin

write(‘Доброе утро!’);

end.

Учитываем важные моменты при использовании языка Турбо Паскаль:

• все пишется латинскими буквами;
• регистр неважен;
• каждая строка – команда, в конце строки ставится Enter и «;»;
• после «end» должна быть «.».

Как видим, в программе есть свои слова-команды, как в письменных алгоритмах. Слово program – как заголовок, название объекта, а тest – непосредственно название программы.

Началом является команда begin, end – окончанием, а между ними стоят операторы или команды-действия («write» – напиши на экране). А текст, который нужно выводить на экране берется в скобки и ’….’.

Чтобы запустить программу, следует нажать Ctrl+F9 или набор команд Run Run.

Если нет ошибок в командах, появится такой результат:

Чтобы выйти обратно, можно нажать любую кнопку клавиатуры.

При каждом запуске будет новая запись, на той же строке. Если заменить write на writeln, то текст будет выводиться в новой строчке:

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

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