Алгоритмы
Выписка из кодификатора 2012
1.6
| Элементы теории алгоритмов
| 1.6.1
| Формализация понятия алгоритма
| | 1.6.2 | Вычислимость. Эквивалентность алгоритмических моделей | | 1.6.3 | Построение алгоритмов и практические вычисления |
Выписка из спецификации 2012 №
| Задание | Элемент содержания | Уровень сложности | | 5 | А5 |
1.6.1 Формальное исполнение алгоритма, записанного на естественном языке
| Базовый | | 13 | А13 | 1.6.3 Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд
| Повышенный | | 15 | В2 | 1.6.2 Умение создавать линейный алгоритм для формального исполнителя | Базовый | | 20 | В7 | 1.6.1 Анализ алгоритма, содержащего вспомогательные алгоритмы, циклы и ветвление | Повышенный | | 26 | В13 | 1.6.1 Умение анализировать результат исполнения алгоритма | Повышенный | | 31 | С3 | 1.6.3 Умение построить дерево по заданному алгоритму и обосновать результат построения | Высокий |
- Линейные алгоритмы
- Алгоритмы с ветвлением
- Циклы
- Задания из вариантов ЕГЭ
Линейные алгоритмы
Простейшие задачи имеют линейный алгоритм решения.
Это означает, что он не содержит проверок условий и повторений.
Задача № 1. Пешеход шел по пересеченной местности. Его скорость
движения по равнине составляла ʋ1 км/ч, в гору – ʋ2 км/ч, под гору ʋ3 км/ч. Время движения – соответственно t1, t2 и t3ч. Какой путь прошел
пешеход?
Решение: 
Задача № 2. Дано натуральное трехзначное число n,
в записи
которого нет нулей. Составить алгоритм, который возвращает значение «истина»,
если верно утверждение: «число n кратно каждой своей цифре»,
и «ложь» — в противном случае.
Решение:
На схеме DIV и MOD — соответственно операции
деления нацело и получения остатка от целочисленного деления. В фигурных
скобках записаны пояснения (комментарии) к операторам. 
Алгоритмы с ветвлением
Достаточно
часто решение, какое из действий, записанных в алгоритме, выполнять, зависит от
значения логического выражения, выступающего в качестве условия. В таких
случаях используется развилка.
Задача № 3. Вычислить значение функции 
Решение: 
Задача № 4. Дано натуральное число n. Если число
нечетное и его удваивание не приведет к выходу за 32 767 (двухбайтовое целое
число со знаком), удвоить его, иначе оставить без изменения.
Решение:
Чтобы число n удовлетворяло условию
удваивания, одно должно быть нечетным и меньше 16 384. 
Циклы
Если какие-либо операторы необходимо выполнить
несколько раз, то их не переписывают каждый раз заново, а организуют цикл.
Задача № 5. Подсчитать количество нечетных цифр в записи
натурального числа n.
Решение: Будем удалять цифру за цифрой из младшего разряда
числа до тех пор, пока цифры числа не исчерпаются, т. е. число не станет равным
нулю. Каждую нечетную цифру будем учитывать.
Задача решена двумя способами. Слева решение
оформлено с использованием цикла с предусловием, справа – с постусловием.
 Задание А5 Определите
значение переменной А после выполнения следующего алгоритма:
1) 5
2) 11 3) 23
4) 47
Ответ: 3) 23.
Задание А13
Система команд исполнителя РОБОТ, «живущего» в прямоугольном
лабиринте на клетчатой плоскости:
вверх
вниз влево
вправо
При выполнении любой из этих команд РОБОТ
перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.
Четыре команды проверяют истинность условия
отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху
свободно снизу свободно слева свободно справа свободно
Цикл ПОКА < условие > команда
выполняется, пока условие истинно, иначе происходит
переход на следующую строку.
Сколько
клеток приведенного лабиринта соответствуют требованию, что, выполнив
предложенную ниже программу, РОБОТ
остановится в той же клетке, с которой он начал движение? |
НАЧАЛО
ПОКА < снизу свободно > вниз
ПОКА < слева свободно > влево
ПОКА < сверху свободно > вверх
ПОКА < справа свободно > вправо
КОНЕЦ
| 
|
1) 1 2)
2 3) 3
4) 0
Решение: Изобразим движение Робота согласно алгоритма при
помощи графа и получим:  
Воспользовавшись, полученным шаблоном, проверим возможные
перемещения Робота, 
Получаем, что только из одной клетки можно начинать
движение Робота.
Ответ:
1) 1
Задание В2
У исполнителя Калькулятор две команды, которым присвоены
номера:
1. прибавь 2
2. умножь на
3
Выполняя первую из них, Калькулятор прибавляет к
числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в
программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь
номера команд. (Например, программа 21211 – это программа:
умножь на 3
прибавь 2
умножь на 3
прибавь 2
прибавь 2,
которая преобразует число 1 в 19.)
Решение: 
Ответ: 121211
| 
