Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Блок-схема алгоритма).pdf

>>>print(factorial)

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

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

Начало

Ввод N

S=0

i от 1 до N

C=S/N

Ввод A[i]

Вывод С

S=S+A[i]

Конец

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

Существуют три вида циклов.

Это: цикл «До», цикл «Пока», цикл «для…»

Они все состоят из нескольких этапов. Это:

1. Подготовка цикла, в которую входят начальные присвоения;
2. Тело цикла – команды повторения цикла;
3. Условие – обязательная часть циклов «До» и «Пока».

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

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

Массив – это множество однотипных элементов, объединённых общим именем и занимающих в компьютере определённую область памяти. Количество элементов в массиве всегда конечно. В общем случае массив – это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип. Название регулярный тип (или ряды) массивы получили за то, что в них объединены однотипные (логически однородные) элементы, упорядоченные (урегулированные) по индексам, определяющим положение каждого элемента в массиве. В качестве элементов массива можно использовать любой тип данных, поэтому вполне правомерно существование массивов записей, массивов указателей, массивов строк, массивов и т.д. Элементами массива могут быть данные любого типа, включая структурированные. Тип элементов массива называется базовым. Особенностью языка Паскаль является то, что число элементов массива фиксируется при описании и в процессе выполнения программы не меняется. Элементы, образующие массив, упорядочены таким образом, что каждому элементу соответствует совокупность номеров (индексов), определяющих его местоположение в общей последовательности. Доступ к каждому отдельному элементу осуществляется путем индексирования элементов массива. Индексы представляют собой выражения любого скалярного типа (чаще целого), кроме вещественного. Тип индекса определяет границы изменения значений индекса. Для описания массива предназначено словосочетание array of (массив из).

Для работы с массивом как единым целым используется идентификатор массива без указания индекса в квадратных скобках. Массив может участвовать только в операциях отношения "равно", "не равно" и в операторе присваивания. Массивы, участвующие в этих действиях, должны быть идентичны по структуре, т. е. иметь одинаковые типы индексов и одинаковые типы компонентов. Например, если массивы А и В описаны как var А, В: array[1..20] of real; то применение к ним допустимых операций даст следующий результат: выражение результат А=В True, если значение каждого элемента массива А равно соответствующему значению элемента массива ВА<>В True, если хотя бы одно значение элемента массива А не равно значению соответствующего элемента массива ВА:=В все значения элементов массива В присваиваются соответствующим элементам массива А. Значения элементов массива В остаются неизменны.

Действия над элементами массива. После объявления массива каждый его элемент можно обработать, указав идентификатор (имя) массива и индекс элемента в квадратных скобках. Например, запись Mas [2], Vector Z[10] позволяет обратиться ко второму элементу массива Mas и десятому элементу массива Vector Z.

При работе с двумерным массивом указываются два индекса, с n-мерным массивом - n индексов. Например, запись Matr U[4,4] делает доступным для обработки значение элемента, находящегося в четвертой строке четвертого столбца массива Matr U. Индексированные элементы массива называются индексированными переменными и могут быть использованы так же, как и простые переменные. Например, они могут находиться в выражениях в качестве операндов, использоваться в операторах for, while, repeat, входить в качестве параметров в операторы Read, Read ln, Write.

Преимущество использования массивов.

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

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

Массив позволяет сохранять и манипулировать многими элементами данных посредством единственной переменной.

Кроме уменьшения общего числа различных имен переменных, которые

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

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

различных элементов массивов.

Объединяя массивы и циклы можно написать небольшое число

операторов, которые обрабатывают большой объем данных. Выполнение тех

же задач с использованием отдельных переменных может потребовать

написания сотен операторов.

Обработка двумерных массивов (матриц)

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

Ввод массива осуществляется построчно при помощи двух циклов. Пусть M — количество столбцов, N — количество строк. Элементы массива обозначим как mas[i,j], первый индекс — номер строки, второй — номер столбца.

ввод M,N

нц для i от 1 до N

нц для j от 1 до M

ввод mas[ i , j ]

кц

кц

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

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

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

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

Пример работы программы:

>>> print (fact(6))

720

>>>

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

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

Сложность рекурсивных вычислений. При относительной простоте написания, у рекурсивных подпрограмм часто встречается существенный недостаток – неэффективность. Так, сравнивая скорость вычисления чисел Фибоначчи с помощью итеративной и рекурсивной функции можно заметить, что итеративная функция выполняется почти «мгновенно», не зависимо от значения n. При использовании же рекурсивной функции уже при n=40 заметна задержка при вычислении, а при больших n результат появляется весьма не скоро.

Оценить сложность рекурсивных вычислений (количество рекурсивных вызовов) можно с помощью рекуррентных соотношений. 

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

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

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

Технология, называемая восходящим динамическим программированием (bottom-up dynamic programming) основана на том, что значение рекурсивной функции можно определить, вычисляя все значения этой функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения.

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

Нисходящее динамическое программирование(top down dynamic programming) – еще более простая технология. Она позволяет выполнять рекурсивные функции при том же количестве итераций, что и восходящее динамическое программирование. Технология требует введения в рекурсивную программу неких средств, обеспечивающих сохранение каждого вычисленного значения и проверку сохраненных значений во избежание их повторного вычисления.

Метод «разделяй и властвуй». Многие алгоритмы используют два рекурсивных вызова, каждый из которых работает приблизительно с половиной входных данных. Такая рекурсивная схема, по-видимому, представляет собой наиболее важный случай хорошо известного метода «разделяй и властвуй» (divide and conquer) разработки алгоритмов.

Избавление от рекурсий. Любой рекурсивный алгоритм может быть переписан без использования рекурсии. Заметим, что быстродействие алгоритмов при избавлении от рекурсии, как правило, повышается. Еще одной причиной чтобы избавиться от рекурсии является ограничение на объем хранимых программой локальных переменных и значений параметров одновременно выполняющихся процедур. При очень глубокой рекурсии этот объем возрастает, и программа перестает работать, выдавая ошибку «Stack overflow» (переполнение стека*).

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

Ранее, при описании циклов while и for мной были приведены примеры программ для вычисления значения факториала без использования рекурсии.

Индексный массив.

Индексный массив (в некоторых языках программирования также таблица, ряд)- именованный набор однотипных переменных, расположенных в памяти, непосредственно друг за другом (в отличие от списка), доступ к которым осуществляется по индексу. Индекс массива целое число, либо значение типа, приводимого к целому, указывающее на конкретный элемент массива.
В ряде скриптовых языков, например JavaScript, PHP, Ruby применяются также ассоциативные массивы, в которых переменные не обязаны быть однотипными, и доступ к ним не обязательно осуществляется по индексу. 
Количество используемых индексов массива может быть различным. Массивы с одним индексом называют одномерными, с двумя — двумерными и т.д. Одномерный массив нестрого соответствует вектору в математике, двумерный - матрице. Чаще всего применяются массивы с одним или двумя индексами, реже - с тремя, ещё большее количество индексов встречается крайне редко.

.

Приведем пример построения таблицы значений факториала в зависимости от n:

N = int(input())

Zfact = []

def fact(n):

if n == 0:

return 1

return fact(n-1)*n

for k in range(N+1):

print('Значение факториала ',fact(k))

Пример работы программы:

>>>7 #(ввод)

Значение факториала 1

Значение факториала 1

Значение факториала 2

Значение факториала 6

Значение факториала 24

Значение факториала 120

Стек* - область памяти, в которой хранятся локальные переменные и адреса возврата

Значение факториала 720

Значение факториала 5040

>>>