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

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

Содержание:

ВВЕДЕНИЕ

Немного о языке Python

Python это универсальный современный язык программирования высокого уровня, к преимуществам которого относят высокую производительность программных решений и структурированный, хорошо читаемый код. Синтаксис Питона максимально облегчен, что позволяет выучить его за сравнительно короткое время. Ядро имеет очень удобную структуру, а широкий перечень встроенных библиотек позволяет применять внушительный набор полезных функций и возможностей. ЯП может использоваться для написания прикладных приложений, а также разработки WEB-сервисов.
Python может поддерживать широкий перечень стилей разработки приложений, в том числе, очень удобен для работы с ООП функционального программирования.
Один из самых популярных интерпретаторов языка – CPython, написанный на Си. Распространяется эта среда разработки бесплатно по свободной лицензии. Интерпретатор поддерживает большинство популярных платформ.
Питон активно развивается. Примерно раз в 2 года выходят обновления. Важной особенностью языка является отсутствие таких стандартов кодировки как ANSI, ISO и некоторых других, они работают благодаря интерпретатору.

Реализация алгоритмов на Python

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

Эффективный алгоритм обработки ассоциативных массивов (поиска значений, добавления и удаления значений и ключей, сортировки и пр.) в значительной степени зависит от используемого языка программирования и определённых в этом языке типов и структур данных. Так, в языке программирования Basic ассоциативный массив образуется из нескольких согласованных одномерных массивов. В языке программирования Pascal для представления ассоциативных массивов используется структура данных «запись» (record). В Python для ассоциативных массивов определена специальная структура данных — словарь, но мы рассмотрим работу с ассоциативными массивами с помощью списков и функций работы со списками

Машина Тьюринга

Устройство машины Тьюринга

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

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

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

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (S)). Для каждой возможной конфигурации имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Алгоритмы и их понятия
Один из крупнейших специалистов по системному программированию Дональд Э. Кнут начинает серию своих книг «Искусство программирования для ЭВМ» с определения понятия алгоритма: «Понятие алгоритма является основным при составлении любого вида программ для ЭВМ… Помимо того, что алгоритм – не просто свод конечного числа правил, задающих последовательность выполнения операций при решении той или иной специфической задачи, он имеет еще и пять важных особенностей:

1) Конечность (финитность). Алгоритм всегда должен заканчиваться после конечного числа шагов.

2) Определенность. Каждый шаг алгоритма должен быть точно определен. Действия, которые необходимо произвести, должны быть строго и недвусмысленно определены в каждом возможном случае.
3) Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число. входных данных, т.е. величин, заданных ему до начала работы. Эти данные берутся из некоего конкретного множества объектов.

4) Вывод. Алгоритм имеет одну или несколько выходных величин, т.е. величин, имеющих вполне определенные отношения ко входным данным.

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

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

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

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

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

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

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

Глава I

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

Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритмы работы машины, двигателя и т.п.);

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

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

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

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

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

2) вычисление искомых величин по формулам;

3) вывод результатов из памяти на информационный носитель.

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

Пример 1. Составить алгоритм вычисления площади круга по формуле

Python 3.6.3 (v3.6.3:2c5fed8, Oct 3 2017, 18:11:49) [MSC v.1900 64 bit (AMD64)]on win32
Type "copyright", "credits" or "license()" for more inform
>>>Pi=3.14 #инициализация числа

>>>R=3.0 #задаем значение R

>>>S=Pi*R**2 #формула для вычисления площади круга

>>>S #вывод

28.259999999999998 #результат

>>>

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

1) такие описания не строго формализованы;

2) страдают многословностью записей;

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

Сначала с помощью функции (метода) numpy.zeros() создаётся двумерный массив (матрица), заполненный нулями, а потом вместо нулей подставляются реальные значения. Индексы элементов, так же как в строках, кортежах и списках, начинаются с 0 (первый — верхний левый — элемент матрицы в Python имеет индекс [0,0]). Оператор print выводит индексы очередного элемента матрицы, который нужно ввести.

Задача 1. Выполнить обработку элементов прямоугольной матрицы A, имеющей N строк и M столбцов. Найти среднее арифметическое элементов массива.

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

Дано:

n — количество строк в массиве;

m — количество столбцов в массиве;

A[i,j] — элемент массива;

i,j — индексы элемента массива.

Найти:

S — сумма элементов массива (сумма всех A[i,j] при всех i и j)

K — количество элементов в массиве (K = m∗n)

C — среднее арифметическое элементов массива (C = S/K)

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

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

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


Начало алгоритма	Ввод/вывод данных	Операция

Разветвление	Цикл	Ссылка

Соединитель	Комментарий	Конец алгоритма

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

Для примера 1 блок-схема будет выглядеть так:

начало

Инициализация константы Pi

Ввод переменной

S=Pi*R**2

Вывод S

конец

Псевдокод и программное представление алгоритма

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

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

Для примера 1 текст программы на «псевдоязыке» будет выглядеть так:

инициализация константы (Pi)

ввод переменной R

S=Pi*R**2

вывод S

На практике в качестве исполнителей алгоритмов используются специальные автоматы – компьютеры. Алгоритм для компьютера должен быть написан на «понятном» ему языке. Такой языке принято называть языком программирования, а запись алгоритма на таком языке – программой. Теперь мы можем написать полноценную программу. На языке Python программа для примера 1 будет выглядеть так:

Pi=3.14

R=float(input('Введите радиус круга '))

S=Pi*R**2

print ("Площадь круга равна: ", S)

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

Порядок разработки иерархической системы реализации алгоритмов

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

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

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

Условная конструкция. Этот блок включает проверку некоторого логического условия (Р), в зависимости от которого выполняется либо один (S1), либо другой (S2) операторы:

Блок обобщенного цикла. Этот блок обеспечивает многократное повторение выполнения оператора S пока выполнено логическое условие P

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

Глава II

Ветвление и операторы выбора

В решениях задач по алгоритмизации одним из важнейших элементов является так называемое «ветвление».

Начало

Ввод данных

Условие

Нет

Действия «нет»

Да

Действия «да»

Вывод

Конец

Если условие, указанное в блоке «Условие», выполняется, то далее производятся действия, соответствующие «ветви ДА», иначе выполняются действия, соответствующие «ветви НЕТ». Условия нужно составлять так, чтобы результат проверки любого условия допускал только два исхода – условие либо выполняется, либо не выполняется.

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

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

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

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

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

В языках программирования для обеспечения проверки условий используется специальный составной оператор IF («если»). В этом операторе указывается условие, которое нужно проверить, и действия для ветвей «ДА» и «НЕТ».

Начало

Ввод Данных

Условие 1

Условие 2

Действия «да» 1

Условие N

Действия «да» 2

Действия «да» N

Действия «Нет»

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

Конец

Пример 2. Можно ли из бревна, имеющего диаметр поперечного сечения D, выпилить квадратный брус шириной A?

Постановка задачи: Исходными данными является значение диаметр бревна R, и ширина бруса А. Максимальную ширину бруса для заданного диаметра бревна можно определить из формулы радиуса описанной возле квадрата со стороной А окружности: . Необходимо сформировать строку S. При . S="брус можно выпилить" иначе S="брус нельзя выпилить".

Текст программы на «псевдоязыке»:

ввод D

ввод A

из D получаем R=D/2

если ( ) то

S=”брус можно выпилить”

иначе

S=”брус нельзя выпилить”

конец если

вывод S (рис)

Начало

D , A

R = D/2

A <2*R

Нельзя

Можно

Конец

Текст на Python:

from math import sqrt

D=float (input("Введите диаметр бревна") )

R=D/2

a=float(input("Введите ширину бруса") )

if a<R*sqrt(2):

S="брус можно выпилить"

else:

S="брус нельзя выпилить"

print (S)

Пример 3. На том же примере 2 мы так же можем предоставить выбор единицы измерения: метр (“m”), или миллиметр (“mm”), для чего вводим флаг F.

Текст программы на «псевдоязыке»:

Ввод F

ввод D

ввод A

из D получаем R=D/2

если ( ) то

S=”брус можно выпилить”

иначе

S=”брус нельзя выпилить”

конец если

вывод S (рис)

Текст программы на Python:

from math import sqrt

F=input ("Какую единицу измерения хотите использовать? Введите m - метр, mm - миллиметр ")

D=float (input("Введите диаметр бревна "))

R=D/2

a=float(input("Введите ширину бруса "))

if a<R*sqrt(2):

if F=="m":

S=["брус шириной",a, "m", "можно выпилить "]

elif F=="mm":

S=["брус шириной",a, "mm","можно выпилить "]

else:

if F=="m":

S=["брус шириной",a, "m","нельзя выпилить "]

elif F=="mm":

S=["брус шириной",a, "mm", "нельзя выпилить "]

print (S[0],S[1],S[2],S[3])

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

Метры

Какую единицу измерения хотите использовать? Введите m - метр, mm - миллиметр m

Введите диаметр бревна 2

Введите ширину бруса 1

брус шириной 1.0 m можно выпилить

>>>

Миллиметры

Какую единицу измерения хотите использовать? Введите m - метр, mm - миллиметр mm

Введите диаметр бревна 200

Введите ширину бруса 160

брус шириной 160.0 mm нельзя выпилить

>>>

Операторы ввода-вывода

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

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

Рис. 5. Прямоугольный параллелепипед.

Площадь его поверхности: S = 2*(ab+ac+bc), (3)

где a, b, c - длина, ширина и высота параллелепипеда.

2.3 АЛГОРИТМ программы

Приведем текстовую интерпретацию алгоритма. Программа состоит из следующих шагов:

Шаг 1 - ввод исходных данных - параметров фигур.

Шаг 2 - открытие цикла с предусловием (while) по высоте шарового сегмента.

Шаг 3 - вычисление площади поверхности шарового сегмента и радиуса его основания.

Шаг 4 - открытие второго, вложенного цикла также с предусловием по стороне параллелепипеда с.

Шаг 5 - вычисление площади поверхности параллелепипеда.

Шаг 6 - проверка условия, что если текущее значение высоты меньше минимального и одновременно (оператор &) площадь поверхности шарового сегмента не меньше площади поверхности параллелепипеда, то считать текущее значение высоты и радиуса основания сегмента минимальным

Шаг 7 - наращивание счетчика вложенного цикла

Шаг 8 - если параметр вложенного цикла не удовлетворяет условию c<=c2, то выход из цикла.

Шаг 9 - наращивание счетчика внешнего цикла

Шаг 10 - если параметр этого цикла не удовлетворяет условию h>=h2, то выход из цикла.

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

Шаг 12 - завершение работы программы.

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

Глава III

Циклы. Обработка последовательностей и одномерных и двумерных массивов

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

Рис. 2.9: Пример блок-схемы цикла с параметром.

Начало

Ввод данных

i от N1 до N2 шаг K

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

Действия 1

Действия N

Конец

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

Для организации циклов с параметром в языках программирования используется составной оператор FOR («для»), а в циклах с условием чаще всего используется составной оператор WHILE («пока»).

n = int(input())

factorial = 1

while n > 1:

factorial *= n

n -= 1

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

>>>print(factorial)

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

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

Начало

Ввод N

S=0

i от 1 до N

C=S/N

Ввод A[i]

Вывод С

S=S+A[i]

Конец

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

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

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

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

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

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

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

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

кц

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

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

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

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

Факториал



n! = n * (n-1)!, при n>0

1, n=0

def fact(n):

if n == 0:

return 1

return fact(n-1)*n

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

>>> 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

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

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

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

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

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

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

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

>>>

Заключение

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

Конечно, полностью я Кнута или Лутца прочесть не смог, лишь использовал оттуда наиболее важное, однако сложно выбрать что-то “важное” из «Искусства программирования» Кнута, ведь многие можно сказать считают это непростое чтиво «библией» программиста.

*Так же я нашел описание Машины Тьюринга, ведь (МТ) идеально подходит для темы алгоритмизации.

Библиография

Лутц М. – «Изучаем питон I том», 2011, 976 стр.:
Хахаев И.А. – Практикум по алгоритмизации и программированию, 2010, 124 стр.:
Кнут Д.Э. – «Искусство программирования»
Жданова Т.А., Бузыкова Ю.С. – Основы алгоритмизации и программированию (Учебное пособие), 2011, 59 стр.: