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

АННОТАЦИЯ

Учебное пособие составлено в соответствии с требованиями стандартов ФГОС ТОП–50 для специальности 09.02.07 «Информационные системы и программирование», одобрено цикловой методической комиссией «Программное обеспечение информационных технологий» БПОУ «Омавиат».

Учебное пособие предназначено для студентов специальности 09.02.07 «Информационные системы и программирование», изучающих дисциплину «Основы алгоритмизации и программирования».

Дисциплина «Основы алгоритмизации и программирования» входит в общепрофессиональный цикл программы подготовки специалистов среднего звена по специальности 09.02.07 «Информационные системы и программирование» в соответствии с ФГОС СПО. Дисциплина базируется на знаниях, умениях, сформированных в ходе изучения предшествующих дисциплин: ЕН.01 Элементы высшей математики; ОП.01 Операционные системы и среды; ОП.03 Информационные технологии.

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

Целью освоения Раздела «Основы алгоритмизации» данной дисциплины является приобретение обучающимся теоретических основ и практических умений разработки алгоритмов и оценки их эффективности.

В состав раздела входят три основных темы:

- Тема 1. Основные модели алгоритмов;

- Тема 2. Методы построения базовых алгоритмов;

- Тема 3. Методы вычисления сложности алгоритмов.

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

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

Тема 3 посвящена вопросам эффективности алгоритмов. Акцент сделан на рассмотрение особенностей временной эффективности алгоритмов. Рассмотрены методы вычисления сложности алгоритмов на конкретных примерах.

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

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

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

В результате освоения раздела «Основы алгоритмизации» дисциплины «Основы алгоритмизации и программирование» обучающийся должен

уметь:

- разрабатывать алгоритмы для конкретных задач;

- использовать программы для графического отображения алгоритмов;

- определять сложность работы алгоритмов;

знать:

- основные модели алгоритмов;

- методы построения алгоритмов;

- методы вычисления сложности работы алгоритмов.

Также изучение раздела дисциплины должно способствовать формированию следующих общих и профессиональных компетенций:

профессиональные компетенции:

- ПК.1.1 - Формировать алгоритмы разработки программных модулей в соответствии с техническим заданием;

общие компетенции:

- ОК1 - Выбирать способы решения задач профессиональной деятельности, применительно к различным контекстам;

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

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

- ОК9 - Использовать информационные технологии в профессиональной деятельности;

- ОК10 - Пользоваться профессиональной документацией на государственном и иностранном языке.

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

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

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

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

1. РАЗДЕЛ «ОСНОВЫ АЛГОРИТМИЗАЦИИ». Тема «Основные модели алгоритмов»

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

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

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

Примечание. Узбекский математик Аль-Хорезми еще в IX в. разработал простейшие арифметические алгоритм, его имя и легло в основу слова «алгоритм».

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

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

восприятие информации

Постановка задачи

2. Построение математической модели

кодирование

Разработка алгоритма (алгоритмизация)

обработка

Составление программы (программирование)

5. Реализация программы на компьютере

передача результатов

Анализ (интерпретация) результатов

Рис.1.1 Процесс обработки информации на компьютере

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

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

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

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

1. Понятность. Каждая команда алгоритма должна входить в систему команд исполнителя.

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

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

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

5. Конечность и результативность. Алгоритм должен приводить к результату за конечное число шагов.

Пример 1.1 Рассмотрим в качестве примера пошаговую инструкцию по отправке SMS с сотового телефона.

1) Взять телефон.

2) Если телефон выключен, то включить его.

3) Если телефон заблокирован, то разблокировать.

4) Зайти в меню «Сообщения».

5) Нажать на кнопку «Создать новое сообщение».

6) Указать получателя.

7) Ввести текст сообщения.

8) Нажать на кнопку «Отправить сообщение».

Проанализируем, является ли данная инструкция алгоритмом?

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

Перечислим некоторые способы описания алгоритмов:

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

- Операторные схемы;

- Графическое описание;

- Псевдокод.

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

Графическое описание (блок-схема) – это способ представления алгоритма c помощью геометрических фигур, называющихся блоками. Этот способ описания алгоритма (блок - схема) чаще всего используется при разработке алгоритмов. К основным достоинствам блок-схем можно отнести их визуальную наглядность, что упрощает чтение и понимание логики алгоритма.

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

Основные правила использования блоков в схемах алгоритмов регламентирует ГОСТ 19.701-90 “Схемы алгоритмов программ, данных и систем”.

Основные блоки схем алгоритмов, регламентируемые стандартом, представлены в таблице 1.1

Таблица 1.1 Основные блоки схем алгоритмов

Графический блок	Наименование (из стандарта)	Назначение	Пример
	Терминатор	Начало и конец любого алгоритма
	Данные	В блоке перечисляются данные для ввода или вывода
	Процесс	Одна или несколько (ГОСТ не запрещает) вычислительных операций (в том числе и присваивания)
	Предопределен ный процесс	Вызов внешних процедур и функций
	Соединитель	Указание связи прерванных линий между потоками информации в пределах одного листа
	Комментарий	Подробности любых действий
	Решение	Выбор одного из направлений выполнения алгоритма в зависимости от некоторого условия. Он имеет один вход и несколько подписанных выходов. В случае если блок имеет 2 выхода, они подписываются как да или нет. Если из блока выходит большее число линий (выбор одного из многих), внутри него записывается имя переменной, а на выходящих дугах – значения (диапазон значений) этой переменной
	Подготовка	Блок задает подготовительные операции (инициализация, условие, модификация) для дальнейшего повторения команды или группы команд. Используется обычно для задания циклов со счетчиком
	Границы цикла	Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип цикла: с предусловием (условие в верхнем блоке) или с постусловием (условие в нижнем блоке)

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

Например, алгоритм из примера 1 в виде операторной схемы будет выглядеть так: A₁ Р₂ ↑⁴A₃ Р₄ ↑⁶А₅ A₆A₇ А₈ А₉ А₁₀

Запись Ai↑^mозначает, что после выполнения вычислительного оператора Ai будет выполняться оператор с меткой m. Запись Pi↑^m означает, что после выполнения условного оператора Pi, в случае истинности условия, выполняется следующий оператор, в противном случае осуществляется переход на оператор с меткой m.

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

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

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

Рис.1.2Линейная структура Рис.1.3 Ветвление Рис.1.4 Цикл

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

В таблице 1.2 приведены варианты описания алгоритма из примера 1.1, используя рассмотренные способы описания алгоритмов.

Таблица 1.2 Варианты описания алгоритма

Словесно-формульное описание	Псевдокод	Блок-схема
1) Взять телефон. 2) Если телефон выключен, то включить его. 3) Если телефон заблокирован, то разблокировать. 4) Зайти в меню «Сообщения». 5) Нажать на кнопку «Создать новое сообщение». 6) Указать получателя. 7) Ввести текст сообщения. 8) Нажать на кнопку «Отправить сообщение».	алг Отправка СМС() нач Взять телефон; Если (телефон выключен) то включить телефон; конецЕсли Если (телефон заблокирован) то разблокировать телефон; конецЕсли Зайти в меню «Сообщения»; Нажать на кнопку «Создать новое сообщение»; Указать получателя; Ввести текст сообщения; Нажать на кнопку «Отправить сообщение»; кон

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

Псевдокод

Блок-схема

1) Взять телефон.

2) Если телефон выключен, то включить его.

3) Если телефон заблокирован, то разблокировать.

4) Зайти в меню «Сообщения».

5) Нажать на кнопку «Создать новое сообщение».

6) Указать получателя.

7) Ввести текст сообщения.

8) Нажать на кнопку «Отправить сообщение».

алг Отправка СМС()

нач

Взять телефон;

Если (телефон выключен)

то включить телефон;

конецЕсли

Если (телефон заблокирован)

то разблокировать телефон;

конецЕсли

Зайти в меню «Сообщения»;

Нажать на кнопку «Создать

новое сообщение»;

Указать получателя;

Ввести текст сообщения;

Нажать на кнопку «Отправить сообщение»;

кон

И наконец, сформулируем основные принципы проектирования алгоритмов:

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

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

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

Контрольные вопросы для самоанализа материала.

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

- алгоритм

- алгоритмизация

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

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

- принципы проектирования алгоритмов

- виды алгоритмов

2. Приведите два примера алгоритмов, с которыми вы сталкивались в жизни. Опишите один из них словесно. Докажите, что представленная вами последовательность действий удовлетворяет требованиям, предъявляемым к алгоритмам.

3. Сравните способы представления алгоритмов. Основания для сравнения выберите сами, например, удобство применения, простота перевода в программный код и другие. Наиболее принципиальные позиции зафиксируйте в таблице.

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

Выскажите и аргументируйте свое мнение по поводу наиболее приемлемого для вас способа описания алгоритма:

1) ______________________________________________________________________________________________________________________________________________

2) ______________________________________________________________________________________________________________________________________________

Линейные и разветвленные алгоритмы

Рассмотрим основные виды алгоритмов.

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

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

На рис. 1.5 показан шаблон блок-схемы линейного алгоритма. Блок-схема линейного алгоритма содержит только блоки «Процесс» и не использует блоки «Решение» или блоки цикла.

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

Рассмотрим разработку блок-схем линейных алгоритмов на конкретных примерах.

Пример 1.2

Даны два значения х и у. Требуется обменять их местами, т.е. новое значение х должно стать равно старому значению у, и наоборот.

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

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

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

Решение задачи распадается на три шага:

1) Ввод исходных данных;

2) Обмен местами:

- Создание копии значения х в переменной copy;

- Замена х на значение у;

- Замена у на значение х, взятое из копии;

3) Вывод результатов.

Алгоритм решения является линейным, так как не содержит условий и повторений.

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

Рис. 1.6 Блок-схема алгоритма обмена местами двух значений.

Пример 1.3

Дано значение радиуса круга R. Требуется вычислить площадь круга, используя формулу S=πR².

Решение.

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

Решение задачи распадается на три шага:

1) Ввод исходных данных;

2) Вычисление площади;

3) Вывод результатов.

В таблице 1.3 для сравнения представлены два способа описания алгоритма: блок-схема и псевдокод.

Разветвленным называется алгоритм, который имеет несколько вариантов выполнения. Вариант выполнения называется ветвью алгоритма.

Разветвленный алгоритм содержит одно или несколько логический условий и имеет несколько ветвей обработки.

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

Таблица 1.3 Алгоритм вычисления площади круга

Псевдокод	Блок-схема
алг ПлощадьКруга( ) нач Ввод R; Pi=3.14; S= PiRR; Вывод S; кон

Псевдокод

Блок-схема

алг ПлощадьКруга( )

нач

Ввод R;

Pi=3.14;

S= Pi*R*R;

Вывод S;

кон

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

1) Полное Ветвление;

2) Неполное Ветвление;

3) Выбор-Иначе.

Порядок выполнения Полного и Неполного Ветвления:

- Проверка условия, результат проверки значения true или false;

- Если true, то выполняется ветвь Да;

- Если false, то выполняется ветвь Нет;

- В случае, когда Неполное ветвление, ветвь Нет не содержит никаких действий.

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

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

Блок-схема разветвленного алгоритма всегда содержит, по меньшей мере, один блок «Решение». В таблице 1.4 представлены блок-схемы и псевдокод разветвленных структур.

Таблица 1.4. Варианты разветвленной структуры

Название конструкции	Псевдокод	Блок-схема
Полное ветвление	Если условие То действие 1; Иначе действие 2; Все;
Неполное ветвление	Если условие То действие 1; Все;
Выбор - иначе	Выбор При выражение= значение_1: действие 1; При выражение= значение_2: действие 2; ….. При выражение= значение_n: действие n; Иначе действие n+1; все

Пример 1.4

Даны два действительных числа х и у. Найти максимальное из этих чисел.

Решение.

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

Решение задачи распадается на следующие шаги:

- Ввод исходных данных;

- Проверка условия (х>у);

- Если условие истинно, то в переменную max записывается х, иначе у;

- Вывод результата max.

В таблице 1.5 для сравнения представлены два способа описания алгоритма: блок-схема и псевдокод.

Таблица 1.5 Алгоритм нахождения максимального их двух чисел

Псевдокод	Блок-схема
алг Максимум( ) нач Ввод х, у; Если (х>y) То max=x; Иначе max=y; Все; Вывод max; кон

Псевдокод

Блок-схема

алг Максимум( )

нач

Ввод х, у;

Если (х>y)

То max=x;

Иначе max=y;

Все;

Вывод max;

кон

Пример 1.5

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

Решение.

Алгоритм решения задачи состоит в вычислении у по разным формулам, в зависимости от аргумента х. Если аргумент больше нуля, то у=cos(x). В противном случае, возможны два варианта: либо x<0, либо x=0. Поэтому, необходимо проверить хотя бы одно из этих условий, например x<0. Таким образом, в данном случае тип алгоритма – разветвленный с проверкой двух условий. Чтобы алгоритм был более компактным, удобнее сначала проверить вырожденный случай (х=0) и вывести сообщение об ошибке, затем проверить одно из заданных условий. Такая конструкция называется вложенные условия, так как в ветвь Иначе первого условия вложено другое условие.

Решение задачи распадается на следующие шаги:

- Ввод аргумента функции x;

- Проверка первого условия (х=0);

- Если условие истинно, то выводим сообщение об ошибке;

- Иначе Проверка второго условия (х>0);

- Если второе условие истинно, то вычисляем у по формуле y=cos(x);

- Если второе условие ложно, то вычисляем у по формуле y=sin(x);

- Вывод результата y.

В таблице 1.6 для сравнения представлены два способа описания алгоритма: блок-схема и псевдокод.

Таблица 1.6 Алгоритм вычисления значения функции

Псевдокод	Блок-схема
алг Функция( ) нач Ввод х; Если (х=0) То Вывод «х не определено»; Иначе Если (х>0) То y= cos(x); Иначе y=sin(x); Все; Вывод y; Все; кон

Псевдокод

Блок-схема

алг Функция( )

нач

Ввод х;

Если (х=0)

То Вывод «х не определено»;

Иначе Если (х>0)

То y= cos(x);

Иначе y=sin(x);

Все;

Вывод y;

Все;

кон

Пример 1.6

Дано действительное число х и натуральное у (целое, большее нуля). Также пользователь задает одну из арифметических операций в виде знака: ‘+’, ’-‘, ’*’, ’/’. Вычислить результат заданной арифметической операции над числами х и у.

Решение.

Алгоритм решения задачи состоит в проверке того, какая арифметическая операция задана. Для этого надо сравнить заданный пользователем знак операции поочередно со всеми известными знаками: ‘+’, ’-‘, ’*’, ’/’. Это проверка нескольких альтернативных условий, так как истинным может быть только одно. Проверка альтернативных условий реализуется с помощью алгоритмической конструкции Выбор – иначе, при этом, ветвь Иначе может и отсутствовать. После попадания на одну из ветвей Выбора, другие условия уже не проверяются, мы как бы «проваливаемся» на оператор, следующий за Выбором. Таким образом, в данном случае тип алгоритма – разветвленный, с проверкой нескольких условий.

Решение задачи распадается на следующие шаги:

- Ввод чисел x и у;

- Ввод знака операции с;

- Вычисляем выражение с;

- При равенстве с=‘+’, вычисляем сумму rez=x+y; выводим результат;

- При равенстве с=‘-’, вычисляем разность rez=x-y; выводим результат;

- При равенстве с=‘*’, вычисляем произведение rez=x*y; выводим результат;

- При равенстве с=‘/’, вычисляем частное rez=x/y; выводим результат;

- Иначе выводим сообщение об ошибке ввода;

В таблице 1.7 для сравнения представлены два способа описания алгоритма: блок-схема и псевдокод.

Таблица 1.7 Алгоритм вычисления результата арифметической операции

Псевдокод	Блок-схема
алг Арифметическая_операция( ) нач Ввод х,у; Ввод с; Выбор При с=‘+’: rez=x+y; Вывод rez ; При с=‘-’: rez=x-y; Вывод rez ; При *с=‘’: rez=xy; Вывод rez ;* При с=‘/’: rez=x/y; Вывод rez ; Иначе Вывод «Ошибка»; все кон

Псевдокод

Блок-схема

алг Арифметическая_операция( )

нач

Ввод х,у;

Ввод с;

Выбор

При с=‘+’: rez=x+y; Вывод rez ;

При с=‘-’: rez=x-y; Вывод rez ;

При с=‘*’: rez=x*y; Вывод rez ;

При с=‘/’: rez=x/y; Вывод rez ;

Иначе Вывод «Ошибка»;

все

кон

Контрольные вопросы для самоанализа материала.

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

- Разветвленный алгоритм

- Блок-схема

- Блок «Процесс»

- Ветвь алгоритма

- Блок «Решение»

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

- Алгоритмическая конструкция «Неполное ветвление»

- Алгоритмическая конструкция «Выбор - Иначе»

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

Основания для сравнения	Виды алгоритмов
Основания для сравнения	ра линейный	разветвленный

3. Проанализируйте блок-схему предложенного алгоритма (рис. 1. 7). Перечислите используемые алгоритмические конструкции и укажите их назначение. Определите результат выполнения алгоритма при различных исходных данных. Составьте краткую аннотацию к алгоритму (по пунктам):

- Назначение алгоритма;

- Краткая характеристика (основная идея);

- Названия алгоритмических конструкций и цель их использования;

- Вид алгоритма;

- Диапазон входных данных;

- Результат выполнения алгоритма при N=6, N=55, N=56;

- Область применения.

Рис. 1.7 Блок-схема алгоритма

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

Продолжим рассмотрение основных видов алгоритмов.

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

Примеры циклических алгоритмов очень часто встречаются в жизни:

- Пока не закончится грязная посуда, продолжать мыть тарелки;

- Пока не закончится книга, продолжать читать страницы;

- Пока не откроется дверь, продолжать подбирать ключи;

- Пока не появится зеленый сигнал светофора, водителю остановиться и ждать и др.

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

Существует несколько разновидностей циклических конструкций:

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

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

- Цикл со счетчиком (с параметром).

Порядок выполнения цикла с предусловием:

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

2) При входе в цикл, вычислить условие;

3) Если условие = false, то вход в цикл не выполняется и управление передается блоку, следующему за конструкцией цикла;

4) Если условие = true, то происходит вход в цикл и однократное выполнение его тела;

5) Как только достигнут конец тела цикла, управление снова передается на его заголовок, где снова вычисляется условие, т.е. переход на пункт 2;

6) Цикл завершен, когда очередное вычисление условия дает значение false.

Порядок выполнения цикла с постусловием:

2) При входе в цикл, происходит однократное выполнение его тела;

3) Вычислить условие;

4) Если условие = true, то выход из цикла, управление передается блоку, следующему за конструкцией цикла;

5) Если условие = false, то происходит снова выполнение тела цикла, т.е. переход на пункт 2;

6) Цикл завершен, когда очередное вычисление условия дает значение true.

Правила организации циклов с условиями:

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

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

Цикл со счетчиком (параметром) работает следующим образом:

1) Вычисляется начальное значение параметра цикла;

2) Параметру цикла присваивается начальное значение;

3) Проверяется условие, чтобы значение переменной цикла была <= конечного значения;

4) Если условие истинно, то выполняются действия, стоящие в теле цикла;

5) Если условие ложно, то происходит выход из цикла на блок, стоящий за ним;

6) Переменной цикла присваивается следующее значение;

7) Повтор с пункта 3.

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

- Начальная установка значения переменной цикла до входа в цикл не требуется;

- Запрещено изменять в теле цикла значения переменных, стоящих в заголовке (блок "Подготовка");

- количество итераций цикла неизменно и точно определяется начальным и конечным значениями;

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

Итак, циклический алгоритм должен содержать следующие основные блоки:

- Инициализация, т.е. определение начального значения параметра;

- Проверка условия цикла;

- Тело цикла (повторяющаяся группа действий);

- Модификация параметра цикла.

В таблице 1.8 представлены блок-схемы и псевдокод этих трех вариантов циклических конструкций.

Таблица 1.8 Варианты циклических конструкций

Название конструкции	Принцип работы	Псевдокод (АЯ)	Блок-схема
Цикл с предусловием	Пока условие истинно, повторяй тело цикла	Нц Пока условие тело цикла Кц;
Цикл с постусловием	Выполняй тело цикла до тех пор, пока условие не станет истинным	Нц тело цикла Кц Пока условие;
Цикл со счетчиком (с параметром)	Выполняй тело цикла для всех значений параметра цикла в заданном диапазоне	Нц Для (инициализация параметра; условие цикла; модификация параметра) тело цикла Кц ;

Пример 1.7

Необходимо протабулировать функцию y = cos(x), т.е. вывести таблицу ее значений при изменении аргумента x в пределах заданного диапазона от некоторого начального значения x0 до конечного значения xn с шагом h.

Решение.

Проведем анализ алгоритма решения.

Для этого ответим на вопрос: «Будут ли какие-либо действия в алгоритме повторяться?» Ответ, да, вычисление значения функции для каждого значения аргумента х. Это означает, что нам необходим цикл для решения задачи.

Определимся с блоками цикла.

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

Условие цикла – это условие, при котором происходит повтор. В нашей задаче, мы повторяем вычисление функции, пока аргумент находится внутри заданного диапазона. Если до начала вычислений задать аргументу начальное значение x=x0, то для проверки условия, достаточно определить, не достиг ли аргумент верхней границы диапазона: x<=xn.

Также, чтобы повтор действий происходил при разных значениях аргумента, необходимо задать увеличение аргумента на заданный шаг: x=x+h.

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

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

Таблица 1.9 Алгоритм табулирования функции

Псевдокод	Блок-схема
алг Вычисление_Функции() нач Ввод х0, xn, h; x=x0; нц Пока (x<=xn) y=cos(x); Вывод x, y; x=x+h; кц кон
алг Вычисление_Функции() нач Ввод х0, xn, h; x=x0; нц y=cos(x); Вывод x, y; x=x+h; кц Пока (x>xn) кон
алг Вычисление_Функции() нач Ввод х0, xn, h; нц Для (x=x0; x<=xn; x=x+h) y=cos(x); Вывод x, y; кц кон

Псевдокод

Блок-схема

алг Вычисление_Функции()

нач

Ввод х0, xn, h;

x=x0;

нц Пока (x<=xn)

y=cos(x);

Вывод x, y;

x=x+h;

кц

кон

алг Вычисление_Функции()

нач

Ввод х0, xn, h;

x=x0;

нц

y=cos(x);

Вывод x, y;

x=x+h;

кц Пока (x>xn)

кон

алг Вычисление_Функции()

нач

Ввод х0, xn, h;

нц Для (x=x0; x<=xn; x=x+h)

y=cos(x);

Вывод x, y;

кц

кон

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

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

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

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

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

Контрольные вопросы для самоанализа материала.

- Циклический алгоритм

- Тело цикла

- Условие цикла

- Блок «Подготовка»

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

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

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

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

Основания для сравнения	Виды циклов
Основания для сравнения

3. Проанализируйте блок-схему предложенного алгоритма (рис. 1.8). Для удобства алгоритм разделен на 3 фрагмента. Укажите назначение каждого фрагмента. Перечислите используемые алгоритмические конструкции в каждом фрагменте. Определите вид алгоритма. Составьте краткую аннотацию к алгоритму (по пунктам):

1) Назначение алгоритма

2) Краткая характеристика (основная идея)

3) Названия алгоритмических конструкций и цель их использования

4) Вид алгоритма

Рис. 1.8 Блок-схема алгоритма

2. РАЗДЕЛ «ОСНОВЫ АЛГОРИТМИЗАЦИИ». Тема «Методы построения базовых алгоритмов»

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

В обработке информации, центральное место занимает сама обрабатываемая информация, которая называется еще данными.

Данные можно классифицировать по разным признакам.

По своему назначению можно выделить:

- Входные данные – элементы информации, существующие во внешнем мире и читаемые алгоритмом извне в ходе процесса;

- Результаты (выходные данные) - элементы информации, которые передаются алгоритмом во внешний мир в ходе процесса;

- Внутренние данные – элементы информации, содержащиеся внутри алгоритма на каком-либо этапе процесса.

По отношению к процессу решения различают исходные данные трех видов: постоянные, условно-постоянные и переменные.

- Постоянные исходные данные - это данные, которые сохраняют свои значения в процессе решения задачи (математические константы, координаты неподвижных объектов) и не зависят от внешних факторов.

- Условно-постоянные данные - это данные, которые могут иногда изменять свои значения; причем эти изменения не зависят от процесса решения задачи, а определяются внешними факторами (величина подоходного налога, курс валют, количество дней в году).

- Переменные данные - это данные, которые изменяют свои значения в процессе решения задачи.

Также данные можно классифицировать по способу объединения их составных частей в единое целое. Здесь речь идет о структуре данных.

Структура данных – способ объединения отдельных элементов данных.

Структуры данных наряду с алгоритмами являются основными составными частями создаваемых программ. Одну из своих книг профессор Н. Вирт так и назвал «Алгоритмы + Структуры данных = Программа»

Данные

По структурному признаку данные можно разделить на простые и структурированные (рис. 2.1).

Простые

Структурированные

Неоднородные

Однородные

Рис. 2.1 Классификация данных по структурному признаку

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

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

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

Если все элементы, входящие в такую структуру, однотипны, то такая структура называется однородной, в противном случае - неоднородной.

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

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

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

Больший интерес для нас представляет организация работы с набором данных.

Существует разные способы работы с однотипным набором данных:

- Для работы с набором данных используется одна переменная (ячейка памяти), в которую последовательно, поочередно вводятся все элементы набора. Все действия с элементом данных происходят до очередного ввода нового значения, затирающего предыдущее значение. Действия с одним элементом образуют одну итерацию. Таких итераций будет столько, сколько элементов, потребуется ввести. Следовательно, для организации работы с набором данных таким способом, нам потребуется циклическая структура. Как правило, если количество обрабатываемых элементов заранее неизвестно, то необходим цикл с пред- или постусловием. Такой набор однотипных величин, которые вводятся и обрабатываются циклически, называется последовательностью значений. Чтобы цикл ввода элементов последовательности не был бесконечным, определяют специальный элемент, который является признаком конца последовательности.

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

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

Рассмотрим пример алгоритма обработки последовательности.

Пример 2.1

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

Решение

Для хранения элементов последовательности возьмем простую переменную х. При организации работы с последовательностью необходим цикл с условием, например с предусловием. На каждой итерации цикла будем осуществлять ввод элемента последовательности и проверки для него условий отрицательности ( х<0), положительности ( x>0) и четности ( x%2= =0) (остаток от деления на 2 должен быть равен 0, для обозначения операции взятия остатка используем знак %, как в С-подобных языках программирования). В зависимости от выполнения условий, будем производить вычисления суммы и произведения. Для организации проверок условий используем конструкцию Ветвление. Особенностью алгоритма является то, что нам пришлось первый раз ввести х до цикла, так как при входе в цикл сразу осуществляется проверка условия, и х должно уже быть определено.

На рис. 2.2 приведена блок-схема алгоритма.

Рис.2.2 Блок-схема алгоритма обработки последовательности

Контрольные вопросы для самоанализа материала.

1. Обобщите понятие последовательности по следующему плану:

- Назначение последовательности;

- Краткая характеристика (определение);

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

- Область применения.

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

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

3. Проанализируйте блок-схему предложенного алгоритма (рис. 2.3). Алгоритм выводит минимальный элемент последовательности и его номер. Последовательность вводится пользователем, окончание ввода – ввод нулевого значения.

a) Опишите алгоритмические конструкции, использованные в данном алгоритме.

b) Перечислите название и назначение каждого пронумерованного блока.

c) Укажите блок, ошибочно размещенный не там, где нужно.

Рис. 2.3 Ошибочная блок-схема алгоритма

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

Структурированные данные образуются объединением простых элементов, составные части называются компонентами этой структуры.

Классическим примером однородной структуры данных является массив.

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

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

ИМЯ

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

Дадим определение массива.

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

Перечислим основные признаки массива:

- Массив является структурой, т.е. состоит из множества компонент и в каждый момент времени имеет несколько значений;

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

- Массив является упорядоченной структурой, т.е. данные в массиве хранятся не хаотично, а в установленном порядке;

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

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

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

имя массива[индекс]

Например: A[1], Mas[10], Х[i]

В зависимости от количества измерений различают одномерные массивы - когда для получения доступа к его элементам достаточно одного индекса, двумерные – два индекса, и т.д.

Таким образом, массив определяется своим именем и имеет фиксированный размер, все его элементы упорядочены (пронумерованы). В нашем примере массив имеет имя - ИМЯ, размер – 9 компонент, пронумеровать его элементы можно с помощью одного индекса от 1 до 9.

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

Выделим следующие действия над массивами, которые следует осуществлять поэлементно:

- ввод массива (инициализация массива);

- вывод массива;

- арифметические действия, выполняемые над всеми элементами массива;

- арифметические действия, выполняемые над определенной группой элементов массива;

- поиск максимального или минимального элемента;

- перестановка элементов;

- замена элементов;

- вставка элемента;

- удаление элемента;

- поиск элемента по условию;

- сортировка элементов.

Пример 2.2

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

Решение

Для хранения результата вычислений возьмем простую переменную Sum.

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

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

На каждой итерации второго цикла будем осуществлять проверку условия кратности элемента массива заданному числу, A[i] % k= =0 (остаток от деления на k должен быть равен 0). В зависимости от выполнения условия, будем производить вычисление суммы. Для проверки условия используем конструкцию Неполного ветвления.

На рис. 2.4 приведена блок-схема алгоритма.

Рис. 2.4 Блок-схема алгоритма

Пример 2.3

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

Решение

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

Для реализации алгоритма используем циклическую структуру. Поскольку количество повторов цикла равно количеству элементов массива, то можно использовать конструкцию Цикла со счетчиком.

На каждой итерации второго цикла будем осуществлять одновременно поиск максимального и минимального элемента. В качестве начального значения максимума и минимума возьмем значение первого элемента массива A[0].

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

Последним действием будет обмен местами максимума и минимума. Этот обмен происходит в самом массиве, поэтому меняются местами элементы A[Nmax] и A[Nmin]. Обмен реализуется переприсваиванием элементов, для этого используются копии этих элементов max и min.

На рис. 2.5 приведена блок-схема алгоритма.

Рис. 2.5 Блок-схема алгоритма

Пример 2.4

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

Решение

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

Для реализации алгоритма используем циклическую структуру.

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

Осуществляя поиск отрицательного элемента, мы не знаем, где он будет находиться, возможно, в начале массива, а может быть и в конце. Но, если мы встретим его, нет необходимости просматривать остальные элементы, можно закончить просмотр массива и выйти из цикла. Таким образом, так как количество повторов цикла заранее неизвестно, то можно использовать конструкцию цикла с условием, например, Цикл с предусловием. Условием выхода из цикла будет либо равенство флага 1 (элемент найден) либо достижение верхней границы массива (i=N), а элемент не был найден.

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

На рис. 2.6 приведена блок-схема алгоритма.

Рис. 2.6 Блок-схема алгоритма

Контрольные вопросы для самоанализа материала.

1. Обобщите понятие массива по следующему плану:

- Назначение массива;

- Краткая характеристика (определение);

- Алгоритмические конструкции, применяемые при обработке массива;

- Область применения;

- Недостатки и преимущества использования для хранения данных.

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

3. Проанализируйте блок-схему предложенного алгоритма (рис. 2.7). Алгоритм формирует из двух заданных массивов Х(n) и У(n) размерности n - третий Z(n) такой же размерности, по правилу: большее из X[i] и Y[i] становится новым значением Z[i]:

d) Опишите алгоритмические конструкции, использованные в данном алгоритме.

e) Перечислите название и назначение каждого пронумерованного блока.

f) Укажите и аргументируйте ошибку в блок-схеме алгоритма.

Рис. 2.7 Ошибочная блок-схема алгоритма

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

Рассмотрим массивы с большим, чем одно, числом измерений
(индексов).

Как известно, одномерный массив можно представить в виде цепочки, где каждый элемент имеет свой номер, свое значение индекса.

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

А [1,3]

Рис. 2.8 Двумерная таблица

Положение элемента в двумерном массиве описывается двумя индексами: первый – номер строки таблицы, второй – номер столбца.

Чтобы обратится к элементу двумерного массива, необходимо знать два индекса - номер строки и номер столбца, например можно обратиться с помощью индексной переменной - А [1,3] к элементу, стоящему в первой строке и третьем столбце (рис. 2.8).

Так как мы изучаем алгоритмы для того, чтобы в дальнейшем научиться писать программы, то подобно многим языкам программирования примем диапазон значений индекса строки от 0 до n-1, а индекса столбца от 0 до m-1 для массива из n строк и m столбцов.

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

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

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

Заказы_билетов = Массив [Месяц, День, Ряд, Место],

где Месяц = 1 .. 12;

День= 1 .. 31;

Ряд = ‘A’ .. ‘J’;

Место = 1 .. 25;

Значениями элементов массива могут быть значения «Да»
(продано) или «Нет» (не продано). Например, обращение к элементу B [1, 1, ‘B’, 16] – скажет нам, заказан ли билет на 1 января на место B16. Это пример многомерного массива, имеющего четыре индекса.

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

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

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

Пример 2.5

Пользователь вводит значения двумерного массива заданной размерности (n строк и m столбцов). Рассмотрим алгоритм подсчета среднего арифметического всех четных элементов массива. Составить блок-схему алгоритма.

Решение

Для хранения результата вычислений возьмем простую переменную Sr.

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

Отделим операцию ввода данных от операции вычисления. Для этого будем также использовать два вложенных счетных цикла. Для проверки четности элемента массива возьмем условие A[i] % 2= =0 (остаток от деления на 2 должен быть равен 0). В конструкции Неполного ветвления в зависимости от выполнения условия, будем производить вычисление суммы и количества элементов.

Среднее арифметическое вычислим разделив итоговую сумму на количество четных элементов, если последнее не равно нулю. На рис. 2.9 приведена блок-схема алгоритма.

Пример 2.6

Пользователь вводит значения двумерного массива заданной размерности (n строк и m столбцов). Рассмотрим алгоритм вывода значений максимальных элементов каждого столбца массива. Составить блок-схему алгоритма.

Решение

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

Для хранения максимальных элементов возьмем простую переменную max. Так как вычисления происходят последовательно, столбец за столбцом, то для хранения максимумов достаточно будет одной переменной, при переходе к новому столбцу значение max будем инициализировать заново и вычислять новый максимум.

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

Рис. 2.9 Блок-схема алгоритма

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

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

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

На рис. 2.10 приведена блок-схема алгоритма.

Рис. 2.10 Блок-схема алгоритма

Контрольные вопросы для самоанализа материала.

1. Заполните кроссворд (рис.2.11):

По горизонтали

1. Свойство, при котором алгоритм должен приводить к решению задачи за конечное число шагов.

2. Графический способ описания алгоритма.

3. Название блока в блок-схеме для организации цикла с заданным числом повторений.

4. Один из вариантов, путей выполнения алгоритма.

5. Многократно повторяемая группа действий.

По вертикали

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

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

7. Таблица из однотипных элементов, организованная по строкам и столбцам - это … . массив.

8. Процесс разработки алгоритма для решения задачи.

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

1.					8.
		6.

				2.

						9.
	3.		7.



						4.
					5.

Рис. 2.11 Кроссворд

2. Сравните одномерные и двумерные массивы. Основания для сравнения выберите сами, например: количество индексов, необходимых для доступа к элементу; алгоритмические конструкции, используемые при реализации, и другие. Наиболее принципиальные позиции зафиксируйте в таблице.

Основания для сравнения	Виды массивов
Основания для сравнения

3. Проанализируйте блок-схему предложенного алгоритма (рис. 2.12). Для удобства алгоритм разделен на 3 фрагмента. Укажите назначение каждого фрагмента. Перечислите используемые алгоритмические конструкции в каждом фрагменте. Определите вид алгоритма. Составьте краткую аннотацию к алгоритму (по пунктам):

1) Назначение алгоритма

2) Краткая характеристика (основная идея)

3) Названия алгоритмических конструкций и цель их использования

4) Вид алгоритма

Рис. 2.12 Блок-схема алгоритма

Алгоритмы сортировки структурированных данных

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

Такое расположение объектов в определенном порядке и называется сортировкой. А основная цель сортировки - сделать дальнейший поиск нужных объектов более быстрым или эффективным.

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

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

Мы встречаемся с отсортированными объектами в телефонных книгах, в оглавлениях книг, в библиотеках, словарях и т.д.

Рассмотрим сортировку на примере одномерного массива как структуры, состоящей из заданного множества однотипных объектов.

Элементы массива можно отсортировать по следующим признакам:

- по возрастанию: a [1] < a [2] < … < a [n]

- по не убыванию: a [1] ≤ a [2] ≤ … ≤ a [n]

- по убыванию: a [1] > a [2] > … > a [n]

- по не возрастанию: a [1] ≥ a [2] ≥ … ≥ a [n]

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

Имеется одномерный массив чисел, состоящий из n элементов: А[n]. Переставить элементы массива так, чтобы их значения располагались в порядке возрастания (не убывания). Другими словами, для любой пары элементов А[i] и А[i+1] должно выполняться неравенство вида: А[i] <= А[i+1].

К настоящему времени разработано большое количество алгоритмов сортировки. Швейцарский программист Н.Вирт в книге «Алгоритмы и структуры данных» подробно описал и провел сравнительный анализ алгоритмов сортировки.

Все методы сортировки делятся на базовые (прямые) и улучшенные.

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

Базовые методы сортировки по принципу, лежащему в основе метода, в свою очередь делятся:

- сортировка выбором (выделением);

- сортировка обменом («пузырьковая»);

- сортировка вставкой (включением).

Рассмотрим каждый из этих методов в отдельности.

Сортировка методом простого обмена («пузырьковая» сортировка)

Этот метод может быть применен для любого массива.

Рассмотрим сортировку одномерного массива из n элементов по возрастанию.

Идея метода:

1. Просматриваем весь массив с первого по последний элемент.

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

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

4. Так как один просмотр массива выставляет на свое место только один элемент, то просмотров массива необходимо n-1, где n - количество элементов массива. Первый элемент автоматически окажется на своем месте.

Этот метод также называют методом «пузырька», т.к. в процессе сортировки элементы с заданным свойством всплывают на «поверхность», как пузырьки воздуха на поверхность воды.

Пример 2.7

Рассмотрим сортировку одномерного массива чисел из 5 элементов по возрастанию.

5 6 4 8 1

1. шаг 5 6 4 8 1

5 4 6 8 1

5 4 6 1 8

2. шаг 4 5 6 1 8

4 5 6 1 8

4 5 1 6 8

3. шаг 4 5 1 6 8

4 1 5 6 8

4. шаг 1 4 5 6 8

На рис. 2.13 приведена блок-схема алгоритма.

Сделаем некоторые комментарии к блок-схеме.

Для хранения массива возьмем переменную А[] – одномерный массив, k – номер просмотра массива (от 1 до n – 1); I – номер рассматриваемой пары элементов; x – промежуточная переменная для перестановки элементов.

Отделим операцию ввода массива от операции сортировки. Для ввода массива будем использовать конструкцию вложенных циклов.

Поскольку сортировка обменом предполагает n–1 просмотр массива, то для цикла по количеству просмотров можно использовать конструкцию Цикла со счетчиком. В качестве параметра цикла можно взять номер просмотра массива k.

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

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

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

Сортировка методом простого выбора.

Эта сортировка обычно применяется для массивов, не содержащих повторяющихся элементов.

Рассмотрим сортировку также одномерного массива из n элементов по возрастанию.

Идея метода:

1. Выбираем в массиве из элементов с первого по последний максимальный элемент (в случае сортировки по возрастанию).

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

3. Повторяем действия пункта 2 для элементов с первого по предпоследний, не затрагивая последний элемент, который уже отсортирован.

4. Так как один просмотр массива выставляет на свое место только один элемент, то просмотров массива необходимо n - 1, где n - количество элементов массива. Первый элемент автоматически окажется на своем месте.

Пример 2.8

Рассмотрим сортировку одномерного массива чисел из 5 элементов по возрастанию. На рис. 2.14 приведена блок-схема алгоритма.

1. шаг 5 13 7 1 9

2. шаг 5 9 7 1 13

3. шаг 5 1 7 9 13

4. шаг 1 5 7 9 13

Сделаем некоторые комментарии к блок-схеме.

Для хранения массива возьмем переменную А[] – одномерный массив, k – номер просмотра массива (от 1 до n – 1); max – промежуточная переменная для перестановки элементов.

Поскольку сортировка выбором предполагает n–1 просмотр массива, то для цикла по количеству просмотров можно использовать конструкцию Цикла со счетчиком. В качестве параметра цикла можно взять номер просмотра массива k.

Одна итерация цикла - один просмотр массива. На каждой итерации будем осуществлять поиск максимального (для сортировки по возрастанию) из элементов с 1 по n-k. Далее, найденный максимум обменивается местами с последним из рассматриваемых элементов, используя промежуточную переменную max. Для проверки условия используем конструкцию Неполного ветвления.

Рис. 2.14 Блок-схема алгоритма сортировки выбором

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

Сортировка методом вставок (прямого включения)

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

Рассмотрим сортировку также одномерного массива из n элементов по возрастанию.

Идея метода:

1. Мысленно массив делится на две части: отсортированную и не отсортированную. Первоначально отсортированная часть состоит из одного первого элемента, а не отсортированная из всех остальных.

2. Наша задача - поочередно все элементы из не отсортированной части вставить в отсортированную, не нарушая ее упорядоченности. Таким образом, алгоритм разбивается на шаги, каждый шаг - это вставка одного элемента, со второго по последний. Возьмем для обозначения номера этого элемента переменную I = 2, ....n

3. Вставка I-го элемента в отсортированную часть состоит в следующем:

a) Создаем копию I–го элемента в дополнительной переменной x.

b) Просматриваем все элементы левее I–го, двигаясь к началу массива.

c) Среди элементов с 1 по i – 1 ищем позицию вставки k, куда нужно поставить I–ый элемент, не нарушая упорядоченности массива.

d) Одновременно с просмотром все элементы, большие вставляемого, т.е. когда a[k] > x, будем сдвигать на одну позицию вправо, так как в силу упорядоченности по возрастанию они должны располагаться правее. В результате в отсортированной части будет освобождено место под вставляемый элемент.

e) Просмотр заканчивается, как только встретится элемент, меньше либо равный вставляемому (a[k] <= x) или будет достигнут левый конец упорядоченной части массива.

f) Вставляем элемент в отсортированную часть на следующую позицию за той, где закончился просмотр (т.е. на позицию k + 1) или на первую позицию, если позиция вставки не была найдена (все элементы оказались больше вставляемого).

Пример 2.9

Рассмотрим сортировку одномерного массива чисел из 5 элементов по возрастанию.

1. шаг 1 13 6 0 11

1 13 6 0 11

2. шаг 1 13 6 0 11

1 13 0 11

1 6 13 0 11

3. шаг 1 6 13 0 11

1 6 13 11

0 1 6 13 11

4. шаг 0 1 6 13 11

0 1 6 13

0 1 6 11 13

На рис. 2.15 приведена блок-схема алгоритма.

Сделаем некоторые комментарии к блок-схеме.

Для хранения массива возьмем переменную А[] – одномерный массив, I – номер позиции вставляемого элемента из не отсортированной части массива; k – позиция вставки I–го элемента в отсортированную часть массива.

Поскольку необходимо вставить n–1 элемент, то I - номер этого элемента будет меняться от 1 до n–1. Используем для этого конструкцию Цикла со счетчиком (с параметром I).

Одна итерация цикла – это вставка одного элемента массива. Для поиска позиции вставки используем цикл с предусловием. С помощью переменной k будем двигаться влево, уменьшая k от i-1 до нуля. На каждой итерации цикла с предусловием проверяем, нашли ли мы меньший элемент, или достигли ли мы левой границы: A[k]<=x или k<0 . Если нет, то сдвигаем большие элементы вправо: A[k+1]=A[k]. Далее, производим вставку элемента на позицию k+1: A[k+1]=x.

Рис.2.15 Блок-схема алгоритма сортировки методом вставок

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

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

- количество присваиваний;

- количество сравнений.

Практические и теоретические исследования показали, что время исполнения алгоритма сортировки обменами и вставками оценивается как величина порядка – О (n²), где n – длина массива, тогда как время исполнения алгоритма выбора – О (n * ln (n)).

На практике это означает, что прямые методы сортировки лучше применять для коротких массивов, а для массивов большой длины лучше использовать улучшенные методы сортировки: пирамидальная сортировка; «быстрая» сортировка Хоара и др.

Контрольные вопросы для самоанализа материала.

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

Основания для сравнения	Алгоритмы сортировки набора данных
Основания для сравнения

2. Приведите три примера использования алгоритмов сортировки на практике в вашей жизни.

1.______________

2.______________

3.______________

3. Покажите на примере массива (5 8 2 7 5 2 4 9 4) пошаговое выполнение сортировки по убыванию методом обмена, выбора и вставок (смотри примеры 2.7,2.8,2.9).

Алгоритмы поиска в упорядоченных структурах

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

Последовательный (линейный) поиск

Этот метод может быть применен для любого набора данных.

Идея метода:

1. Последовательно просматриваем элементы структуры данных;

2. Сравниваем значение очередного рассматриваемого элемента с искомым элементом;

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

Недостатки алгоритма:

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

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

На рис. 2.16 приведен фрагмент блок-схемы алгоритма.

Рис.2.16 Блок-схема алгоритма последовательного поиска

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

Линейный поиск с использованием барьерного элемента

Этот метод может быть применен для любого набора данных.

Идея метода:

1. На (n + 1) место в структуре данных из n элементов записываем искомый элемент, который будет являться барьерным;

2. Проводим последовательный просмотр элементов массива и сравнение их с искомым;

3. Просмотр заканчивается, если такой элемент найден, если же искомый элемент найден только как последний, т.е. имеющий номер n + 1, значит, такого элемента нет.

На рис. 2.17 приведен фрагмент блок-схемы алгоритма.

Рис 2.17 Блок-схема алгоритма линейного поиска с барьерным элементом

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

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

Алгоритм бинарного поиска

Этот метод может быть применен для отсортированного набора данных.

Рассмотрим задачу поиска заданного элемента в одномерном массиве из n элементов, отсортированном по возрастанию.

Задача поиска значения X в упорядоченном по возрастанию массиве A[0]<=A[1]<=A[2]<=......<=A[N-1] формулируется следующим образом. Требуется выяснить входит ли значение X в этот упорядоченный массив, и если входит, то определить значение K, для которого A[K]=X.

Идея метода:

1. Просматриваем весь массив с первого по последний элемент.

2. Находим средний элемент массива (по положению, т.е. по номеру элемента).

3. Проверяем, является ли средний элемент массива искомым. Если Да, то ответ получен - элемент найден, поиск закончен, если Нет, то возможны два случая.

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

5. Если искомый элемент больше среднего элемента, то, в силу аналогичных причин, можно повторить поиск только для правой части массива.

6. Средний элемент в последующих поисках из рассмотрения исключается.

Пример 2.10

Найти элемент X = 8 в упорядоченном массиве по возрастанию.

номера элементов 0 1 2 3 4

значения элементов 1 5 6 8 10

Шаг 1.

1. Установим левую границу массива (номер самого левого элемента) L=0, правая граница (номер самого правого элемента из рассматриваемых) R=4.

2. Находим номер среднего элемента M = [(L + R) / 2] = (0+4)/2=2, A[M]=6

0 1 2 3 4

1 5 6 8 10

3. Проверяем, равен ли искомый элемент среднему: A[M]=X . Ответ - Нет, продолжаем поиск.

4. Переустанавливаем границы поиска. Для этого:

a) определяем, меньше ли искомый элемент, среднего: X< A[M]. Ответ - Нет, следовательно, искомый элемент больше среднего;

b) исключаем всю левую половину массива из рассмотрения, включая средний элемент, так как там в силу упорядоченности массива находятся только меньшие X=8 элементы;

c) Новые границы массива: L=M+1=2+1=3, а правая не изменяется R=4.

0 1 2 3 4

1 5 6 8 10

Шаг 2.

Повторяем пункты 1-4 для части массива с третьего по четвертый элементы.

5. Находим номер среднего элемента M = [(L + R) / 2] = (3+4)/2=3, A[M]=8

0 1 2 3 4

1 5 6 8 10

6. Проверяем, равен ли искомый элемент среднему: A[M]=X . Ответ - Да, поиск закончен, элемент найден.

На рис. 2.18 приведена блок-схема алгоритма бинарного поиска.

Сделаем некоторые комментарии к блок-схеме.

Для хранения массива возьмем переменную А[] – одномерный массив, L и R – границы рассматриваемой части массива, где ведется текущий поиск; Flag – признак того, что элемент найден, изначально Flag=False; X – элемент, который мы ищем.

Для реализации алгоритма используем конструкцию цикла с предусловием, так количество шагов поиска заранее неизвестно. В качестве условия продолжения цикла потребуем одновременную истинность двух условий: элемент еще не найден и элементы для поиска еще не закончились - (NOT Flag) и (L<=R).

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

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

Рис 2.18 Блок-схема алгоритма бинарного поиска

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

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

Метод «быстрой сортировкой» Хоара (обменная сортировка с разделением) является улучшением метода сортировки, основанного на обмене. Идея улучшения состоит в том, чтобы сравнивать и обменивать местами элементы, стоящие на возможно больших расстояниях друг от друга. Быстродействие метода порядка – n*log(n).

Контрольные вопросы для самоанализа материала.

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

1 этап. Задание параметров поиска

1. Инициализация массива.

2. Определение условий поиска.

3. Определение границ массива.

4. Определение условий окончания поиска.

2 этап. Выполнение поиска

1. Определение среднего элемента.

2. Проверка условий окончания поиска.

3. Определение половинного интервала для продолжения поиска.

3 этап. Оценка результатов поиска

1. Проверка состоялся ли поиск.

2. Публикация результатов.

Этапы алгоритма бинарного поиска	Вопросы для беседы
1 этап. Задание параметров поиска	1. Чему равна первоначально левая граница диапазона поиска? 2. 3. 4.
2 этап. Выполнение поиска	1. 2. 3. 4.
3 этап. Оценка результатов поиска	1. 2. 3. 4.

3. РАЗДЕЛ «ОСНОВЫ АЛГОРИТМИЗАЦИИ». Тема «Методы вычисления сложности алгоритмов»

Анализ трудоемкости алгоритмов

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

Эффективность алгоритма - это характеристика, определяющая объем ресурсов, необходимых для его выполнения.

Эффективность алгоритма можно анализировать с разных позиций.

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

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

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

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

Пространственная эффективность определяется объемом памяти, необходимой для выполнения алгоритма.

В последнее время данная характеристика не так актуальна, поскольку этот ресурс не является дорогостоящим и его можно легко восполнить.

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

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

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

Оценка сложности алгоритма

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

Как измерить временную сложность или эффективность алгоритма?

Время выполнения алгоритма T(n) зависит от объема входных данных (параметра n). Учебные программы, как правило, тестируются на небольшом объеме входных данных, однако как только вы начнете выполнять программу в реальных условиях, время ее работы может резко возрасти и возможность ее практического применения сведется к нулю.

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

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

Запись O(f(n)) - означает, что при большом объеме исходных данных время работы алгоритма ведет себя как функция f(n). Говорим, что алгоритм имеет сложность порядка f(n).

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

Если время работы не зависит от объема входных данных, алгоритм обладает сложностью O(1) или константной сложностью.

Распространенные варианты сложности перечислены в таблице 1. Функции перечислены в порядке возрастания сложности (убывания эффективности). Порядки сложности, перечисленные первыми (1-6), соответствуют наиболее эффективным алгоритмам.

Таблица 3.1 Типичные варианты сложности

Тип	Обозначение	Описание
Постоянная сложность	O(1)	Время работы не зависит от количества элементов. Время выполнения всегда одинаковое при любом n.
Сложность вида log(log(N))	O(log(log(N))
Логарифмическая сложность	O(log(n)) O(n^c), где 0<c<1	Время работы возрастает в логарифмической зависимости от количества элементов
Линейная сложность	O(n)	Время работы возрастает прямо пропорционально количеству элементов
Сложность n-log-n	*O(nlog(n))**	Время работы возрастает как произведение линейной и логарифмической зависимостей от количества элементов
Квадратичная сложность	O(n²)	Время работы возрастает в квадратичной зависимости от количества элементов
Кубическая сложность	O(n³)	Время работы возрастает как кубическая функция
Полиномиальная сложность	O(n^c), где c>3	Время работы возрастает как полином (степенная функция)
Экспоненциальная сложность	O(2ⁿ) O(cⁿ),где c>2	Время работы возрастает как экспонента
Сложность вида n!	O(n!)	Время работы возрастает как факториал

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

Правила определения сложности:

1. O(C*a)=O(a)

2. O(a*b)=O(a)*O(b) или O(a/b)=O(a)/O(b)

3. O(a+b) равна доминанте O(a) и O(b)

С - константа, a и b - функции.

Постоянные множители можно не учитывать при определении порядка сложности. Например, О(2*N)=O(N)

Порядок сложности суммы функций заменяется максимальным порядком сложности слагаемых. Например, O(N³+N²)=O(N³)

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

Сложность вычислительного действия и условия всегда константная.

Алгоритмы без циклов имеют константную сложность.

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

Пример 3.1 Вычислить сложность алгоритма нахождения факториала числа

Решение

Номер блока	Псевдокод	Оценка сложности	Комментарии
A	Для i от 1до N с шагом 1	O(A)=N* O(B) = NO(1)=O(N1)=O(N)	тело цикла A выполняется N раз
B	Нц	O(B)=О(C) = О(1)	Тело цикла B состоит из действия C. Сложность вычисляется как сложность блока C
C	f=f*i;	О(C)=О(1)	Сложность вычислительного действия константная
	Кц;

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

Пример 3.2 Вычислить сложность алгоритма нахождения максимального элемента в каждой строке для матрицы A[NxN]

Конструкция вложенных циклов в худшем случае имеет квадратичную сложность.

Решение

Номер блока	Порядок рассмотрения	Псевдокод	Оценка сложности	Комментарии
A	8	Для i от 1 to N с шагом 1	O(A)=N* O(B) = NO(N)=O(NN)=O(N²)	тело цикла A выполняется N раз
B	7	Нц	O(B)=О(C+ D+I) = О(N)	Тело цикла B состоит из действия C, цикла D и действия I. Сложность вычисляется как доминанта для блоков C, D и I
C	6	max=A[i,1];	О(C)=О(1)	Сложность вычислительного действия константная
D	4	Для j от 1 до N с шагом 1	O(D)=N* O(E) = NO(1)=O(N1)=O(N)	тело цикла D выполняется N раз
E	3	Нц	O(E)=О(F+ G) = О(1)	Тело цикла E состоит из условия F и действия G. Сложность вычисляется как доминанта для блоков F и G
F	2	Если (a[i]>max)	O(F)=O(1)	Сложность условия константная
G	1	Тогда max=a[i];	О(G)=О(1)	Сложность вычислительного действия константная
		Все
		Кц;
I	5	Вывод(max)	O(I)=O(1)	Сложность вычислительного действия константная
		Кц

Сложность алгоритма O(N²) - квадратичная, так как количество итераций вложенных циклов равно N*N.

О(G)=О(1); O(F)=O(1);

O(E)=О(F+ G) = О(1); // правило 3

O(D)=N* O(E) = N*O(1)=O(N*1)=O(N); //правила 2 и 1

О(C)=О(1); O(I)=O(1);

O(B)=О(C+ D+I) = О(N); // правило 3

O(A)=N* O(B) = N*O(N)=O(N*N)=O(N²) //правило 2

Рекомендации по анализу и понижению сложности алгоритма.

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

Далее попытайтесь сократить количества операторов в циклах с наибольшей глубиной вложенности.

Контрольные вопросы для самоанализа материала.

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

- Эффективность алгоритма

- Пространственная эффективность

- Временная эффективность

- Сложность алгоритма

- О – сложность алгоритма

- Правила определения сложности

- Способы анализа сложности

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

3. Укажите способы понижения сложности циклических алгоритмов.

4. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ РАЗДЕЛА «ОСНОВЫ АЛГОРИТМИЗАЦИИ»

Цель работы:

- Закрепить навыки разработки спецификаций основных моделей алгоритмов;

- Закрепить навыки анализа сложности алгоритма.

Квалификационные требования:

- Знать основные модели алгоритмов;

- Знать методы построения алгоритмов;

- Знать методы вычисления сложности работы алгоритмов.

- Уметь разрабатывать алгоритмы для конкретных задач;

- Уметь использовать программы для графического отображения алгоритмов;

- Уметь определять сложность работы алгоритмов.

Ход выполнения:

1. Провести анализ задачи;

2. Определить вид алгоритма (линейный, разветвленный, циклический, комбинированный);

3. Выделить алгоритмические конструкции, используемые для реализации алгоритма;

4. Разработать блок-схему алгоритма, используя среду автоматизированного проектирования;

5. Сохранить блок-схему в виде графического файла с расширением jpeg, bmp и др.

6. Описать алгоритм задачи в виде псевдокода;

7. Провести вычисление сложности алгоритма;

8. Оформить результаты в виде таблицы;

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

Пример 4.1 Разработать алгоритм решения следующей задачи

Торговая фирма в первый день работы реализовала товаров на P тыс. руб., а затем ежедневно увеличивала выручку на 3%. Какой будет выручка фирмы в тот день, когда она впервые превысит заданное значение Q? Сколько дней придется торговать фирме для достижения этого результата?

Ход выполнения.

1. Анализ задачи

Каждый день торговая фирма имеет выручку на определенную сумму, начиная с Р тыс. рублей, причем эта сумма ежедневно увеличивается на 3%. Также задано пороговое значение выручки. Необходимо определить количество дней для достижения порогового значения выручки, а также саму выручку в этот день.

2. Определение вида алгоритма

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

3. Выделение алгоритмических конструкций для реализации алгоритма

Каково будет количество повторений цикла? Это заранее неизвестно. Вывод: для реализации циклического алгоритма будем использовать конструкцию цикла с условием, например, с предусловием.

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

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

4. Описание алгоритма задачи в виде псевдокода

Начало

Ввод P,Q;

Profit=P; count_days=1;

нц Пока (Profit <=Q)

Profit= Profit*1,03;

count_days= count_days+1;

кц

Вывод Profit, count_days;

Конец

Вставьте псевдокод в текстовый файл Контрольная_Задание_1

5. Разработка блок-схемы алгоритма

Для разработки алгоритма используем приложение FCEditor.exe Данное бесплатное приложение предназначено для построения блок схем алгоритмов и перевода их в код программ на языках Pascal, Delphi и C#. Полученную схему можно отредактировать, сохранить и экспортировать в графический файл. Основное отличие FCEditor от похожих программ - автоматическое расположение блоков и подстройка их размеров под содержимое. Новая версия редактора на основе технологии MS .NET позволяет красиво и быстро преобразовать код в понятную визуальную схему.

- Откройте FCEditor.exe

- Создайте новый файл командой Файл\Новый (рис. 4.1);

- В левой части экрана увидите блок-схему из двух блоков Начало и Конец, которую можно дополнить нужными блоками;

- Если навести курсор на стрелку, соединяющую блоки Начало и Конец, и нажать правую кнопку мыши (правое контекстное меню), то можно увидеть команды (рис. 4.2):

Рис. 4.1 Главное окно FCEditor

- Добавление нового – вставка нового блока между ними;

- Блок Вставить – вставка скопированного блока из имеющихся на рисунке;

- Передвинуть схему – переместить блок-схему по экрану;

- Редактировать – редактирование текста внутри блока.

Рис. 4.2 Новая блок-схема

- Эти же команды можно найти на панели быстрых кнопок;

- После создания блок-схемы, ее можно сохранить в виде файла с расширением .fml. Этот файл можно открыть в редакторе и снова отредактировать или создать на его основе новую блок-схему;

- Также можно конвертировать этот файл в графический с расширением .bmp (рис. 4.3).

Рис. 4.3 Конвертация в BMP

6. Оформление документации

Вставьте рисунок с блок-схемой в текстовый файл Контрольная_Задание_1 (рис. 4.4)

Рис. 4.4 Блок-схема алгоритма

Пример 4.2 Вычислить сложность алгоритма нахождения максимального элемента в массиве

Ход выполнения.

1. Анализ задачи

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

2. Определение вида алгоритма

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

3. Выделение алгоритмических конструкций для реализации алгоритма

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

4. Опишем алгоритм задачи в виде псевдокода:

Начало

max=a[1];

Для i от 1 to N с шагом 1

Нц

Если (a[i]>max)

То max=a[i];

Все

Кц;

Конец

5. Проанализируем псевдокод.

Очевидно, что основную сложность алгоритма несет на себе цикл перебора элементов массива. Тело цикла выполняется N раз. Сложность самого тела цикла вычисляется как доминанта условия и действия, которые в свою очередь имеют константные сложности O(1). Таким образом, сложность алгоритма определяется количеством повторений цикла N, т.е. линейная.

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

6. Оформим результаты в виде таблицы (таблица 4.1).

Таблица 4.1 Результаты вычисления сложности примера 1

Номер блока	Порядок рассмотрения	Псевдокод	Оценка сложности	Комментарии
Z	5	max=a[1];	O(Z)=1	Сложность присваивания константная
A	4	Для i от 1 to N с шагом 1	O(A)=N* O(B) = NO(1)=O(N1)=O(N)	тело цикла A выполняется N раз
B	3	Нц	O(B)=О(C+ D) = О(1)	Тело цикла B состоит из условия C и действия D. Сложность вычисляется как доминанта для блоков C и D
C	1	Если (a[i]>max)	О(C)=О(1)	Сложность условия константная
D	2	Тогда max=a[i];	О(D)=О(1)	Сложность вычислительного действия константная
		Все
		Кц;

7. Выводы.

Сложность самого алгоритма вычисляется как доминанта сложности цикла и присваивания. Сложность цикла O(N), т.к. тело цикла выполняется N раз, и сложность тела цикла равна O(1). В подобной ситуации принято говорить, что алгоритм имеет линейную сложность О(N).

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

Пример 4.3 Вычислить сложность алгоритма нахождения суммы ряда 1+х¹+х²+х³+х⁴+...+хⁿ

Ход выполнения.

1. Опишем алгоритм задачи в виде псевдокода:

Алгоритм Сумма_ряда(N,x)

Начало

s=0;

Для k от 0 до N с шагом 1

Нц

y=1;

Для i от 1 до k с шаг 1

Нц

y=y*x;

Кц;

s=s+y;

Кц

Вывод s;

Конец

2. Проанализируем псевдокод.

Очевидно, что основную сложность алгоритма несут на себе вложенные циклы: на каждой итерации внутреннего цикла вычисляется новый член ряда (новая степень х), а на каждой итерации внешнего производится суммирование этого вычисленного элемента. Тело внутреннего цикла в худшем случае выполняется N раз. Внешний цикл также выполняется N раз. Можно ожидать, что сложность алгоритма будет определяться NxN количеством действий, т.е. будет квадратичной.

3. Оформим результаты в виде таблицы (таблица 4.2).

Таблица 4.2 Результаты вычисления сложности

Номер блока	Порядок рассмотрения	Псевдокод	Оценка сложности	Комментарии
A	10	Начало	O(A)=O(B+C+K)= O(N²)	A состоит из действия B, цикла C и действия K. Сложность вычисляется как доминанта для блоков B,C и K
B	8	s=0;	O(B)=O(1)	Сложность вычислительного действия константная
C	7	Для k от 0 до N с шагом 1	O(C)=N* O(D) = NO(N)=O(NN)=O(N²)	тело цикла A выполняется N раз
D	6	Нц	O(D)=О(E+ F+I) = О(N)	Тело цикла D состоит из действия E, цикла F и действия I. Сложность вычисляется как доминанта для блоков E,F и I
E	5	y=1;	О(E)=О(1)	Сложность вычислительного действия константная
F	3	Для i от 1 до k с шаг 1	O(F)=N* O(G) = NO(1)=O(N1)=O(N)	тело цикла F в худшем случае выполняется N раз
G	2	Нц	O(G)=О(H) = О(1)	Тело цикла G состоит из действия H. Сложность вычисляется как сложность блока H
H	1	y=y*x;	О(H)=О(1)	Сложность вычислительного действия константная
		Кц;
I	4	s=s+y;	O(I)=O(1)	Сложность вычислительного действия константная
		Кц
K	9	Вывод(s);	O(K)=O(1)	Сложность вычислительного действия константная
		Конец

Оценим его сложность.

О(H)=О(1)

O(G)=О(H) = О(1)

O(F)=N* O(G) = N*O(1)=O(N*1)=O(N)

O(I)=O(1); О(E)=О(1)

O(D)=О(E+ F+I) = О(1)+ О(N)+О(1)= О(N)

O(C)=N* O(D) = N*O(N)=O(N*N)=O(N²)

O(B)=O(1); O(K)=O(1)

O(A)=O(B+C+K)= О(1)+ О(N²)+О(1)= O(N²)

4. Выводы.

При использовании вложенных циклов получена квадратичная сложность O(N²).

Можно ли улучшить эффективность алгоритма, понизив порядок его сложности?

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

Улучшенный псевдокод алгоритма.

Алгоритм Сумма_ряда(N,x)

A Начало

B s=1;

C Для k от 1 до N с шагом 1

D Нц

E Y=y*x;

F s=s+y;

Кц

G Вывод s;

Конец

О(D)=O(E+F)=О(1)+О(1)=О(1)

О(C)=N*О(D)= N*О(1)= О(N*1)= О(N)

O(A)=O(B)+O(C)+O(G)=О(1)+ О(N)+О(1)= О(N)

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

5. КРИТЕРИИ ОЦЕНКИ КОНТРОЛЬНОЙ РАБОТЫ

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

Задания контрольной работы разделены на три блока А, В и С, которые содержат задачи различных тем раздела разного уровня сложности. Блок А содержит задачи по теме 1 «Основные модели алгоритмов», блок В – по теме 2 «Методы построения базовых алгоритмов», блок С - по теме 3 «Методы вычисления сложности алгоритмов». Решение задач блока В требует больших затрат по времени, чем решение задач из блока А из-за повышения степени их сложности. В задачах блока С требуется оценить сложность алгоритма.

Решение любой задачи включает в себя следующие обязательные части:

1. Анализ задачи;

2. Определение вида алгоритма;

3. Выбор и обоснование используемых алгоритмических структур;

4. Составление блок-схемы алгоритма решения задачи в автоматизированной среде проектирования;

5. Разработка псевдокода алгоритма (только для задач блока С);

6. Вычисление сложности алгоритма (только для задач блока С);

7. Анализ эффективности алгоритма, рекомендации по понижению порядка сложности алгоритма (только для задач блока С);

8. Оформление результатов в виде текстового файла.

По результатам контрольной работы проводится оценка знаний и умений, полученных при изучении раздела дисциплины, с помощью балльно-рейтинговой системы оценивания. Каждая задача контрольной работы имеет рейтинг в баллах. Для каждого блока задач установлен свой рейтинг оценки выполненных заданий (за отдельную задачу) (таблица 1). Задачи блока А оцениваются максимально 1 баллом, блока В – 1,5 баллами, блока С – 2 баллами. Баллы за задачу начисляются по объективным и субъективным критериям (последние обозначены * в таблице 5.1).

Таблица 5.1 Итоговая рейтинговая таблица выполнения контрольной работы

Объекты оценки	Критерии оценки результата	Рейтинг в баллах
Объекты оценки	Критерии оценки результата	А (1)	В (1,5)	С (2)
Знание основных моделей алгоритмов Знание методов построения алгоритмов Умение разрабатывать алгоритмы для конкретных задач Умение использовать программы для графического отображения алгоритмов Знание методов вычисления сложности работы алгоритмов Умение определять сложность работы алгоритмов	Выбор модели алгоритма для решения задачи обоснован верно	0,1	0,2	0,2
	Алгоритмические конструкции использованы обосновано	0,1	0,2	0,2
	Описание алгоритма обработки данных выполнено на языке графических спецификаций в соответствии с нормативно-технической документацией (стандартом ГОСТ 19.701-90)	0,1	0,2	0,2
	Описание алгоритма с помощью псевдокода выполнено верно			0,2
	Логика выполнения алгоритма соответствует его целевому назначению	0,1	0,2	0,2
	Результат выполнения алгоритма соответствует условию задачи при выполнении тестов в полной мере (минус 0,1 балл за каждый неправильный тест блока А, 0,2 балла – блоков В и С)	0,3	0,4	0,4
	*Описание алгоритма выполнено наглядно и компактно	0,05	0,05	0,05
	*Разработка алгоритма выполнена оптимальным образом	0,1	0,1	0,1
	Описание алгоритма обработки данных выполнено верно с использованием средств автоматического проектирования алгоритмов	0,1	0,1	0,1
	Продемонстрировано умение импортировать результаты автоматического проектирования при оформлении документации	0,05	0,05	0,05
	О-функции и правила вычисления сложности алгоритма применены обоснованно			0,1
	Класс сложности алгоритма определен верно			0,1
	Рекомендации по понижению порядка сложности алгоритма указаны верно			0,1

Итоговая оценка за контрольную работу выставляется на основании рейтинговой таблицы оценки результатов (табл. 5.2).

Таблица 5.2 Шкала итоговых оценок по контрольной работе (максимальный рейтинг - 16 баллов)

Оценка	Сумма баллов	Пояснение оценок
отлично	>12	Знания и умения по разделу освоены полностью, без пробелов, большая часть предусмотренных программой обучения учебных заданий выполнено, качество их выполнения высокое
хорошо	10-12	Знания и умения по разделу освоены полностью, большая часть предусмотренных программой обучения учебных заданий выполнено, качество их выполнения достаточно высокое
удовлетворительно	6-9,95	Знания и умения по разделу освоены частично, но пробелы не носят существенного характера, часть предусмотренных программой обучения учебных задач выполнено, в них имеются ошибки
неудовлетворительно	<6	Знания и умения по разделу не освоены, большинство предусмотренных программой обучения учебных задании не выполнено, качество их выполнения оценено числом баллов, близким к минимальному

6. КОНТРОЛЬНАЯ РАБОТА ПО РАЗДЕЛУ «ОСНОВЫ АЛГОРИТМИЗАЦИИ»

Уважаемый студент! Вам предлагаются задачи для самостоятельного выполнения. Задания контрольной работы разделены на три блока А, В и С, которые содержат задачи различных тем раздела разного уровня сложности. Блок А содержит задачи по теме 1 «Основные модели алгоритмов», блок В – по теме 2 «Методы построения базовых алгоритмов», блок С - по теме 3 «Методы вычисления сложности алгоритмов». Решение задач блока В требует больших затрат по времени, чем решение задач из блока А из-за повышения степени их сложности. В задачах блока С требуется оценить сложность алгоритма.

Критерии оценивания контрольной работы приведены в файле Критерии оценки. Для получения удовлетворительной оценки по контрольной работе Вам достаточно набрать больше 6 баллов, а это означает, что выполнять все задачи не требуется, достаточно правильно выполнить две из блока А и две из блока В или все задачи блока С. Учитывайте, что баллы за задачу начисляются по критериям, поэтому если какой-то из критериев не будет выполнен, Вы не получите за задачу максимальный итоговый балл, который она имеет. Поэтому, если Вы не уверенны в правильности решения задачи, лучше выполнить большее количество заданий.

Решение любой задачи включает в себя следующие обязательные части:

1. Анализ задачи;

2. Определение вида алгоритма;

3. Выбор и обоснование используемых алгоритмических структур;

4. Составление блок-схемы алгоритма решения задачи в автоматизированной среде проектирования;

5. Разработка псевдокода алгоритма (только для задач блока С);

6. Вычисление сложности алгоритма (только для задач блока С);

8. Оформление результатов в виде текстового файла.

Ход решения задачи:

1. Провести анализ задачи;

2. Определить вид алгоритма (линейный, разветвленный, циклический, комбинированный);

3. Выделить алгоритмические конструкции, используемые для реализации алгоритма;

4. Описать алгоритм задачи в виде псевдокода в текстовом файле с именем КР_Задание1;

5. Разработать блок-схему алгоритма, используя автоматизированное программное средство FCEditor;

6. Сохранить блок-схему в виде графического файла с расширением jpeg, bmp и др.

7. Вставить рисунок из файла (пункт 6) в текстовый файл КР_Задание1. doc

:þ Задачи для самостоятельного выполнения (по уровням)

Уровень А. Разработать блок-схему алгоритма решения следующих задач

Задание 1

Даны действительные числа x, y, z. Получить max( x,y*z, x²).

Задание 2

Вычислить сумму членов ряда: .

Задание 3

Гражданин 1 марта открыл счет в банке, вложив 1000 руб. Через каждый месяц размер вклада увеличивается на 2% от имеющейся суммы. Определить за какой месяц величина ежемесячного увеличения вклада превысит 30 руб.; через сколько месяцев размер вклада превысит 1200 руб.

Задание 4

Найти все натуральные числа, а, в, с из интервала от 1 до 20, для которых выполняется равенство: а + в = с².

Уровень B. Разработать блок-схему алгоритма решения следующих задач

Задание 5

Дан одномерный массив размерности N (N вводит пользователь). Заменить все его элементы, стоящие после минимального на нуль.

Задание 6

Дан одномерный массив размерности N (N вводит пользователь). Поменять местами в массиве максимальный элемент и первый.

Задание 7

Дан двумерный массив размерности NхM (N,M вводит пользователь). Определите число ненулевых элементов в каждой строке массива.

Задание 8

Дан двумерный массив размерности NхN (N вводит пользователь). Поменять знак у всех элементов главной диагонали массива.

Уровень С. Разработать псевдокод алгоритма. Вычислить сложность алгоритмов. Дать рекомендации по улучшению эффективности алгоритма, если это возможно

Задание 9

Дано целое число а и натуральное (целое неотрицательное) число n. Разработать алгоритм вычисления а в степени n. Произвести анализ сложности алгоритма.

Задание 10

Оценить сложность алгоритма, вычисляющего сумму ряда: 1/0!+1/1!+...+1/n! , где n - натуральное число

Задание 11

Оценить сложность алгоритма, печатающего квадраты всех натуральных чисел от 0 до заданного натурального n.

СПИСОК РЕКОМЕНДОВАННЫХ ИСТОЧНИКОВ

1. Основная литература

1.1.Колдаев, В.Д. Основы алгоритмизации и программирования: Учебное пособие / В.Д. Колдаев. - М.: Форум, 2019. - 414 c.

1.2.Семакин, И.Г. Основы алгоритмизации и программирования: Учебник / И.Г. Семакин. - М.: Academia, 2017. - 384 c.

1.3.Семакин, И.Г. Основы алгоритмизации и программирования. Практикум: Учебное пособие / И.Г. Семакин. - М.: Academia, 2017. - 224 c.

1.4.Серкова, Е.Г. Основы алгоритмизации и программирования: практикум / Е.Г. Серкова. - РнД: Феникс, 2019. - 189 c.

1.5.Трофимов, В. В. Алгоритмизация и программирование. — М.: Издательство Юрайт, 2017. — 137 с.

2. Дополнительная литература

2.1.Абрамов С.А. Лекции о сложности алгоритмов. – М: МЦНМО, 2012. - 256 с.

2.2.Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. – 360 с.

2.3.Кнут Дональд Э. Искусство программирования. В 3-х томах. Пер. с англ./ Дональд Э. Кнут. – 3-е изд. – М.: Вильямс, 2006.-Т.1.: Основные алгоритмы. -720 с.

2.4.Кнут Дональд Э. Искусство программирования. В 3-х томах. Пер. с англ./ Дональд Э. Кнут. – 3-е изд. – М.: Вильямс, 2007.-Т.2.: Полученные алгоритмы.-832 с.

2.5.Кнут Дональд Э. Искусство программирования. В 3-х томах. Пер. с англ./ Дональд Э. Кнут. – 3-е изд. – М.: Вильямс, 2007.-Т.3.: Сортировка и поиск. -824 с.

Электронные издания (электронные ресурсы)

1. Иванова Г.С. Технология программирования (для бакалавров). – 3-е изд., ЭБС для СПО, вузов и библиотек — Book.ru ©–2019

Учебные материалы

- Комплект теоретических материалов (Students (\\oat.local) (S:)\Обучение\09.02.07\Основы алгоритмизации и программирования\Теория);

- Комплект методических рекомендаций для выполнения лабораторных работ (Students (\\oat.local) (S:)\Обучение\09.02.07\Основы алгоритмизации и программирования\Практикум).

Интернет- и интранет-ресурсы

- Библиотека учебных курсов Microsoft [Электронный ресурс].- Режим доступа: http://msdn.microsoft.com/ru-ru/gg638594, свободный.

- Библиотека учебных курсов/ Интернет-Университет информационных технологий - Интуит (Национальный Открытый университет) [Электронный ресурс]. - Режим доступа: http://old.intuit.ru/catalog/, свободный.

- Единая система программной документации [Электронный ресурс]. - Режим доступа: http://prog-cpp.ru/espd/, свободный.

Скачать материал

Скачать материал "Учебное пособие "Основы алгоритмизации""

Как учитель может зарабатывать на Инфоуроке?

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 660 073 материала в базе

Найти материалы

Скачать материал

Другие материалы

docx

Статья «Интеграция информатики с другими дисциплинами как средство повышения познавательного интереса обучающихся»

22.11.2019
113
0

docx

Методические указания по выполнению курсовой работы МДК 05.01 Технологии и средства разработки корпоративных систем

22.11.2019
719
2

docx

Задания по информатике по теме «Найти и заменить»

Учебник: «Информатика», Босова Л.Л., Босова А.Ю.
Тема: Глава 4. Обработка текстовой информации

22.11.2019
1443
7

pptx

Презентация открытого урока по информатике на тему: "Компьютерные сети"

Учебник: «Информатика (углублённый уровень) (в 2 частях)», Семакин И.Г., Шеина Т.Ю., Шестакова Л.В.
Тема: Глава 4. Компьютерные телекоммуникации

22.11.2019
959
17

«Информатика (углублённый уровень) (в 2 частях)», Семакин И.Г., Шеина Т.Ю., Шестакова Л.В.

pptx

Презентация по информатике на тему " Роль информационной деятельности в современном обществе"

Учебник: «Информатика. Углубленный уровень (в 2-ух частях) », Поляков К.Ю., Еремин Е.А.
Тема: § 1. Информатика и информация

Рейтинг: 5 из 5

22.11.2019
867
18

«Информатика. Углубленный уровень (в 2-ух частях) », Поляков К.Ю., Еремин Е.А.

docx

Рабочая программа учебной дисциплины ОП. 01 Операционные системы и среды

22.11.2019
479
10

docx

Организация самостоятельной работы на уроках информатики

22.11.2019
559
3

docx

Дополнительная общеобразовательная общеразвивающая программа технической направленности «Мультстудия»

22.11.2019
1891
87

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Скачать материал
- 22.11.2019 5416
- DOCX 987 кбайт
- 106 скачиваний
- Оцените материал:
Настоящий материал опубликован пользователем Бабикова Татьяна Михайловна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Автор материала

Бабикова Татьяна Михайловна
- На сайте: 8 лет и 9 месяцев
- Подписчики: 0
- Всего просмотров: 15951
- Всего материалов: 10