Методические рекомендации по организации изучения дисциплины (стр. 4 из 9)

При разработке алгоритма используют следующие основные принципы.

1. Принцип поэтапной детализации алгоритма (другое название — "проектирование сверху-вниз"). Этот принцип предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи) и их постепенную детализацию.
2. Принцип "от главного к второстепенному", предполагающий составление алгоритма, начиная с главной конструкции. При этом, часто, приходится "достраивать" алгоритм в обратную сторону, например, от середины к началу.
3. Принцип структурирования, т.е. использования только типовых алгоритмических структур при построении алгоритма. Нетиповой структурой считается, например, циклическая конструкция, содержащая в теле цикла дополнительные выходы из цикла. В программировании нетиповые структуры появляются в результате злоупотребления командой безусловного перехода (GoTo). При этом программа хуже читается и труднее отлаживается.

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

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

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

Идея решения задачи. Очередной ход следует делать на то поле, с которого на другие поля меньше всего ходов.

Формализация задачи. Назовем термином "потенциал поля" количество допустимых ходов коня. Введем следующие обозначения:

• С — матрица 8*8, содержащая потенциалы полей (фрагмент C показан на рис. 13);
• R — матрица 8*8, содержащая решение задачи в виде номеров ходов коня;
• Sx, Sy — массивы из 8 элементов, содержащие смещения коня относительно текущей координаты, необходимые для реализации правила буквы "Г":

Sx = ( 1, 2, 2, 1,-1,-2,-2,-1);
Sy = (-2,-1, 1, 2, 2, 1,-1,-2).

• x, y — текушие координаты коня;
• x1,y1 — координаты поля с минимальным потенциалом для текущих (x, y);
• m — значение минимального потенциала допустимого поля.

Будем учитывать пройденные поля путем задания соответствующим элементам матрицы C значения 9, т.е. значения вне множества допустимых потенциалов.

Разработка алгоритма решения задачи

На рис. 8 показан укрупненный алгоритм решения поставленной задачи. На рис. 9 - 12 показаны основные шаги поэтапной детализации основного алгоритма.

Следует обратить внимание на нумерацию блоков в детализирующих блок-схемах. Число до первой точки является номером детализируемого блока в основной схеме. Число после первой точки является номером блока в схеме детализации первого уровня и т.д.

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

Значком & на рис. 11 обозначена логическая операция И.

Пример 3

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

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

Задача 2

Вычислить сумму

Решение

Моделирование задачи 2 показывает, что для вычисления суммы можно использовать цикл For-Next, поскольку заранее известно количество слагаемых. Кроме того, не следует вычислять заново факториал для очередного слагаемого: гораздо проще вычислить факториал, опираясь на значение факториала для предыдущего слагаемого. Аналогично организуется чередование знаков слагаемых: введем целую переменную Z=1 и будем в цикле выполнять команду Z=-Z.

Для решения задачи введем следующие величины:

• S — искомая сумма;
• F — значение факториала;
• C — значение числителя;
• Z — знак слагаемого (+1 или –1).

Таким образом, в задаче 2 дано: N, X; надо получить S.

Контрольный пример: при N=4 и X=3 получим S = -0.125.

Алгоритм решения задачи показан на рис. 2.

Лекция 3. Алгоритмы ветвления и циклов

1. Структурограмма:
   
   

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

Неполная форма:

Пример: найти наименьшее из трех чисел.
1 вариант решения:

2 вариант решения:



Алгоритмическая конструкция цикла.

Цикл - управляющая структура, организующая многократное выполнение указанного действия.

Цикл "пока":

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

Исполнение цикла начинается с выполнения действия. Таким образом тело цикла будет реализовано хотя бы один раз. После этого происходит проверка условия. Поэтому цикл "до" называют циклом с постусловием. Если условие не выполняется, то происходит возврат к выполнению действий. Если условие истинно, то осуществляется выход из цикла. Таким образом условие цикла "до" - это условие выхода. Для предотвращения зацикливания необходимо предусмотреть действия, приводящие к истинности условия.
Цикл с параметром, или цикл со счетчиком, или арифметический цикл - это цикл с заранее известным числом повторов.

В блоке модификации указывается закон изменения переменной параметра.
Xo - начальное значение параметра
h - шаг
Xn - последнее значение параметра
Для создания циклов с параметром необходимо использовать правила:

1. Параметр цикла, его начальное и конечное значения и шаг должны быть одного типа
2. Запрещено изменять в теле цикла значения начальное, текущее и конечное для параметра
3. Запрещено входить в цикл минуя блок модификации
4. Если начальное значение больше конечного, то шаг - число отрицательное
5. После выхода из цикла значение переменной параметра неопределенно и не может использоваться в дальнейших вычислениях
6. Из цикла можно выйти не закончив его, тогда переменная параметр сохраняет свое последнее значение

Задача 1

Дан кирпич прямоугольной формы со сторонами A, B, C и прямоугольное отверстие в стене со сторонами X и Y. Определить, пройдет ли кирпич в отверстие, если допускается располагать его грани только параллельно сторонам отверстия.