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

Информатика и ИКТ. 9 класс. Основы алгоритмизации.

Урок № 10

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

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

Ход урока:

1. Организационный момент

2. Актуализация опорных знаний (опрос по теме прошлого урока)

1. Дайте определение «алгоритм»?

2. Происхождение понятия «алгоритм»?

3. Какие виды алгоритмов существуют?

1. Изучение нового материала:

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

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

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

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

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

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

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

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

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

• выделении законченных частей вычислительного процесса;

• формальной записи каждого из них;

• назначении определенного порядка выполнения выделенных частей;

• проверки правильности выбранного алгоритма по реализации заданного метода вычислений.

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

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

• словесное описание;

• формульно-словесное описание;

• псевдокод;

• графический способ (блок-схема);

• программа (способ описания с помощью языков программирования).

Словесное описание

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

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

Пример 1.

Алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

1. задать два числа;

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

3. определить большее из чисел;

4. заменить большее из чисел разностью большего и меньшего из чисел;

5. повторить алгоритм с п. 2.

Пример 2.

Алгоритм выполнения домашнего задания по математике.

1. открыть дневник;

2. посмотреть, что задано;

3. взять учебник и тетрадь по предмету;

4. прочитать параграф и выполнить письменные упражнения;

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

6. если ответы совпадают, закрыть тетрадь и учебник, если нет – повторить алгоритм с п. 4.

Формульно-словесный способ

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

Пример 3.

Алгоритм вычисления следующего выражения: у=2∙а–(х+6).

1. ввести значения а и х;

2. найти сумму (х+6);

3. найти произведение (2∙а);

4. вычислить y как разность y=2∙a–(x+6);

5. вывести у как результат вычисления выражения.

Пример 4.

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

1. Дано: высота треугольника AH=2 см, основание треугольника BC= 5 см.

2. Найти: площадь S ∆ABC.

3. Решение: Площадь треугольника находится по формуле

4. Подставим данные задачи:

5. Результат:

Псевдокод

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

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

Пример 5.

Алгоритм сложения двух чисел.

Псевдокод:

1. Ввод двух чисел a и b.

2. Вычисление суммы S=a+b.

3. Вывод S.

4. Конец.

Пример 6.

Алгоритм заполнения зачетной ведомости группы из 20 студентов (i – номер студента).

Псевдокод

начало цикла

для

i от 1 до 20 с шагом 1

повторять:

1.1. ввести фамилию студента

1.2. поставить оценку.

конец цикла (кц)

вывод ведомости

Графическая запись

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

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

• концентрация внимания на структуре алгоритма;

• использование принципа блочности при коллективном решении сложной задачи;

• преобразование алгоритма методом укрупнения (сведения к единому блоку) или детализации (разбиения на ряд блоков);

• быстрая проверка разработанного алгоритма.

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

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

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

Средства графического изображения алгоритмов

Наименование

Символ

Выполняемые действия

Терминатор (пуск-остановка)

Обозначает начало и конец алгоритма

Данные (ввод-вывод)

Ввод и вывод данных

Процесс

Вычислительные действия

Решение

Наличие условия в алгоритме

Граница цикла

Наличие цикла в алгоритме

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

Наличие подпрограммы

Соединитель

Разрыв алгоритма (соединительные блоки)

Комментарий

———

Внесение комментариев

Терминатор (пуск-остановка). Элемент отображает вход из внешней среды или выход из нее (наиболее частое применение − начало и конец алгоритма). Внутри фигуры записывается соответствующее действие − начало/конец.

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

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

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

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

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

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

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

Соответствующие соединительные символы должны иметь одно (при том уникальное) обозначение.

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

Пример 7.

Алгоритм сложения двух чисел.

Пример 8

Алгоритм совершения покупок в магазине.

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

Программа

Программа − это алгоритм, записанный в виде последовательности команд, понятных ЭВМ (машинных команд). При записи алгоритмов в виде программ для ЭВМ используются языки программирования — системы кодирования предписаний и правила их использования. Такие языки являются искусственными языками со строго определенными синтаксисом и пунктуацией. Они не допускают свободного толкования для своих конструкций, как это характерно для естественного языка. Существует большое количество языков программирования, предназначенных для решения прикладных задач.

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

Пример 9.

Алгоритм сложения двух чисел. Программа, записанная на языке Qbasic:

Rem Вычисление суммы двух чисел

Input «Введите число a»; a

Input «Введите число b»; b

Print «Сумма a+b=»; a+b

End

1. Закрепление материала.

1. Составить алгоритм вычисления значения функции y=7x+5 при любом значении x.

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

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

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

1. Домашнее задание.

Записи в тетради, повторить понятие «алгоритма».

Беляев Д. М. МАОУ лицей № 21 г. Тамбов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Картинка с сайта: moodle.kstu.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

         Пример 1.

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

         Псевдокод:

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

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

Вывод S.

Конец.

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

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

Картинка с сайта: moodle.kstu.ru

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

             Пример 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 двумя способами: с помощью условного блока а и с помощью блока границы цикла б. Особенностью цикла с предусловием является то, что если изначально условное выражение ложно, то тело цикла не выполнится ни разу.

Картинка с сайта: moodle.kstu.ru

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

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

Картинка с сайта: moodle.kstu.ru

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

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

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

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

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

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

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

         Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от О до 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.

Картинка с сайта: moodle.kstu.ru

               Пример 4.

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

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

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

Картинка с сайта: moodle.kstu.ru

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

            Пример 5.

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

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

Источник статьи

Автор24
— учеба по твоим правилам

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

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

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

Процесс разработки алгоритма — достаточно сложный и трудоемкий.

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

Цель же, в свою очередь, является достижением желаемого результата.

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

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

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

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

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

Понятие алгоритма в теорию и практику обучения вошло в конце $50$-х годов прошлого столетия в связи с развитием программированного обучения и применением обучающимися машин.

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

Существуют различные способы описания алгоритмов. Приведем основные из них:

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

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

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

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

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

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

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

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

1. Наличие ввода исходных данных.
2. Наличие вывода результата выполнения.
3. Однозначность, так как компьютеру понятны лишь однозначные инструкции.
4. Общность, в соответствии с которой алгоритм может использоваться не только для решения одной задачи, но и целого класса задач.
5. Корректность, согласно которой при выполнении алгоритма должно быть всегда правильное решение задачи.
6. Конечность означает, что решение задачи необходимо получить за конечное число шагов.
7. Эффективность означает, что для решения задачи необходимо использовать ограниченные ресурсы компьютера (объем оперативной памяти, процессорное время и т. д.).

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

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

Блок-схемы

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

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

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

Операторный блок (блок действия) содержит команды обработки данных.

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

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

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

Картинка с сайта: spravochnick.ru

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

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

Давайте
составим таблицу, в которой будет 2 столбца и 2 строки. В первой строке первого
столбца запишем: текстовая форма записи алгоритма.

Во
второй строке первого столбца запишем алгоритм, как мы делали это на прошлом
уроке, но внесём и некоторые изменения.

Все
алгоритмы начинаются с команды «начало», её мы и запишем первой. Затем
записываем уже известный нам алгоритм. Команда «начало» не нумеруется.

Первое
действие: измерить длину стороны a треугольника.

Второе
действие: измерить длину стороны b треугольника.

Третье
действие: измерить длину стороны c треугольника.

Четвёртое
действие: найти сумму длин всех сторон треугольника.

Добавим
ещё одно действие алгоритма.

Пятое
действие: записать результат на носителе.

Все
алгоритмы заканчиваются командой «конец». Его и пишем самым последним. Как и
«начало», команда «конец» тоже не нумеруется.

Вот
мы и создали текстовую форму записи алгоритма.

В
первой строке второго столбца запишем: графическая форма записи алгоритма
(блок-схема).

Но
прежде, чем её записать, надо разобраться, что такое блок-схема.

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

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

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

Блок
для команды выполнения действия изображается в виде прямоугольника. В нём мы
записываем, например, найти произведение сторон вычислить сумму 2 чисел, залить
в чайник воду.

Есть
ещё и блок с командой проверки условия. Он изображается в виде ромба, в
нём записывается условие, например, чётное ли число, если в чайнике вода. Из
блока выходят вправо и влево две стрелки, которые подписаны «Да» или «Нет».
Если условие выполняется, то следует перейти к следующему блоку с командой по
стрелке перехода с названием «Да», если условие не выполняется, то переходим к
следующему блоку с командой по стрелке перехода с названием «Нет».

Ну
что же, перейдём к графической форме записи алгоритма. Смотрим на текстовую
форму и выбираем, какой блок нам использовать.

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

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

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

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

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

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

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

Как
вы думаете, есть ли ещё какие-то виды алгоритмов?

Чтобы
ответить на этот вопрос, рассмотрим ещё одну задачу.

Петя
предложил Алисе загадать двузначное число. И попросил: «Если это двузначное
число заканчивается на цифру 5, то прибавь к нему 10 и назови число. Если
задуманное число не заканчивается на цифру 5, то из него вычти 3 и назови
число».

Вы
заметили, что в условии этой задачи есть такие слова, как «если…, то …»?

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

В
чём же особенность такого алгоритма?

Дело
в том, что для того, чтобы решить такую задачу, необходимо сделать выбор:

·   
Если
задуманное число заканчивается на цифру 5, то необходимо выполнить одно
действие.

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

Давайте
представим описание последовательности действий Алисы в форме блок-схемы.

Изображаем
блок «Начало». От него идёт стрелка перехода вниз к блоку ввода данных «Задумай
двузначное число» в форме параллелограмма. От этого блока идёт стрелка перехода
к блоку с командой проверки условия «Заканчивается ли число на цифру 5». Он
изображается в виде ромба. От него влево идёт стрелка перехода с пометкой «Да»
к блоку выполнения действия «Прибавь 10». И от этого блока вниз идёт стрелка
перехода к блоку вывода данных «Назови результат сложения» в форме
параллелограмма. Вернёмся к блоку с командой проверки условия. Вправо от него
идёт стрелка перехода с пометкой «Нет» к блоку выполнения действия «Вычти 3». И
от этого блока вниз идёт стрелка перехода к блоку вывода данных «Назови
результат вычитания» в форме параллелограмма. Теперь от блоков вывода данных
ведём вниз линии, которые переходят в общую стрелку перехода к блоку «Конец».

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

Запомните!

Алгоритм
с ветвлением содержит блок выбора, в котором есть условие, один вход и два
выхода: «Да» и «Нет».

Давайте
проверим, как хорошо вы усвоили новую тему. Выполните следующие задания.

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

Проверьте,
правильно ли вы выполнили задание.

Второе
задание. Вставьте пропущенные слова.

Справились?
Проверьте, правильно ли вы выполнили задание.

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

Существует
две формы записи алгоритмов: текстовая и графическая в виде
блок-схемы.

Блок-схема
– это описание команд (шагов, инструкций), составляющих алгоритм.

Текстовая
форма даёт более подробную информацию, а графическая – более наглядную.

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

Алгоритм
с ветвлением – это алгоритм, который содержит блок с
условием, один вход и два выхода: «Да» и «Нет».

Ну а мы с вами прощаемся. До свидания. До новых встреч.