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

Обновлено: 05.07.2024

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

Содержание

Прикрепленные файлы: 1 файл

курсовая.docx

Московский государственный открытый университет

Чебоксарский политехнический институт

Кафедра информационных технологий и программирования

по дисциплине: Структура и алгоритм обработки данных

Студент 2-го курса

Проверила: Замкова Т.В.

г. Чебоксары, 2013

Деревья и их приминения10

Применение и особенности деревьев 12

Пример программы на языке C++15

Обход графа в ширину. Применение.17

Основные понятия 17

Описание графов 18

Процедура поиска в ширину 18

Пример программы на языке C++20

Список использованной литературы.25

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

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

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

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

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

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

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

Распределение памяти имеет ключевое значение для эффективного использования двусвязных списков. Как только возникает необходимость использовать новый узел, для него следует зарезервировать память. При объявлении переменной типа node для нее резервируется память во время компиляции. Однако часто приходится организовать вычисления, связанные с резервированием памяти во время выполнения, посредством вызовов системных операторов управления памятью. Например в строке кода

link x = new node;

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

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

Каждая ячейка двусвязного списка содержит в поле связей два указателя адреса. Первый указывает на следующую ячейку, а второй на предыдущую.
В качестве примера на рисунке ниже представлен двусвязный список, составленный из четырёх ячеек, которые содержат элементы A, B, C и D.

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

Urm, Prec : AdresaCelula;

var P, V : AdresaCelula;

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

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

Лекции

Лабораторные

Справочники

Эссе

Вопросы

Стандарты

Программы

Дипломные

Курсовые

Помогалки

Графические

Доступные файлы (1):

1.docx

2 Практическая часть 9

Библиографический список 12

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

^ Элементы жадной стратегии

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

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

^ Свойство жадного выбора

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

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

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

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

^ Оптимальная подструктура

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

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

^ Алгоритм Хаффмена

Однозначно расшифровывалась;
Имела минимальную длину.

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

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

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

Теперь можно сформулировать сам алгоритм Хаффмена.

Его первая часть сводит задачу к задаче кодирования алфавита с двумя символами.

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

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

^ Упорядочить буквы в порядке убывания частот

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

^ КОНЕЦ ЦИКЛА

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

Сопоставить первой букве код 0, второй – код 1

ПОКА не все исходные буквы получили двоичные коды

^ ЕСЛИ буква получена слиянием двух других, сопоставить им коды, полученные добавлением 0 или 1 к коду расщепляемой буквы.

КОНЕЦ ЦИКЛА
^

2 Практическая часть

Дан неупорядоченный массив целых чисел размером N. Рассчитать вычислительную сложность алгоритма для заданного метода сортировки для N=5. Метод сортировки – сортировка вставками.

^ Сортировка вставками

Сортировка вставками похожа на процесс тасования карточек с именами. Регистратор заносит каждое имя на карточку, а затем упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее место. Опишем этот процесс на примере нашего пятиэлементного списка A = 50, 20, 40, 75, 35 (рисунок 1).

Рисунок 1 – Процесс сортировки вставками

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

первую последовательность так, чтобы она оставалась отсортированной. Поиск места вставки осуществляют с конца, сравнивая вставляемый элемент а_i с очередным элементом отсортированной последовательности a_j. Если элемент a_i больше a_j, его вставляют вместо a_j+1, иначе сдвигают a_j вправо и уменьшают j на единицу. Поиск места вставки завершают, если элемент вставлен или достигнут левый конец массива. В последнем случае элемент a_i вставляют на первое место.

^ Вычислительная сложность сортировки вставками

Сортировка вставками требует фиксированного числа проходов. На n-1 проходах вставляются элементы от A[1] до A[n-1]. На i-ом проходе вставки производятся в подсписок A[0]–A[i] и требуют в среднем i/2 сравнений. Общее число сравнений равно 1/2 + 2/2 + 3/2 + . + (n-2)/2 + (n-1)/2 = n(n-1)/4.

В отличие от других методов, сортировка вставками не использует обмены. Сложность алгоритма измеряется числом сравнений и равна O(n 2 ). Наилучший случай – когда исходный список уже отсортирован. Тогда на i-ом проходе вставка производится в точке A[i], а общее число сравнений равно n-1, т.е. сложность составляет O(n). Наихудший случай возникает, когда список отсортирован по убыванию. Тогда каждая вставка происходит в точке A[0] и требует i сравнений. Общее число сравнений равно n(n-1)/2, т.е. вычислительная сложность алгоритма составляет O(n 2 ).

В лучшем случае – 5;
В худшем случае – 25.

Библиографический список

2 Новиков Ф.А., Поздняков С.Н. Компьютерные инструменты в образовании, №2. – Заочная школа современного программирования, 2005. – 58с.

Теоретическая часть - "Жадные алгоритмы".
Элементы жадной стратегии.
Свойство жадного выбора.
Оптимальная подструктура.
Алгоритм Хаффмена.
Практическая часть - расчет вычислительной сложности алгоритма сортировки методом вставок.
10стр.

Асанов М.О., Расин В.В. Комбинаторные алгоритмы

формат pdf
размер 1 МБ
добавлен 21 ноября 2010 г.

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

Дроздов С. Комбинаторные задачи и элементы теории вычислительной сложности

формат doc
размер 140.3 КБ
добавлен 23 мая 2007 г.

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы

формат doc
размер 7.54 МБ
добавлен 06 апреля 2010 г.

Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: Построение и анализ, 1-е издание

формат zip
размер 3.67 МБ
добавлен 07 июня 2010 г.

1-е издание, 1990. — 893 с.: ил. Фундаментальный труд известных специалистов в области кибернетики достоин занять место на полке любого человека, чья деятельность так или иначе связана с информатикой и алгоритмами. Для профессионала эта книга может служить настольным справочником, для преподавателя — пособием для подготовки к лекциям и источником интересных нетривиальных задач, для студентов и аспирантов — отличным учебником. Каждый может найти.

Кузюрин Н.Н. Фомин С.А. Сложность комбинаторных алгоритмов. Курс лекций

формат pdf
размер 1.62 МБ
добавлен 21 февраля 2011 г.

Московский физико-технический институт. 2007 г. 135 стр. Элементы теории сложности Несложно о сложности. Примеры алгоритмов Формально об алгоритмах Сложность алгоритмов Вероятностные вычисления Вероятностно проверяемые доказательства Схемы и схемная сложность Коммуникационная сложность Диаграмма классов сложности Приближенные алгоритмы с гарантированными оценками точности Приближенные алгоритмы с фиксированными оценками точности Приближенные алго.

Курсовая работа - Теория алгоритмов. Разработка эффективных алгоритмов

формат doc
размер 1.16 МБ
добавлен 09 сентября 2011 г.

Содержание Введение: Актуальность темы Понятие алгоритма Признаки алгоритмов Структуры данных и их представление в памяти ЭВМ Эффективность алгоритмов и методы её достижения Форма алгоритмов Эффективность алгоритмов Машина Тьюринга Краткое содержание курсовой работы Разработка эффективных алгоритмов: Типы алгоритмов Линейный алгоритм Задание 1 Алгоритмы разветвляющейся структуры Задание 2 Циклические вычислительные процессы Задание 3 Словесн.

Лекции - Теория алгоритмов

формат pdf
размер 43.93 МБ
добавлен 04 февраля 2012 г.

Автор не известен. 136 с. Лекции в виде презентации. Содержание. - Алгоритмы в математике. Основные черты алгоритмов. Числовые функциии алгоритмы их вычисления. Примитивно рекурсивные функции. - Частично рекурсивные функции.Тезис Черча. - Машины Тьюринга и машины с неограниченными регистрами. Вычислимость частично рекурсивных функций на МНР. - Нумерации и универсальные функции. - Нормальные алгорифмы. - Алгоритмические проблемы в логике и матем.

Скиена С. Алгоритмы. Руководство по разработке

формат djvu
размер 10.81 МБ
добавлен 16 января 2012 г.

2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург. 2011. — 720 с.: ил. Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбин.

В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в определенном порядке. Часто при сортировке больших объемов данных нецелесообразно переставлять сами элементы, поэтому длярешения задачи выполняется упорядочивание элементов по индексам. То есть индексы элементов выстраивают в такой последовательности, что соответствующие им значения элементов оказываются отсортированными поусловию задачи.
Сортировка применяется для облегчения поиска элементов в упорядоченном множестве. Задача сортировки одна из фундаментных в программировании.
Сортировка – это упорядочивание набораоднотипных данных по возрастанию или убыванию.
Чаще всего при сортировке данных лишь часть их используется в качестве ключа сортировки. Ключ сортировки – это часть данных, определяющая порядокэлементов. Таким образом, ключ участвует в сравнениях, но при обмене элементов происходит перемещение всей структуры данных. Например, в списке почтовой рассылки в качестве ключа может использоватьсяпочтовый индекс, но сортируется весь адрес. При решении задач сортировок массивов ключ и данные совпадают.
Оценка алгоритмов сортировки
Существует множество различных алгоритмов сортировки. Всеони имеют свои положительные и отрицательные стороны. Перечислим общие критерии оценки алгоритмов сортировки.
Скорость работы алгоритма сортировки. Она непосредственно связана с количествомсравнений и количеством обменов, происходящих во время сортировки, причем обмены занимают больше времени. Сравнение происходит тогда, когда один элемент массива сравнивается с другим; обмен происходит тогда,когда два элемента меняются местами. Время работы одних алгоритмов сортировки растет экспоненциально, а время.

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

Связанные рефераты

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

. курсовому проекту по дисциплине: Алгоритмы и структуры.

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

. Контрольная работа по предмету «Структуры и алгоритмы обработки.

9 Стр. 2 Просмотры

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

. Алгоритм Дейкстра. Алгоритм Дейкстры решает задачу о кратчайших путях из.

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

. | |по дисциплине «Структуры и алгоритмы обработки.

5 Стр. 44 Просмотры

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

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

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

Выбранный для просмотра документ Алгоритмические структуры Реферат.doc

МОУ Нижнеингашская средняя общеобразовательная школа №2

по информатике на тему:

Выполнила: Нерушкина Е. В.

Проверила: Алексеева О.В.

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

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

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

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

Список используемой литературы

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

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

Решение любой задачи включает в себя следующие этапы:

Запись на формальном языке.

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

Цели моей работы:

дать понятие алгоритма;

провести классификацию алгоритмических структур на основе диалектической логики;

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

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

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

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

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

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

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

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

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

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

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

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

словесная (записи на естественном языке);

графическая (изображения из графических символов);

Цикл с параметром

программная (тексты на языках программирования).

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

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

Найти скорость, если известна масса и ускорение.

m , a Находим скорость с помощью формулы

второго закона Ньютона.

Условие – высказывание, которое может быть либо истинным, либо ложным.

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

Если пошел дождь, то надо открыть зонтик.

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

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

Условные выражения могут быть простыми и сложными . Простое условие включает в себя два числа, две переменных или два арифметических выражения, которые сравниваются между собой с использованием операций сравнения (больше, меньше, равно и пр.). Например, 5>3, 2*8=4*4)

Сложное условие – это последовательность простых условий, объединенных между собой знаками логических операций. Например, 5>3 and 2*8=4*4 и т.д.

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

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

Полный разветвляющийся алгоритм

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

а, b 1.Сравнить два числа.

Найти: 2.Записать большее.

m (большее из а и b )

Вывод m

If a > b Then m = a Else m = b’ ( реализация полной развилки ( формы ))

Неполный разветвляющийся алгоритм

Вычислите значения составной функции.

y = - x , при 0 x ≤ 4

Rem «Вычисление значения составной функции

If x ≤ 0 Then y = x 3

If 0 x ≤ 4 Then y = x (реализация неполной развилки)

If x > 0 Then y = 4

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

Циклический алгоритм – алгоритм с условием, в котором действия повторяются многократно.

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

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

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

Алгоритм с предусловием

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

Найдите наибольший общий делитель, с помощью алгоритма Евклида.

х, y Пока два числа не равны, большее

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

Найти: и меньшего. Когда числа станут равны.

НОД Любое из них можно считать НОД-ем.

If x>y Then x=x-y Else y=y-x

Найти факториал числа.

Факториал числа – это произведение

N натуральных чисел от 1 до этого числа.

Найдем факториал по определению.

Алгоритм с постусловием

Найдите наибольший общий делитель, с помощью алгоритма Евклида.

х, y Делим большее число на меньшее с

остатком и заменяем его на получен-

ный остаток до тех пор пока остаток

не станет равным нулю. НОД-ем будет

Найти: являться последний остаток не равный

If x>y Then x=x mod y Else y=y mod x

Loop Until x=0 or y=0

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

Бросок левой – подбросить мяч левой рукой.

Бросок правой – подбросить мяч правой рукой.

Захват левой – поймать мяч левой рукой.

Захват правой – поймать мяч правой рукой.

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

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

Найдите большее из трех чисел.

а, b , с Сравнить первые два числа. Выбрать

большее. Теперь это большее

Найти: М сравнить с третьим числом. Выбрать

(большее) большее. Записать ответ.

If x > y Then M = x Else M = y

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

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

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

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

запись программы на языке программирования QBasic .

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

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

Информатика и информационные технологии. Учебник для 10-11 классов/ Н.Д. Угринович. – 2-е изд. – М.: БИНОМ. Лаборатория знаний, 2005. – 511 с.: ил. ISBN 5-94774-189 –X

Информатика. 7-9 класс. Базовый курс. Теория. / Под ред. Н.В. Макаровой. – СПб.: Питер, 2003. – 368с.: ил. ISBN 5-273-00186-9

Энциклопедия для детей. Том 22. Информатика/Глав.ред. Е.А. Хлебалина, вед.науч.ред. А.Г. Леонов. – М.: Аванта+, 2003. – 625с.:ил. ISBN 5-94623-040-9 ?ISBN 5-94623-001-8

Бейсик и Паскаль в вопросах и задачах.(Рабочая тетрадь 2) Житкова О.А., Кудрявцева Е.К. – М. Интеллект Центр. 2001 80 с.

Информатика. 5-6 класс. Начальный курс. / Под ред. Н.В. Макаровой. – СПб.: Питер, 2002. – 160с.: ил. ISBN 5-272-00129-Х

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

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

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

I . По порядку выполнения действий:

1. Алгоритм, в котором команды выполняются однократно одна за другой.

2. Описание действий, которые выполняются однократно в заданном порядке.

3.Алгоритм, в котором команды выполняются одна за другой.

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

По наличию условия:

Алгоритм с условием;

Алгоритм без условия (Вспомогательный алгоритм).

Алгоритм с условием

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

По количеству проверок:

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

По наличию действия при ложном значении условия:

1.1. Полный разветвляющийся алгоритм;

1.2. Неполный разветвляющийся алгоритм.

Полный разветвляющийся алгоритм

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

Неполный разветвляющийся алгоритм

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

1. Описание действий, которые должны повторяться указанное число раз, или пока не выполнено заданное условие.

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

I . По расположению команды проверки условия:

1.1. Циклический алгоритм с предусловием;

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

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

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

I . По виду команды:

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

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

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

Вспомогательный алгоритм (Подпрограмма, процедура)

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

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

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

Данный сборник понятий составлен

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

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

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

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

Читайте также: