Урок

посмотрите презентацию или видеоурок по теме "Основные сведения об алгоритмах"

Теория

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

Исполнитель алгоритма – субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.

Один и тот же алгоритм может быть записан разными способами: на естественном языке, псевдокодом, с помощью блок-схем, на языке программирования и т. д.

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

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

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

Примерные задания выполняемые на уроке

Задание 1. У исполнителя Делитель две команды, которым присвоены номера:

1. раздели на 2

2. вычти 3

Первая из них уменьшает число на экране в 2 раза, вторая уменьшает его на 3. Исполнитель работает только с натуральными числами. Составьте алгоритм получения из чиcла 76 числа 5, содержащий не более 5 команд. В ответе запишите только номера команд. Если таких алгоритмов более одного, то запишите любой из них.

Решение

Оформить решение можно в виде таблицы.

• в столбце "Число" запишем исходное число 76.

• в столбце "№ команды" запишем номер одной из двух команд, учитывая что по условию задачи требуется максимально быстро и за ограниченное количество шагов алгоритма получить из числа 76 число 5. Из двух имеющихся команд, именно команда №1 быстрее всего приведет к требуемому результату. Команду №2 будем использовать в тех случаях, когда число невозможно разделить на 2 без остатка.

• в столбце "Результат" будем записывать результат выполнения алгоритма, т.е. 76 : 2 = 38, 38 : 2 = 19, 19 - 3 = 16 и т.д.

Число № команды Результат

76 1 38

38 1 19

19 2 16

16 1 8

8 2 5

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

Ответ: 11212

Задание 2. У исполнителя Бета две команды, которым присвоены номера:

1. прибавь 2;

2. умножь на b (b — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Бета увеличивает число на экране на 2, а выполняя вторую, умножает это число на b. Программа для исполнителя Бета — это последовательность номеров команд. Известно, что программа 11121 переводит число 4 в число 72. Определите значение b.

Решение

Оформить решение можно в виде таблицы.

• в столбец "№ команды" выпишем все команды.

• в столбце "Число" на первом шаге алгоритма к исходному числу 4 прибавляем 2, получается 6. На втором шаге алгоритма к 6 прибавляем 2, получается 8. На третьем шаге алгоритма к 8 прибавляем 2, получается 10. На четвертом шаге алгоритма 10 умножаем на b, получается 10b. На пятом шаге алгоритма к 10b прибавляем 2, получается 10b + 2 = 72.

• в столбце "Результат" будем записывать результат выполнения алгоритма, т.е. 4+2=6, 6+2=8 b и т.д. На последнем шаге алгоритма надо учесть, что по условию задачи должно получиться число 72.

№ команды Число Результат

1 4+2 6

1 6+2 8

1 8+2 10

2 10*b 10b

1 10b + 2 10b + 2 = 72

Решаем получившееся уравнение.

10b + 2 = 72

10b = 70

b = 7

Ответ: 7

Задание 3. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам:

1.Складываются первая и вторая, а также вторая и третья цифры исходного числа.

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

Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711.

Решение:

1.Единственный способ разбить запись 1711 на два числа – это 17 и 11.

2.Чтобы число было меньше, надо чтобы сумма первой и второй цифр была наименьшей, в данном случае 11.

3.Сумма значений двух последних цифр равна 17. Не трудно заметить, что 17 = 8 + 9 = 9 + 8. Других вариантов нет.

4.Тогда 11 = 2 + 9 = 3 + 8. Выбираем пару, которая даст ме́ньшее число.

Ответ: 298.

Домашнее задание

Прочитать §5, ответить на вопросы теста