Более сложные исполнители (страница 4)
Исполнитель обезьянка живет на числовой оси. Начальное положение обезьянки точка 0. Система команд исполнителя:
1. Вверх k;
2. Вниз 3;
Определите наименьшее число k ( k > 1 ), если при конечном положении 16 команда (2) встречалась в программе минимум 3 раза.
Пусть \(x\) – количество команд (1), а \(y\) – количество команд (2). Тогда верно равенство:
\(kx - 3y = 16;\)
\(kx = 16 + 3y;\)
Так как команда (2) встречалась в программе минимум 3 раза - то есть 3 или больше, попробуем найти такие \(x\) и \(y\), чтобы \(k\) было минимальным и больше 1.
Попробуем \(k=2\):
\(2x - 3y = 16\), при \(y \geq 3\).
Попробуем \(y = 3\): тогда \(2x = 25\), что не имеет решений, так как \(x\) натуральное.
Попробуем \(y = 4\): тогда \(x = 14\) и всё работает. Значит, ответ \(k = 2\).
Автомат получает на вход четырехзначное число \(k\). По этому числу строится новое число \(M\) по таким правилам:
1. Последняя цифра числа увеличивается на единицу;
2. Последняя цифра числа переставляется в начало числа;
3. Пункты \(1-2\) повторяются \(n\) раз.
4. Вывод получившегося числа \(M\).
Примечание: В процессе работы алгоритма не должно происходить ситуаций переполнения (когда последняя цифра числа 9 и она увеличивается на единицу)
Пример: при исходных числах \(k = 3672\) и \(n = 3\) автомат выведет число \(7833\).
Укажите наименьшее число \(k\) такое, что при \(n = 6\) сумма цифр числа \(M\) равна 31, и третья цифра числа \(M\) равна \(8\).
Запишем исходное число \(k\) в таком виде: \(x_1 : x_2 : x_3 : x_4\).
Если \(n = 6\), то новое число будет представлено в виде \((x_3+2) : (x_4+2) : (x_1+1) : (x_2+1)\). Заметим, что сумма цифр нового числа \(M\) на \(n\) больше чем сумма цифр исходного числа \(k\). Тогда сумма цифр исходного числа \(k\) есть \(25\). Также заметим, что если на третьей позиции в числе \(M\) стоит \(8\), то верно \(x_1 + 1 = 8\), откуда \(x_1 = 7\); Значит, необходимо подобрать такие \(x_1,x_3,x_4\), чтобы их сумма была равна \(18\), и число \(k\) было минимально при этом \(x_2 < 9,\) а \(x_3,x_4 < 8.\) Подбор можно осуществить, постепенно увеличивая \(x_2\), начиная с 0, и подбирая \(x_3\) и \(x_4\) под это значение \(x_2\) так, чтобы сумма была равна 18. Таким образом, первое значение \(k\), у которого \(x_2 < 9,\) а \(x_3,x_4 < 8\), будет равно \(7477\). Так как мы перебирали снизу и ничего улучшить уже нельзя (переставить цифры, например, чтобы уменьшить), это и есть ответ.
Исполнитель обезьянка живет на числовой оси. Начальное положение обезьянки точка 0. Система команд исполнителя:
1. Вверх k;
2. Вниз 4;
Определите наименьшее число k ( k > 1 ), если при конечном положении 18 команда (2) встречалась в программе минимум 3 раза.
Пусть \(x\) – количество команд (1), а \(y\) – количество команд (2). Тогда верно равенство:
\(kx - 4y = 18;\)
\(kx = 18 + 4y;\)
Т.к. данное выражение может быть верным при \(y\) хотя бы 3, подставим его в выражение. Тогда \(kx = 30\). Откуда \(k\) – делитель числа \(30\). Значит, \(K = \{1,2,3,5,6,10,15,30\}.\) Т.к по условию необходимо найти минимальное \(k,\) которое больше единицы, выбираем \(K = 2.\)
Некий крабоед-исполнитель умеет делать всего две команды, которым присвоены номера:
1. вычти 1
2. умножь на три
Первая из них уменьшает число на экране на 1, вторая — утраивает его. Запишите порядок команд в программе получения из 9 числа 17, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.
Например, 21211 — это программа:
умножь на три
вычти 1
умножь на три
вычти 1
вычти 1,
которая преобразует число 2 в 13.
В решении этой задачи удобнее приводить конечное число к начальному с помощью противоположных команд. То есть в нашем случае мы пойдем от числа 17 к числу 9 с помощью команд “прибавь 1” и “раздели на 3”.
Так как 17 не кратно трём, добавим к числу единицу, получим 18 и поделим его на 3. Получаем 6 и три раза добавляем по единице. Получили последовательность команд:
\(1.\;17+1=18\)
\(2.\; 18/3=6\)
\(1.\;6+1=7\)
\(1.\;7+1=8\)
\(1.\;8+1=9\)
Поскольку мы решали задачу “от противного”, записываем команды в обратном порядке и записываем ответ.
Некий крабоед-исполнитель умеет делать всего две команды, которым присвоены номера:
1. вычти 1
2. умножь на три
Первая из них уменьшает число на экране на 1, вторая — утраивает его. Запишите порядок команд в программе получения из 5 числа 7, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.
Например, 21211 — это программа:
умножь на три
вычти 1
умножь на три
вычти 1
вычти 1,
которая преобразует число 2 в 13.
В решении этой задачи удобнее приводить конечное число к начальному с помощью противоположных команд. То есть в нашем случае мы пойдем от числа 7 к числу 5 с помощью команд “прибавь 1” и “раздели на 3”.
Так как 7 не кратно трём, добавим к числу два раза единицу, получим 9 и поделим его на 3. Получаем 3 и два раза добавляем по единице. Получили последовательность команд:
\(1.\;7+1=8\)
\(1.\;8+1=9\)
\(2.\; 9/3=3\)
\(1.\;3+1=4\)
\(1.\;4+1=5\)
Поскольку мы решали задачу “от противного”, записываем команды в обратном порядке и получаем ответ.
Примечение. В данной задаче программа вышла симметричной, поэтому порядок записи не имеет значения, но в аналогичных задачах необходимо записывать команды в обратном порядке, так как мы решаем задачу “от противного”.
Некий крабоед-исполнитель умеет делать всего две команды, которым присвоены номера:
1. вычти 1
2. умножь на два
Первая из них уменьшает число на экране на 1, вторая — удваивает его. Запишите порядок команд в программе получения из 6 числа 17, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.
Например, 21211 — это программа:
умножь на два
вычти 1
умножь на два
вычти 1
вычти 1,
которая преобразует число 3 в 8 .
В решении этой задачи удобнее приводить конечное число к начальному с помощью противоположных команд. То есть в нашем случае мы пойдем от числа 17 к числу 6 с помощью команд “прибавь 1” и “раздели на 2”.
Так как 17 не кратно двум, добавим единицу и поделим на 2, получаем 9. 9 не является четным, поэтому добавляем единицу и делим на 2 для получения наименьшего результата — 5. Затем добавляем единицу и приходим к 6. Получили последовательность команд:
\(1.\;17+1=18\)
\(2.\; 18/2=9\)
\(1.\;9+1=10\)
\(2.\; 10/2=5\)
\(1.\;5+1=6\)
Поскольку мы решали задачу “от противного”, записываем команды в обратном порядке и получаем ответ.
Некий крабоед-исполнитель умеет делать всего две команды, которым присвоены номера:
1. вычти 1
2. умножь на два
Первая из них уменьшает число на экране на 1, вторая — утраивает его. Запишите порядок команд в программе получения из 5 числа 13, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.
Например, 21211 — это программа:
умножь на два
вычти 1
умножь на два
вычти 1
вычти 1,
которая преобразует число 3 в 8 .
В решении этой задачи удобнее приводить конечное число к начальному с помощью противоположных команд. То есть в нашем случае мы пойдем от числа 13 к числу 5 с помощью команд “прибавь 1” и “раздели на 2”.
Так как 13 не является четным числом, добавим единицу и разделим на 2, получаем 7. Затем добавляем еще единицу и опять делим на 2, получаем 4. Прибавляем единицу и приходим к 5. Получили последовательность команд:
\(1.\;13+1=14\)
\(2.\; 14/2=7\)
\(1.\;7+1=8\)
\(2.\; 8/2=4\)
\(1.\;4+1=5\)
Поскольку мы решали задачу “от противного”, записываем команды в обратном порядке и получаем ответ.
