шпаргалка по алгоритмизации. алгоритмы_ответы. 1 Понятие алгоритма и программы. Свойства и формы записи алгоритмов
 Скачать 320.13 Kb.
|
|
1)Понятие алгоритма и программы. Свойства и формы записи алгоритмов. Алгоритм – это последовательность действий для решения какой-либо задачи, приводящая от исходных данных к результату за конечное число шагов. Свойства алгоритмов: 1) Дискретность (делится на шаги) 2) Массовость (примитивность) 3)Определенность(каждый шаг должен быть определен) 4)Результативность(должен завершиться) Формы представления алгоритмов: 1) словесная форма (запись на естественном языке) 2) графическая (в виде блок- схем) 3) псевдокоды ( описание алгоритма на условном алгоритмическом языке4) программная (на языке программирования) 5)Алгоритм циклической структуры с известным количеством повторений Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называют телом цикла. Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз; Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. 13)Алгоритмов сортировки методом «пузырька» Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает – массив отсортирован. При проходе алгоритма элемент, стоящий не на своём месте, "всплывает" до нужной позиции 2)Разновидности структур алгоритмов. Различают следующие структуры алгоритмов: 1)линейные; Линейный – алгоритм, в кот-ом команды выполняются последовательно друг за другом в порядке их естественного следования независимо от каких- либо условий. 2)разветвляющиеся; Разветвляющийся вычислительный процесс – это процесс, в котором направление вычислений определяется некоторыми условиями. 3)циклические. Циклический вычислительный процесс – процесс, в котором отдельные участки вычислений выполняются многократно. 6)Алгоритм циклической структуры с неизвестным количеством повторений. Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называют телом цикла. Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз; Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. 15)Алгоритмы поиска. Бинарный поиск. Под алгоритмами поиска понимае тся процесс просмотра списка в поисках некоторого конкретного элемента, называемого целевым. Двоичный (бинарный) поиск — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. 16)Рекурсивная реализация алгоритмов Рекурсией называется такой способ организации обработки данных, при котором программа (или функция) вызывает сама себя или непосредственно, или из других программ (функций). Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций. 3)Алгоритм линейной структуры. Линейный – алгоритм, в кот-ом команды выполняются последовательно друг за другом в порядке их естественного следования независимо от каких- либо условий. 7)Итерационные циклы. Вложенные циклы Итерационный цикл — это цикл, для которого число повторений тела цикла заранее неизвестно. Если в теле одного цикла имеется другой цикл, то такая структура алгоритма называется вложенными циклами. 8)Алгоритм циклической структуры с параметром и вложенные циклы. Циклическим называется алгоритм, который содержит участок, выполняющийся многократно, каждый раз с новыми значениями переменных, изменяющихся по одним и тем же законам. По способу организации циклы делятся на два основных вида: циклы с известным заранее числом повторений (классические); циклы с неизвестным числом повторений (итерационные). 12)Алгоритм сортировки методом «выбора» Алгоритм сортировки методом выбора начинается со сравнения первых двух элементов массива и их замены в случае необходимости. Например, если вы хотите отсортировать элементы массива в порядке возрастания и если первый элемент больше второго, вам нужно поменять местами элементы. Но, если первый элемент меньше второго, элементы остаются в своей последовательности. Затем снова первый элемент и третий элемент сравниваются и меняются местами, если это необходимо. Этот процесс продолжается до тех пор, пока не будет сравнен первый и последний элемент массива. Это завершает первый шаг выбора сортировки. 4)Общие принципы построения разветвленных алгоритмов Ветвление — метод и форма организации действий, когда в зависимости от выполнения определённого условия совершается та либо иная последовательность шагов. 9) Понятие структуры данных «Массив». Массив — это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элемента в массиве Элемент массива — отдельная переменная, входящая в массив Индекс элемента массива — номер элемента в этом массиве. 11)Алгоритм сортировки методом «вставок» Общая суть сортировок вставками такова: Перебираются элементы в неотсортированной части массива. Каждый элемент вставляется в отсортированную часть массива на то место, где он должен находиться. То есть, сортировки вставками всегда делят массив на 2 части — отсортированную и неотсортированную. Из неотсортированной части извлекается любой элемент. Поскольку другая часть массива отсортирована, то в ней достаточно быстро можно найти своё место для этого извлечённого элемента. Элемент вставляется куда нужно, в результате чего отсортированная часть массива увеличивается, а неотсортированная уменьшается. Всё. По такому принципу работают все сортировки вставками. 18)Понятие структуры данных «хеш-таблицы». Алгоритмы работы с «хеш- таблицы» Хеш-таблица — это структура данных для хранения пар ключей и их значений. По сути она представляет собой массив, где местоположение элемента зависит от значения самого элемента. Связь между значением элемента и его позицией в хеш-таблице задает хеш-функция. Важное свойство хеш-таблицы: поиск, вставка и удаление элементов из таблицы выполняются за фиксированное время, то есть О(1), то есть они нужны тогда, когда максимально важна скорость этих операци 21)Нотация большого О: определение и применение для вычисления временной сложности алгоритмов. Нотация «О» большое описывает, как возрастает предположительное время работы алгоритма по мере увеличения размера решаемой задачи. 19)Понятие структурой данных «стек». Алгоритмы работы со структурой данных «стек». Стек (от англ. stack — стопка) — структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» 20)Понятие структурой данных «очередь». Алгоритмы работы со структурой данных «очередь». Очередь – структура данных типа «список», позволяющая добавлять элементы лишь в конец списка, и извлекать их из его начала. Она функционирует по принципу— «первым пришёл — первым вышел») 21)Понятие структуры данных «Связный список». Организация и работа со списком. Связный список (linked list) — это структура данных, в которой элементы линейно упорядочены, но порядок определяется не номерами элементов (как в массивах), а указателями, входящих в состав элементов списка и указывают на следующий элемент. У списка должна быть «голова» (первый элемент) и «хвост» (последний элемент). |