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

"Алгоритмы + структуры данных = программы".
Вирт, Н. Алгоритмы и структуры данных http://www.iprbookshop.ru/63821.html
Никлаус Вирт - знаменитый швейцарский специалист по программированию, автор языка Паскаль.

Основы алгоритмики.
Понятие алгоритма - одно из основных понятий программирования и математики.
Мухаммед ибн Муса аль-Хорезми (Alhorithmi), 783-850 гг., «Книга о сложении и вычитании»
Алгоритм - это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу.
Программа - конкретная формулировка абстрактных алгоритмов, основанная на конкретных представлениях и структурах данных.

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность».
(Кнут, Д.Э. Искусство программирования. Том 1 : Основные алгоритмы / Д.Э. Кнут; под общей редакцией Ю.В. Козаченко; перевод с английского С.Г. Тригуб, Ю.Г. Гордиенко, И.В. Красикова. - Москва : Вильямс, 2004. - 720 с. - ISBN 5-8459-0080-8)

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

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

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

Псевдокод. Общий вид алгоритма:
алг название алгоритма (аргументы и результаты)
дано условия применимости алгоритма
надо цель выполнения алгоритма
нач описание промежуточных величин
| последовательность команд (тело алгоритма)
кон
алг Факториал (арг цел N, рез цел F)
дано | N
надо | F = 1*2*3* ...*N
нач цел i
ввод N; F:=1
нц для i от 1 до N
F:=F*i
кц
вывод "F = ", F
кон

Алгоритм присвоения переменной
демонстрирует блок-схема программы
(графическая форма)

Пример программы вычисления факториала числа N на языке С#:
using System;
namespace Factorial
{
class Program
{
static void Main(string[] args)
{
int N, F = 1, i;
Console.WriteLine("Расчет факториала. Введите число N = ");
N = Convert.ToInt32(Console.ReadLine());
for (i = 2; i <= N; i++)
F = F * i;
Console.WriteLine("F = " F);
Console.ReadKey();
}
}
}

ГОСТ 19.701-90 (переиздан в 2010г). Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения
Блок-схема – совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий.

Базовая структура "следование".

2. Базовая структура "ветвление".
1) если-то

i=3
string1:= ‘очная форма обучения’
если i=3
то string1:= ‘очная форма обучения’
все
Пример. Формирование 1 цифры в нумерации групп
Да
Нет

2. Базовая структура "ветвление".
2) если-то-иначе

Пример. Формирование 1 цифры в нумерации групп
если i>0
то string2:= ‘высшее образование’
иначе string2:= ‘среднее профессиональное образование’
все
i>0
string1:= ‘очная форма обучения’
Да
Нет
string1:= ‘среднее профессиональное образование’

2. Базовая структура "ветвление".
3) выбор

Пример. Формирование 2 цифры в нумерации групп
выбор
при j=1 string3:=‘первый курс’
при j=2 string3:=‘второй курс’
при j=3 string3:=‘третий курс’
при j=4 string3:=‘четвертый курс’
все
Нет

2. Базовая структура "ветвление".
3) выбор-иначе

Пример. Формирование 2 цифры в нумерации групп
выбор
при j=1 string3:=‘первый курс’
при j=2 string3:=‘второй курс’
при j=3 string3:=‘третий курс’
при j=4 string3:=‘четвертый курс’
иначе string3:=‘пятый курс’
все
Нет
String:3:=‘пятый курс’

3. Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла
1) Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова «пока».

нц пока i<=5
S:=S+A[i]
i:=i+1
кц

3. Базовая структура "цикл".
2) Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.

нц для i от 1 до 5
X[i]:=i*i
Y[i]:=X[i]/2
кц
i=1,5
X[i]:=i*i
Y[i]:=X[i]/2

Условие1 в приведенном ниже алгоритме задает ...
полное ветвление;
цикл с предусловием;
цикл с постусловием;
цикл с заданным числом повторений.

Приведенной блок-схеме соответствует фрагмент программы ...
если условие 1 то
оператор 1
оператор 2
оператор 3
если условие 2 то оператор 4
иначе оператор 5
если условие 1 то
если условие 2 то оператор 4
иначе
начало
оператор 1
оператор 2
оператор 3
конец
иначе оператор 5
если условие 1 то
начало
оператор 1
оператор 2
оператор 3
конец
иначе
если условие 2 то оператор 4
иначе оператор 5

При выполнении приведенного ниже алгоритма с исходными данными х = 14, y = -5 значение переменной z будет равно ...

При выполнении приведенного ниже алгоритма с исходными данными n = 6 значение переменной s будет равно ...

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

Способ представления структур данных

Классификация структур данных

ОПЕРАЦИИ НАД СТРУКТУРАМИ ДАННЫХ
Создание – выделение памяти для структуры данных.
Уничтожение – противоположна по своему действию операции создания.
Выбор – обеспечивает доступ к данным внутри самой структуры.
Обновление – позволяет изменять значения данных в структуре и добавлять (удалять) выбранные данные.

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