7. Алгоритмизация и программирование

алгоритмов
4. Базовые алгоритмические структуры

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

за конечное число шагов.

виде конечной последовательности действий.

Для представления алгоритма в виде, понятном

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

Эти команды поступают на процессор как совокупность нулей и единиц,

т.е. числами. Последовательность чисел – машинный код.

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

(операторов).

Поиск ошибок – тестирование, процесс устранения ошибок – отладка.

программу необходимо либо сразу перевести текст программы в машинный код

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

синтаксических ошибок и автоматически переводят его в машинный код. В

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

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

без участия компьютера.
Постановка задачи:
сбоp инфоpмации о задаче;
фоpмулиpовка условия задачи;
опpеделение конечных целей pешения задачи;
определение формы выдачи результатов;
описание данных (их типов, диапазонов величин, структуры и т.п. ).

анализ существующих аналогов;
анализ технических и программных средств;
pазpаботка математической

модели;
разработка структур данных.

3. Разработка алгоритма:
выбор метода проектирования алгоритма;
выбор формы записи алгоритма (блок-схемы, псевдокод и др.);
выбор тестов и метода тестирования;
проектирование алгоритма.

способов организации данных;
запись алгоpитма на выбpанном языке пpогpаммиpования.
5. Тестиpование

и отладка:
синтаксическая отладка;
отладка семантики и логической стpуктуpы;
тестовые pасчеты и анализ pезультатов тестиpования;
совершенствование пpогpаммы.
Отладка программы — это процесс поиска и устранения ошибок в программе, производимый по результатам её прогона на компьютере.
Тестирование (англ. test — испытание) — это испытание, проверка правильности работы программы в целом, либо её составных частей.

уточнение в случае необходимости математической модели с повторным выполнением этапов

2 — 5.

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

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

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

графических символов);

Псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие

в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

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

последовательность действий:
задать два числа;
если числа равны, то взять любое из

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

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

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

соответствует выполнению одного или нескольких действий;

Такое графическое представление называется схемой алгоритма или блок-схемой.

Графическая форма записи алгоритма

записи алгоритмов. В нем не приняты строгие синтаксические правила для

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

Примеры обозначений

S)
дано | n > 0
надо | S = 1*1 +

2*2 + 3*3 + ... + n*n
нач цел i
ввод n; S = 0
нц для i от 1 до n
S = S + i*i
кц
вывод "S = ", S
кон

tmp;
for (var i = data.length - 1;

i > 0; i--) {
var counter=0;
for (var j = 0; j < i; j++) {
if (data[j] > data[j+1]) {
tmp = data[j]; data[j] = data[j+1];
data[j+1] = tmp; counter++;
}
}
if(counter==0){ break; }
}
return data;
};

void bubble(int* a, int n) {
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}

JavaScript

C++

кроме блока "НАЧАЛО", который не имеет входа вообще. Несколько стрелок,

идущих на вход некоторого блока, положено соединять до точки входа в блок.
Каждый блок имеет строго один выход, кроме блока "КОНЕЦ", который не имеет выхода, и блока проверки условия, имеющего два выхода. Блок проверки условия обозначает разветвление вычислительного процесса в зависимости от выполнения некоторого условия. Чтобы различить выходы этого блока, их помечают словами "да" и "нет". Если условие, записанное в блоке, выполняется, то вычислительный процесс пойдет по стрелке со словом "да", иначе - по стрелке со словом "нет’’.

алгоритма.
Алгоритмические структуры
Линейные
Ветвления
Циклические
Рекурсивные
Вспомогательные
Базовые

шаг алгоритма выполняется только один раз, причем после каждого i-го

шага выполняется (i + 1)-й шаг, если i-й шаг — не конец алгоритма.

формуле эллипса g=·D· d/4, где D - наибольший диаметр сечения ствола,

d - наименьший диаметр сечения ствола, число =3.1416.

Переменной называется величина, значение которой может меняться в процессе работы алгоритма. Каждой переменной отводится определённое место в памяти ЭВМ (ячейка памяти). В эту ячейку помещается текущее значение переменной. Вновь вычисленное значение переменной пересылается в ту же ячейку. При этом "старое содержимое" ячейки теряется.
Можно записать схему алгоритма так

начало

ввод D,d,

g=· D· d/4

вывод g

конец

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

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

полное ветвление
если-то-иначе

неполный вариант ветвления
если-то

первый взгляд, алгоритм нахождения значения y кажется линейным, но это

не так. Приведём схему алгоритма.

начало

ввод x

d=3x-4

d=0

у=(2x+3)/d

вывод y

конец

да

нет

Невозможно вычислить y

x = 3
y = x - a

, если x > 3
x2 + a2  , если x < 3

начало

ввод x,a

y=x+a

x>3

y=x-a

y=x2 +a2

Вывод y

Конец

x=3

да

да

нет

нет

u=min(x,max(y,z))

начало

ввод x,y,z

y>z

r= y

r=z

x

u=r

u=x

вывод u

конец

да

нет

да

нет

выполняется несколько раз. Количество повторений либо фиксировано, либо зависит от

входных данных алгоритма.

Пример 5. Найти конечную сумму S=1+1/2+1/3+….+1/n.

Начало

Ввод n

S = 0

i = 1

i<=n

Вывод S

Конец

S = S + 1/i

i = i + 1

да

нет

Пример 6. Дан массив чисел D=(d1,d2,..,dn). Найти dср по формуле dср= (d1+d2+..+dn)/n

Начало

Ввод n

i = 1

i<=n

S = 0

1

1

i = i + 1

i = 1

i<= n

dср=S/n

S=S +di

i=i+ 1

Вывод dср

Конец

Ввод di

да

да

нет

нет

числа;
строки;
логические величины (аналоги 1 и О, "да" и

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

машинные (самого низкого уровня);
машинно-ориентированные (ассемблеры);
машинно-независимые (высокого уровня).

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

языки программирования:
машинные (самого низкого уровня);
машинно-ориентированные (ассемблеры);
машинно-независимые (высокого уровня).

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

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

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