АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ

Наша цель — научить компьютер решать те задачи, которые он самостоятельно и изначально решать не уме­ет. Что же для этого нужно?

А что, например, следует сделать, если нужно привлечь к решению задачи человека (назовем его исполнитель), не знакомого с ее решением? В общем виде последова­тельность действий здесь следующая:

а) выбрать способ (метод) решения задачи и изучить
его во всех подробностях;

б) сообщить исполнителю выбранный метод в абсолют­
но понятном для него виде.

Первый этап этого процесса обычно не вызывает зат­руднений, так как для большинства встречающихся задач метод решения либо известен из практики, либо подсказы­вается здравым смыслом, либо описан в литературе. Главная трудность этого этапа — выбрать из нескольких методов более подходящий для решения данной задачи: наименее трудоемкий, максимально эффективный и т.д.

Второй этап значительно сложнее. Дело в том, что если способ (метод) решения задачи описан произвольно, то нет гарантии, что он будет верно понят исполнителем.

Попробуйте, например, небольшую игру. Попросите товарища на время забыть все, что он знает, например, о процессе варки картофеля. Если же выбранный вами по­мощник еще никогда не варил картошку, то эксперимент будет максимально «чистым». Опишите ему процесс при­готовления этого нехитрого блюда и попросите его приго­товить, точно следуя вашим инструкциям. После чего уда­литесь с кухни и подождите результата в другой комнате. Ну как картошечка? Надеюсь, вы не забыли сказать ва­шему другу, чтобы он предварительно почистил ее?..

Именно поэтому описание метода следует выполнять в соответствии с определенными правилами, а именно: - выделить величины, являющиеся исходными для задачи;

- разбить процесс решения задачи на такие этапы, кото­рые известны исполнителю и которые он может вы­полнить однозначно без всяких пояснений;

- указать порядок выполнения этапов;

- указать признак окончания процесса решения задачи;

- указать во всех случаях, что является результатом ре­шения задачи.

Описание метода, выполненное в соответствии с этими правилами, называется алгоритмом решения задачи.

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

Или более коротко: алгоритм — это строго опреде­ленная последовательность действий, необходимых для ре­шения данной задачу..

Примером алгоритма может служить уже упоминав­шийся кулинарный рецепт — алгоритм варки картофеля:

1. Подготовить исходные величины — воду, картофель, соль, посуду (кастрюлю с крышкой для варки), нож.

2. С помощью ножа очистить картофель и промыть его водой.

3. Нарезать картофель для варки.

4. Поместить картофель в кастрюлю.

5. Залить содержимое кастрюли водой.

6. Посолить.

7. Довести воду до кипения.

8. Убавить огонь.

9. Варить картофель до готовности (приблизительно в течение 20-30 минут).

10. Снять кастрюлю с огня и слить воду.

11. Картофель готов. Процесс прекратить.

3. Способ, использующий псевдокоды. Псевдокоды — это интерпретация шагов алгоритма на обычном языке, которая описывает действие команды. Псевдокод исполь­зуется в листингах, чтобы показать общую структуру про­граммы, не применяя реальных операторов языка про­граммирования.

4. Запись алгоритма на одном из языков программи­рования (Pascal, Basic и т.п.)

Контрольные вопросы_____________________

1. Строго определенная последовательность действий,
необходимая для решения данной задачи — это...

а) метод решения;

б) алгоритм;

в) блок-схема.

Укажите правильный вариант ответа.

2. Ниже перечислены основные свойства алгоритма:

а) дискретность алгоритма;

б) определенность алгоритма;

в) актуальность алгоритма;

г) результативность алгоритма;

д) массовость алгоритма;

е) строгость алгоритма.

Некоторые из этих понятий не относятся к основным свойствам алгоритма. Укажите какие именно.

3. Свойство, означающее, что решение задачи, запи­
санное в виде алгоритма, разбито на отдельные простей­
шие команды, которые расположены в порядке их вы­
полнения, — это:

а) дискретность алгоритма;

б) определенность алгоритма.
Укажите правильный вариант ответа.

4. Массовость алгоритма — это свойство заключается в
том, что каждый алгоритм, разработанный для решения
некоторой задачи, должен быть применим для решения
задач этого типа при всех допустимых значениях исход­
ных данных.

Верно ли данное высказывание?

5. Существует несколько способов описания алгоритмов:

а) словесно-формульное;

б) графическое (блок-схемы).

Все ли способы описания алгоритмов здесь перечислены?

6. Псевдокоды — это:

а) описание алгоритма с помощью слов и формул;

б) описание с помощью специальных графических схем
алгоритмов;

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

Укажите правильный вариант ответа.

7. Ниже приведены две блок-схемы некоторого алго­
ритма. Какая из приведенных блок-схем ошибочна?

Даны переменные А и В. Требуется обменять их значе­ния, т.е. переменная А должна получить значение В, а В — значение А.

Решение:

1. Исходные данные: А, В. Вспомогательная перемен­ная DOP. Результат: А, В.

2. Метод решения задачи: в ЭВМ каждая величина хранится в отдельном участке памяти (переменной). По­этому задача заключается в том, чтобы поменять местами содержимое двух ячеек.

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

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

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

Напомню, что псевдокоды — это интерпретация шагов алгоритма на обычном языке, которая описы­вает действие команды.

Переменные А, В, Dop: целые числа; {описатель­ный блок} Начало

Ввод (А, В); Dop: =A; А: =В; B: =Dop; Вывод(А, В); Конец.

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

Пусть переменным А и В задаются значения 3 и 6 соот­ветственно. В итоге переменная А должна содержать 6, а В — 3. Проверим работу нашего алгоритма:

Результат работы алгоритма совпадает с ожидаемым. Значит, алгоритм составлен верно.

Нам известны 6 операций сравнения:

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

Часто встречаются задачи, в которых используются не отдельные условия, а совокупность связанных между со­бой условий (отношений). Например, в магазине вам нужно выбрать туфли, размер которых г=45, цвет со1=белый, цена price не более 400 руб.

Другой пример: школьник выяснил, что сможет ку­пить шоколадку, если она стоит 3 руб. или 3 руб. 50 коп.

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

Так, условия наших примеров в алгоритме могут вы­глядеть таким образом:

первое: (г=45) и (со1=белый) и (не (price> 400));

второе: (цена=3) или (цена=3, 5).