Определения
Исполнитель в информатике — это человек, группа людей, животное, машина или другой объект (да вообще что угодно), который может понимать и выполнять некоторые формальные команды.
Алгоритм — это совокупность последовательных шагов, схема действий, приводящих к желаемому результату. Чтобы определить все возможные результаты работы алгоритма, нужно обозначить входные данные как переменные и выполнить алгоритм.
Алгоритмы можно визуально отобразить в виде блок-схем:
В этом типе задания схемы нам не понадобятся. Нужны только логика и немного знаний математики.
Примеры задач
Задача 1-го типа
Впишите правильный ответ.
У исполнителя Квадратор две команды, которым присвоены номера: 1. возведи в квадрат 2. вычти 4 Первая из них возводит число на экране во вторую степень, вторая уменьшает число на 4. Исполнитель работает только с натуральными числами. Составьте алгоритм получения из числа 2 числа 64, содержащий не более пяти команд. В ответе запишите только номера команд. (Например, 12221 –– это алгоритм: возведи в квадрат вычти 4 вычти 4 вычти 4 возведи в квадрат, который преобразует число 5 в число 169.) Если таких алгоритмов более одного, то запишите любой из них.
Логика решения:
Обозначим кнопками 1 и 2 наши возможные команды:
Этого конечно можно не делать, но в некоторых задачах можно случайно напутать номера в ответе, особенно, когда в самом содержании команды есть единицы или двойки.
Вначале нужно попытаься рассмотреть пограничные случаи: начало и конец последовательности команд. Если вспомнить из условия, что исполнитель работает только с натуральными числами (т.е. целыми положительными числами), то первое действие может быть только возведением в квадрат (команда №1):
Следующая команда может быть тоже только возведением в квадрат (ведь исполнитель работает только с натуральными числами)
Далее, получается, если мы возведём в квадрат ещё раз, то при всём желании, отнимая потом 4 несколько раз мы не получим число 64 за оставшиеся 2 попытки. Значит нам остается только команда №2 — отнимаем 4:
По такой же причине повторяем команда №2:
И нам остаётся только действие №1 (возведение в квадрат):
Ответ: 11221
Таким образом, найдя из условия, что возможным первым действием может являться только действие №1, мы по цепочке вывели все остальные. И случайный перебор использовать не нужно, тут всё строго логично.
Задача 2-го типа
У исполнителя Конструктор две команды, которым присвоены номера:
1. приписать 2
2. разделить на 2
Первая из них приписывает к числу на экране справа цифру 2, вторая делит его на 2.
Составьте алгоритм получения из числа 14 числа 9, содержащий не более 5 команд. В ответе запишите только номера команд.
(Например, 22212 –– это алгоритм:
разделить на 2
разделить на 2
разделить на 2
приписать 2
разделить на 2,
который преобразует число 8 в число 6.)
Если таких алгоритмов более одного, запишите любой из них.
Логика решения:
Для собственного контроля, вначале лучше изобразить визуально кнопки команд, на которые жмёт исполнитель:
Опять рассматриваем пограничные случаи в последовательности команд.
Нам нужно получить из числа 14 — число 9. Значит последней командой не может быть команда №1, которая приписывает справа к числу цифру 2, ведь у нас число 9 в результате. Значит последняя команда — это команда №2:
Размышляем дальше. Число 18 также не могло быть получено командой №1, значит была снова команда №2:
И снова, по той же причине число 36 могло быть получено только при помощи команда №2:
Теперь нам нужно получить из числа 14 число 72 за 2 попытки. Легко догадаться, что для этого нужно разделить 14 на 2, получим 7, и приписать двойку:
Ответ: 21222
Шпаргалка. Признаки делимости чисел
Признак делимости на 2
Число делится на 2, если его последняя цифра чётная (0, 2, 4, 6, 8).
Пример: 348 делится на 2, так как последняя цифра — 8 (чётная)
Признак делимости на 3
Число делится на 3, если сумма всех его цифр делится на 3.
Пример: 123 (1 + 2 + 3 = 6, а 6 делится на 3).
Признак делимости на 4
Число делится на 4, если число, составленное из его двух последних цифр, делится на 4.
Пример: 312 делится на 4, так как 12 делится на 4
Признак делимости на 5
Число делится на 5, если его последняя цифра — 0 или 5.
Пример: 245 делится на 5, так как заканчивается на 5.
Признак делимости на 6
Число делится на 6, если оно делится на 2 и на 3 одновременно.
Пример: 108 делится на 6, так как оно чётное и сумма его цифр (1 + 0 + 8 = 9) делится на 3.
Признак делимости на 7
Число делится на 7, если разница между этим числом без последней цифры и удвоенной последней цифрой делится на 7
Признак делимости на 8
Число делится на 8, если число, составленное из его трёх последних цифр, делится на 8.
Пример: 2 456 делится на 8, так как 456 делится на 8.
Признак делимости на 9
Число делится на 9, если сумма всех его цифр делится на 9.
Пример: 729 (7 + 2 + 9 = 18, а 18 делится на 9).
Признак делимости на 10
Число делится на 10, если его последняя цифра — 0.
Пример: 1 230 делится на 10
Признак делимости на 11
Число делится на 11, если разность суммы цифр на нечётных местах и суммы цифр на чётных местах делится на 11.
Пример: 572 (5 + 2 - 7 = 0, а 0 делится на 11)
Заключение
Все задачи этой темы содержат “ключ” к решению, который исключает необходимость перебора. Нужно внимательно вчитаться в условие и тогда найти алгоритм решения несложно.
