Понятие об алгоритме. Свойства алгоритмов. Способы записи алгоритмов

алгоритма
Структурные схемы алгоритмов

вперед
назад

виде
нескольких последовательных этапов:
Постановка задачи,
Математическое или информационное моделирование,
Алгоритмизация задачи,
Программирование,
Ввод программы

и исходных данных в ЭВМ,
Тестирование и отладка программ,
Исполнение отлаженной программы и анализ результатов.

вперед

назад

от исходных данных к требуемому конечному результату. Алгоритм должен быть

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

вперед

назад

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

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

вперед

назад

уравнения
a, b, c
d= b2 –4ac
d>0
ds=d
x1=-b + ds

2a

x2=-b - ds
2a

Решения нет

x1,x2

Конец

Начало

1

2

3

4

5

6

7

8

да

нет

Блок 1- исходные данные,блок 2–вычисляется дискриминанта, блок 3 – проверка значения d. Если оно меньше 0 , то «Решения нет», если больше 0, то вычисляются квадратный корень,значения корней, блок 8 – результат выводится на экран

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

вперед

назад

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

участков программы с определенной структурой. Можно выделить и наглядно представить графически три простейшие структуры:
Последовательность двух или более операций,
Выбор направления,
Повторение.
Любой вычислительный процесс может быть представлен как комбинация этих элементарных алгоритмических структур. Соответственно, вычислительные процессы, выполняемые на ЭВМ по заданной программе, можно разделить на три основных вида:
Линейные
Ветвящиеся
Циклические

вперед

назад

в порядке их записи. Каждая операция является самостоятельной, независимой от

каких-либо условий.

Пример линейного алгоритма,
определяющего процесс вычисления
арифметического выражения
y=(b2-ac):(a+c)

вперед

назад

направлений (ветвей). Каждое отдельное направление является отдельной ветвью вычислений. Направление

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

да

вперед

назад

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

вычислений цикла (тело цикла),
Модификация параметров,
Проверка условий окончания цикла.
Цикл называется детерминированным, если число повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений заранее неизвестно, а зависит от значений параметров, участвующих в вычислениях.

вперед

назад

алгоритм и какими свойствами он обладает?
Укажите формы представления алгоритмов.
Опишите структурные

схемы алгоритмов.
Составьте и запишите алгоритмы (в тетради):
Даны две простые дроби.Составить алгоритм получения дроби, являющейся результатом их деления.
Написать алгоритм вычисления по формуле:
y=(1-x2+2,5x3+x4)2,учитывая следующие ограничения:
Пользоваться можно только операциями сложения, вычитания и умножения; каждое выражение может содержать только одну арифметическую операцию.

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

вперед

назад

под ред. И.Семакина, стр.204-208,
Ю.Шафрин, Информационные технологии, стр.43-52.
возврат

без участия ЭВМ.

1. Постановка задач:
сбор информации о задаче;
формулировка условия

задачи;
определение конечных целей;
описание данных.
2. Построение математической модели.
3. Построение алгоритма:
выбор формы записи алгоритма (блок-схема, табличная и др.);
запись алгоритма.
4. Программирование:
выбор языка программирования;
выбор способа представления данных;
запись алгоритма на выбранном языке;
выбор тестов и методов тестирования.
5. Тестирование:
проверка работоспособности программы.

программы:

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

факт наличия ошибки.
Отладка выясняет её причину.

Программа-отладчик обеспечивает следующие возможности:

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

При отладке важно помнить:

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

!

Два этапа процесса тестирования:

проверка в нормальных условиях;
проверка в экстремальных условиях.


Характерные ошибки программирования:

Вид ошибки Пример

Неправильная Правильное решение неверно
постановка задачи сформулированной задачи

Неверный алгоритм Выбор алгоритма, приводящего к
неточному или не эффективному
решению задач

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

неправильная запись формата оператора;
несогласованность скобок;
пропуск разделителей.

Примеры логических ошибок:

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

цикла;
неверное задание счётчика цикла;
бесконечный цикл.

Примеры ошибок

ввода/вывода и ошибок при работе с данными:
неправильное задание типа данных;
организация считывания меньшего или большего объема
данных, чем требуется.

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

Примеры ошибок при работе с массивами:
неправильно задан размер массива;
неправильно задан тип массива.

(например, целого вместо
вещественного);
неверное определение порядка

действий;

деление на нуль;
извлечение квадратного корня из отрицательного числа;

Эти ошибки обнаруживаются с помощью тестирования.


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

!

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

задачи сводится, как правило, к математической форме описания условий задачи по схеме:

Задача (словесное описание).
Дано (перечисление исходного).
Требуется (перечисление требуемого).
Связь (зависимость между исходным и требуемым).
При (условия допустимости исходного).

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

Методы решения задач:
рекуррентный;
рекурсивный;
приближённые методы.

Рекуррентный метод

Метод, использующий

рекуррентные соотношения, называется рекуррентным.

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

Задача (найти сумму конечной последовательности заданных чисел).
Дано (x1, x2…xn – последовательность n чисел).
Требуется (найти S – сумму этих чисел).
Связь (S = x1+ x2+…+xn ).
При (любых значениях чисел последовательности).

Применив рекуррентный метод, получим соотношения:
S0 = 0
Sk = Sk – 1 + xk k =1,2,…n
S = Sn

прогрессий;
нахождение членов ряда Фибоначчи.


Итальянский математик XVI

в. Фибоначчи построил математический ряд 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…, описывающий биологический процесс (процесс размножения кроликов). Попробуйте записать рекуррентное соотношение для этого ряда.

Если в таком ряду взять отношение последующего члена к предыдущему

и наоборот, получим числа 1,618 и 0,618. Эти числа были открыты «пифагорейцами» и получили название «золотых».
Они являются корнями квадратного уравнения, которое можно вывести из следующей пропорции:

A+B = A A B
A B
A и B – соответственно две части одного отрезка.
Числа эти не зря названы «золотыми». «Пифагорейцы» же заметили, что музыкальный звукоряд построен по закону соотношений частот, равных «золотому» числу. И везде, где человек ощущает гармонию: в звуках, живописи, размерах – всюду присутствуют «золотые» числа (числа Фибоначчи).
К изумлению Кеплера, создававшего свою модель солнечной системы и уже знавшего основные размеры планет, периоды их обращения и взаимные расстояния, эти числа оказались числами Фибоначчи. Оказалось, что весь ближний космос организован по законам музыкальной гармонии. (Всё это Кеплер изложил в своей книге «Музыка сфер».)

.

мозга при реакции на внешний раздражитель – это затухающие апериодические

колебания, соседние периоды которых относятся по закону «золотого сечения».
Если рост человека принять за весь отрезок, а пупок – точка деления, то от него вниз – часть А, а вверх часть – В. Для мужчин это соотношение в среднем 1,7, а для женщин 1,5, т.е. мужчины в среднем стройнее (не из интуитивного ли стремления соответствовать гармонии «золотого сечения» появились туфли на каблуках?).
В ряду Фибоначчи чем больше порядковый номер членов ряда, тем точнее выполняется «золотое соотношение». Проверьте это.

латинской науке поздней античности и средневековья то же понятие передаётся

чаще всего как «небесная гармония», «небесная музыка», «мировая гармония»

Марс, Меркурий, Венера, Солнце, Луна (низший тон).

лишь метафорически, Кеплер рассчитал математические соотношения в движении планет и увязал их

с музыкальными интервалами, установив семь основных гармонических интервалов (консонансов): октаву (2/1), большую сексту (5/3), малую сексту (8/5), ...

Пифагора; Другое — разделение линии на экстремальное и среднее соотношение.
Первое

можно сравнить с мерой золота; Второе мы можем назвать драгоценным камнем».

Рекурсивный

метод

Рекурсивным называется метод вычисления функций через самих себя.
Иногда значение функции для некоторых аргументов можно выразить через значение этой же функции от других аргументов.


Пример 1:

sin(x+ ) = – sin(x) для всех вещественных x.

Пример 2:
1, если n = 1;
n! =
(n-1)!  n, если n > 1.

Метод Монте-Карло (приближённый метод)

Метод используется для вычисления площади фигуры, ограниченной произвольным контуром.
Пусть есть фигура на плоскости, и пусть она расположена внутри квадрата, сторона которого, А, известна. Площадь фигуры можно вычислить, засыпав
квадрат слоем песка. Число песчинок внутри
квадрата будет пропорционально его площади, а число
песчинок внутри фигуры – пропорционально её площади.
Из этой пропорции можно определить площадь фигуры.
Эта задача легко моделируется и программируется. Роль песчинок могут играть точки выводимые произвольно на заданный участок. Их координаты
можно задавать с помощью генератора случайных чисел.

А

А

Y

X

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.