Этапы решения задач на ЭВМ

Свойства алгоритмов.

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

1. Дискретность. (Алгоритм должен состоять из отдельных шагов).

2. Понятность. (Указания должны быть понятны исполнителю).

3. Однозначность. (Единственность толкования правил выполнения действий и порядка их выполнения).

4. Массовость. (С помощью алгоритма можно решать не одну конкретную задачу, а множество однотипных задач и делать это неоднократно).

5. Результативность. (Выполнение алгоритма должно приводить к конкретному результату - решению задачи - за конечное число шагов).

6. Конечность. (Завершение работы алгоритма в целом за конечное число шагов).

Например:

Свойства	Пример выполнения свойства	Пример невыполнения свойства
Дискретность	Казнить нельзя, помиловать!	Казнить, нельзя помиловать
Однозначность	На дубе ларец, а в ларце утка, а в утке яйцо, в яйце игла, в игле смерть Кощея.	Поди туда, не знаю куда, принеси то, не знаю что.
Массовость	Каждой дочери отец привёз по дорогому подарку	Принц мог жениться только на настоящей принцессе
Понятность	Инструкция по-русски	Инструкция на японском языке
Конечность	Мама сварила кашу в горшочке	Каша уже заполнила все улицы, а горшочек всё варил кашу.
Результативность	Мышка хвостиком махнула, яйцо и разбилось	Баба била-била не разбила.

Исполнять алгоритмы может не только человек. Роботы-манипуляторы, станки с программным управлением, компьютер и даже животные в цирке исполняют различные алгоритм.

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

Когда человек хочет работать с формальным исполнителем, он должен выяснить:

1) В какой среде (обстановке) работает исполнитель и какую работу он может выполнять? 2) Какие команды исполнитель понимает? 3) Как команды передаются исполнителю? 4) Как команды выполняются исполнителем? 5) Когда выполнение команды невозможно?

Среда Исполнителя - объекты, над которыми исполнитель может совершать действия

Система Команд Исполнителя (СКИ) – строго заданный список допустимых действий.

Допустимые действия - действия, которые может выполнить Исполнитель.

Отказ – это невозможность выполнить команду.

Итак, при составлении алгоритмов можно допустить ошибки трех типов:

1) ошибки синтаксические - это ошибки формальной записи отдельных команд (отказ «не понимаю»);

2) ошибки семантические - это ошибки, заставляющие исполнителя выполнять действия, выходящие за пределы его возможностей (отказ «не могу»)

3) ошибки логические - это формально правильные команды, которые не ведут к желаемому результату.

Способы описания алгоритмов

¨ Словесно-пошаговый (на естественном языке).

¨ Графический (на языке блок-схем).

¨ Алгоритмический язык.

Например:

	Словесно-пошаговый.	Составить алгоритм поиска площади круга радиусом R. 1. Ввод значения r 2. Вычислить s=p×r2 3. Записать в ответ значение s. 4. Конец.
	Графический (в виде блок-схемы)	Схема- наглядное графическое изображение алгоритма, когда отдельные его действия (этапы) изображаются при помощи различных геометрических фигур (блоков), а связи между этапами указываются при помощи стрелок, соединяющих эти фигуры.

 

Основные блоки.	Пример
	Начало Конец		Условие
	Ввод Вывод
	Выполнение действия

 

3

Алгоритмический язык

алг ЗАДАЧА (вещ r,s) арг r рез s нач ввод r s:= 3.14×r2 вывод s кон

Команда присваивания

При записи вычислительных алгоритмов удобно использовать специальный знак присваивания: =. Не путать со знаком "=" (равно) в математике. Этот знак ис­пользуется для изображения особой операции — операции присваивания. В чем заключается ее смысл?

Пусть имеется предпи­сание вида Y: = X. (Читается: "Y присвоить X").

Здесь Y - переменная, а Х - некоторое выражение.

Предписание означает следующее: выполнить все дей­ствия, предусмотренные формулой X, и полученный ре­зультат (число) считать значением (т.е. присвоить пере­менной Y).

В ячейку памяти, отведённую для Y, ЭВМ должна записать результат действий, предусмотренных формулой X.

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

Например:

Y: = K; Y: = 37; X: =X+1 (“возьми то, что хранится в X, добавь 1 и результат опять положи в X”)

B$: =”Ура! Скоро каникулы!”, B – является символьной или литерной переменной, ее значением является текст.

Лабораторная работа.

Задание 1. Поставьте соответствие, между понятиями и заполните таблицу ответов.

1. Алгоритм – это…	А) среда, система команд исполнителя, отказ
2. Основными свойствами алгоритма являются…	Б) действия которые может выполнить Исполнитель.
3. Формальный исполнитель…	В) невозможность выполнить команду.
4. Назовите характеристики исполнителя:	Г) строго заданная последовательность действий, которую необходимо выполнить, чтобы получить нужный результат.
5. Среда Исполнителя – это…	Д) ничего не знает о цели алгоритма и выполняет его безумно.
6. Система команд Исполнителя – это…	Е) строго заданный список допустимых действий
7. Допустимые действия – это…	Ж) дискретность, определенность (точность), результативность, массовость.
8. Отказ – это…	З) объект, над которым исполнитель может совершать действия.

 

1.

2.

3.

4.

5.

6.

7.

8.

Задание 2. Приведите примеры исполнителей алгоритмов.

1.
2.
3.
4.

Задание 3. Напишите свойства, соответствующие каждому определению:

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

Задание 4. Заполните по образцу таблицу своими примерами.

Свойства	Пример выполнения свойства	Пример невыполнения свойства
Дискретность
Однозначность
Массовость
Понятность
Конечность
Результативность

Задание 5. Некий злоумышленник выдал следующий алгоритм за алгоритм получения кипятка:

Налить в чайник воду.
Открыть кран газовой горелки.
Поставить чайник на плиту.
Ждать, пока вода не закипит.
Поднести спичку к горелке.
Зажечь спичку.
Выключить газ.

Ответьте на вопрос:

Каков результат работы данного алгоритма?
Каким свойством не обладает данный алгоритм?
Исправьте алгоритм

Задание 6. Определить значение переменной А в результате исполнения последовательности команд присваивания:

A:=7; B:= A; A:= 3*A – B;

Задание 7. Записать в виде команды присваивания:

Увеличить значение переменной C на 2;
Уменьшить значение переменной M в три раза;
Занести в память ЭВМ свою фамилию, имя, год рождения, используя три команды присваивания.

Задание 8. Составить алгоритм действий Удвоителя для получения числа 8 из числа 0, используя не более четырех шагов.

1.
2.
3.
4.

Задание 9. Некий человек должен перевезти в лодке через реку волка, козу и капусту. Каждый раз он может перевезти только либо волка, либо козу, либо капусту. На одном берегу нельзя оставить вместе козу и волка, а также козу и капусту.

1. Запишите систему команд исполнителя Перевозчик;

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

ТЕМА: ТИПЫАЛГОРИТМОВ

· Линейные (следования);

· Разветвляющиеся (развилка);

· Циклические.

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

Линейный – это такой алгоритм, в котором все команды выполняются строго последовательно друг за другом.

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

Разветвляющийся – это такой алгоритм, который содержит команду ветвления.

Команда ветвления - это составная команда, в которой та или иная серия команд выполняется после проверки условия.

Команда ветвления имеет полную (1) или сокращенную (2) форму:

если условие (1) то серия 1 иначе серия 2	если условие (2) то серия 1 все
Например:
алг БИД (цел а,b,у) арг а,b резу нач ввод а,b если а<b то у:=а иначе у:==b все вывод у кон

Задание.

Сформулируйте условие задачи, по предложенному алгоритму.

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

Циклический - это такой алгоритм, который содержит команду повторения.

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

Выделяется три типа команд повторения:

цикл ДЛЯ цикл ПОКА цикл ДО

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

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

нц пока условие серия команд кц

нц для х от а до b шаг серия команд кц

ПРИМЕР. Вывести нечетные числа из интервала от 1 до 10

цикл"ПОКА"	Цикл"ДО"	Цикл "ДЛЯ"

Этапы решения задач на ЭВМ

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

При работе на этом этапе необходимо ответить на вопросы:

- что дано?

- Что необходимо найти?

- Какие данные допустимы?

- При каких условиях возможно получение требуемых результатов, а при каких нет?

- Какие результаты, и в каком виде должны быть получены?

- Какие результаты будут достоверными и пра­вильными?

Математическая модель.

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