44. Алгоритм поиска с возвратом (метод программирования с отходом назад).

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

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

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

45. Разработка алгоритмов "сверху-вниз". Требования.

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

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

• обращение к готовому алгоритму;

• вычисление арифметического выражения и присваивание значения переменной;

• сравнение арифметических выражений или переменных;

• ввод или вывод данных; и т.п.

Главное требование – работоспособность, а так же простота и понятность.

46. Этапы решения задач с помощью компьютера и их содержание.

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

1. Постановка задачи:

• сбор информации о задаче;

• формулировка условия задачи;

• определение конечных целей решения задачи;

• определение формы выдачи результатов;

• описание данных (их типов, диапазонов величин, структуры и т.п.).

2. Анализ и исследование задачи, модели:

• анализ существующих аналогов;

• анализ технических и программных средств;

• разработка математической модели;

• разработка структур данных.

3. Разработка алгоритма:

• выбор метода разработки алгоритма;

• выбор формы записи алгоритма (схемы алгоритмов, псевдокод и т.д.);

• выбор тестов и метода тестирования; проектирование алгоритма.

4. Программирование:

• выбор языка программирования;

• уточнение способов организации данных;

• запись алгоритма на выбранном языке программирования.

5. Тестирование и отладка:

• синтаксическая отладка;

• отладка семантики и логической структуры;

• тестовые расчеты и анализ результатов тестирования;

• совершенствование программы.

6. Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2 5.

7. Сопровождение программы:

• доработка программы для решения конкретных задач;

• составление документации к решенной задаче, к математической модели, к алгоритму, к программе, к набору тестов, к использованию.