Вычислительная машина работает по следующему алгоритму
Вычислительная машина работает по следующему алгоритму
Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. В конец записи (справа) добавляется (дублируется) последняя цифра.
3. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 1101.
2. Дублируется последняя цифра, новая запись 11011.
3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.
4. На экран выводится число 54.
Какое наименьшее число, большее 105, может появиться на экране в результате работы автомата?
Рассмотрим числа, большие 105, и найдем наименьшее число, которое является результатом работы алгоритма.
106 = 11010102 — не является результатом работы алгоритма.
107 = 11010112 — не является результатом работы алгоритма.
108 = 11011002 — не является результатом работы алгоритма.
109 = 11011012 — не является результатом работы алгоритма.
110 = 11011102 — не является результатом работы алгоритма.
111 = 11011112 — является результатом работы алгоритма для числа 110112.
Вычислительная машина работает по следующему алгоритму
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 7 – Кузнечик прыгает вперёд на 7 единиц,
Назад 5 – Кузнечик прыгает назад на 5 единиц.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 5», чтобы Кузнечик оказался в точке 19?
Обозначим через 
количество команд «Вперед 7» в программе, а через 
– количество команд «Назад 5», причём и y могут быть только неотрицательными целыми числами.
Для того, чтобы КУЗНЕЧИК попал в точку 19 из точки 0, должно выполняться условие:
Представим его в виде: 
Из последнего уравнения видно, что левая часть должна делиться на 5.
Из всех решений нас интересует такое, при котором y – наименьшее возможное число.
Используем метод подбора:
Наименьшее число команд «Назад 5» 
.
Вычислительная машина работает по следующему алгоритму
Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
4. Новое число вычитается из исходного, полученная разность выводится на экран.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1011.
2. Удаляется первая единица и следующий за ней ноль: 11.
3. Десятичное значение полученного числа 3.
4. На экран выводится число 11 – 3 = 8.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?
Заметим, что при удалении первой единицы и всех стоящих сразу за ней нулей из числа вычитается 2 в степени, равной номеру старшего разряда в двоичной записи числа. Значит, нужно найти количество степеней двойки, которые находятся между 10 и 1000. Также необходимо учесть, что числа от 10 до 15 будут соответствовать предыдущей степени двойки. Значит, к количеству степеней двойки, входящих в диапазон чисел от 10 до 1000, необходимо добавить единицу. Всего в диапазоне от 10 до 1000 шесть степеней двойки. Следовательно, будет показано 6 + 1 = 7 различных чисел.
Заметим, что число 0 не может являться результатом работы алгоритма. Если на вход подается число, равное степени двойки, то после выполнения шага 2 (удаления первой единицы из этого числа) получается 0. На шаге 4 из исходного числа вычитается 0, и получается исходное число, равное степени двойки.
Вычислительная машина работает по следующему алгоритму
Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
4. Новое число вычитается из исходного, полученная разность выводится на экран.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1011.
2. Удаляется первая единица и следующий за ней ноль: 11.
3. Десятичное значение полученного числа 3.
4. На экран выводится число 11 – 3 = 8.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 100 до 3000?
Заметим, что при удалении первой единицы и всех стоящих сразу за ней нулей из числа вычитается 2 в степени, равной номеру старшего разряда в двоичной записи числа. Значит, нужно найти количество степеней двойки, которые находятся между 100 и 3000. Также необходимо учесть, что числа от 100 до 128 будут соответствовать предыдущей степени двойки. Значит, к количеству степеней двойки, входящих в диапазон чисел от 100 до 3000, необходимо добавить единицу. Всего в диапазоне от 100 до 3000 пять степеней двойки. Следовательно, будет показано 5 + 1 = 6 различных чисел.
Заметим, что при вводе числа, равного степени двойки, на экран будет выведено именно это число (из него удалится первая единица и все следующие за ней нули, результат окажется равен 0, и при вычитании этого нуля из исходного числа останется исходное число).