Свойства алгоритма
I >10
Да
Нет
Проверка условия
Печать Z
Ввод-вывод данных
Начало
Начало, завершение программы или под-программы
Имя
Вызов процедуры
Соединительные линии и их объединение.
A
Точки связи или соединители
Комментарий
Эти базовые структуры были положены в основу технологии структурного программирования. Эта технология для разработки сложных программ рекомендует разбивать (декомпозировать) программу на подпрограммы (процедуры), решающие отдельные подзадачи, т.е. базируется на процедурной декомпозиции.
Простая программа - алгоритм, для которого:
Существует единственный вход и единственный выход.
Для каждого элемента алгоритма существует путь от входа к выходу через этот элемент (т.е. алгоритм не содержит бесконечных циклов и не содержит бесполезных (недостижимых) фрагментов).
Цикл «Пока» (с предусловием) -
пока не будет нару-шено условие (блок 3), осуществляется повторение тела цикла (блок 2).
Обход -
частный случай разветвления, когда одна ветвь не содержит ни каких действий.
Множественный выбор -
обобщение разветвле-ния, когда в зависи-мости от значения переменной I выпол-няется одно из нескольких действий.
Следование. Записываются последовательно операции одна под другой. Для отделения части последовательности операторов используются операторы – do…end-do.
первая операция
вторая операция
do
третья операция
end-do
Индексная последовательность (цикл по счетчику). Цикл с заранее определенным числом шагов (среднее между обычными последовательностью и классическим циклом).
for
индексный список
do
do-часть
end-do
Цикл-До. Операции структуры, включая модификацию until-теста, выполняются один или более раз до тех пор, пока until-тест не примет значение истина;
do
do-часть
until
until-тест
end-do
while
while-тест
do
do-часть
end-do
Разветвление. Если…то…иначе.
if
if-тест
then
then-часть
else
else-часть
end-if
case
список 1
case-часть 1
список 2
case-часть 2
…
список n
case-часть n
else
else-часть
end-case
Множественный выбор.
Алгоритм вычисления факториала N с использованием рекурсивной функции
Линейный поиск.
Элементы проверяются последовательно, по одному, до тех пор, пока нужный элемент не будет найден. Для массива из N элементов требуется, в среднем, (N+1)/2 сравнений (вычислительная сложность Оср(N)). Легко программиру-ется, подходит для коротких массивов.
Двоичный (бинарный) поиск.
Применим, если массив заранее отсортирован (по возрастанию ключей). Ключ поиска сравнивается с ключом среднего элемента в массиве. Если значение ключа поиска больше, то та же самая операция повторяется для второй поло-вины массива, если меньше - то для первой. Операция повторяется до нахож-дения нужного элемента. На каждом шаге диапазон элементов в поиске умень-шается вдвое. Требуется, в среднем, (log2N+1)/2 сравнений (выч. сложность Оср(log2N)). Применяется для поиска (многократного) в больших массивах.
Критерии оценки метода сортировки:
- количество необходимых операций сравнения в зависимости от числа элементов N, вычислительная сложность алгоритма характеризуется с помощью О-функции, аргументом которой является другая функция от N;
- эффективность использования памяти
где S(N) - объем памяти, занимаемый элементами данных до сортировки, S(N) - объем дополнительной памяти, требуемой в процессе сортировки.
Ввести массив A(1..N)
for J = 1,N-1,1
do
Мин.Эл. = А(J)
Индекс Мин.Эл. = J
for I = J+1,N,1
do
if A(I) < Мин.Эл.
then
Мин.Эл. = A(I)
Индекс Мин.Эл. = I
end-if
end-do
A(Индекс Мин.Эл.) = A(J)
A(J) = Мин.Эл.
end-do
Вывести A(1..N)
1
N
2
N-1
3
N-2
4
N-3
5
N-4
Требуется, в среднем, N(N+1)/2 срав-нений (выч. сложность O(N2), не зави-сит от начальной упорядоченности). Дополнительная память не нужна.
1
I=2
2
3
4
5
Temp
А(1)
I=3
Temp
А(2)
Temp
I=4
А(2)
I=5
Temp
А(5)
I=6
Temp
А(3)
Требуется, в среднем,
(N-1)(N/2+1)/2 сравнений (вычислительная сложность Оср(N2)). Скорость данного ме-тода зависит от начальной упо-рядоченности массива. Не тре-буется дополнительной памяти.
Ввести массив A(1..N)
K = 1, I = 1
while K <> 0
do
K = 0
for J = 1,N-I,1
do
if A(J) > A(J+1)
then
T = A(J),
A(J) = A(J+1),
A(J+1) = T, K = K+1
end-if
end-do
I = I +1
end-do
Вывести A(1..N)
N
K
1
N-1
K
2
N-2
K
3
N-3
K
4
Вычислительная сложность данного метода сильно зависит от исходного расположения элементов. Минимальное значение числа сравнений – N-1 в полностью отсортированном массиве, максимальное – (N2-N)/2 при начальной сортировке в обратном порядке. Средняя вычислительная сложность
Оср(N2). Доп. память не требуется.
Средняя вычислительная сложность Оср(N log2N) и лучше, если m (число цифр) мало. Требуется дополнительный массив размером N, и еще массив размером 10, в котором подсчитывается число элементов с выделяемой цифрой 0,1,…9.
{Процедура разбиения массива A(1..N) пороговым элементом V}
V = A(1), K = 2, J = N
while K < J
do
if A(K) < V
then
K = K + 1
else
if A(J) < V
then
Temp = A(K), A(K) = A(J)
A(J) = Temp
end-if
J = J - 1
end-if
end-do
if A(K) >= V
then
K = K - 1
end-if
Temp=A(1),A(1)=A(K),A(K)=Temp
K=2
1
V
J=6
K=3
2
J=6
K=4
3
J=6
K=5
4
J=6
K=5
J=5
Ввести массивы B(1..M),С(1..L)
I = 1, J = 1
for K = 1,M+L,1
do
if I > M
then
A(K) = C(J), J = J + 1
else
if J > L
then
A(K) = B(I), I = I + 1
else
if B(I) < C(J)
then
A(K) = B(I),I = I + 1
else
A(K) = C(J),J = J + 1
end-if
end-if
end-if
end-do
Вывести A(1..K)
1
1
2
3
4
5
6
+
+
+
1
2
2
3
+
1
3
2
+
1
МАРКЕР
Методы
ПероВверх
ПероВниз
Черный
Белый
СдвигК : X,Y
СдвигНа : Z
ЧертитьДугу : R,
...
Сообщения (операции) объекту ОкружностьА:
ОкружностьА.Высветить
ОкружностьА.Стереть
Многоугольник А
Многоугольник B
Многоугольник C
Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:
Email: Нажмите что бы посмотреть
Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно хранить и делиться своими презентациями с другими пользователями.
