какое наименьшее трехзначное число может появиться на экране в результате работы автомата
Какое наименьшее трехзначное число может появиться на экране в результате работы автомата
Автомат обрабатывает натуральное число 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.
Какое наименьшее трехзначное число может появиться на экране в результате работы автомата
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.
1. Строится двоичная запись числа N.
2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.
3. Предыдущий пункт повторяется для записи с добавленной цифрой.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 1101.
2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.
3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.
4. На экран выводится число 54.
Какое наибольшее число, меньшее 90, может появиться на экране в результате работы автомата?
Рассмотрим числа, меньшие 90, и определим наибольшее из них, которое может являться результатом работы алгоритма:
8910 = 101 10012 — не может являться результатом работы алгоритма.
8810 = 101 10002 — не может являться результатом работы алгоритма.
8710 = 101 01112 — не может являться результатом работы алгоритма.
8610 = 101 01102 — может являться результатом работы алгоритма.
Какое наименьшее трехзначное число может появиться на экране в результате работы автомата
Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится троичная запись числа N.
2. В конец записи (справа) дописывается остаток от деления числа N на 3.
3. Результат переводится из троичной системы в десятичную и выводится на экран.
Пример. Дано число N = 11. Алгоритм работает следующим образом:
1. Троичная запись числа N: 102.
2. Остаток от деления 11 на 3 равен 2, новая запись 1022.
3. На экран выводится число 35.
Какое наименьшее трёхзначное число может появиться на экране в результате работы автомата?
Рассмотрим числа, большие 99, и определим наименьшее из них, которое может являться результатом работы алгоритма. Заметим, что остаток от деления числа на 3 — это последняя цифра троичной записи числа. В соответствии с заданным алгоритмом эта цифра дописывается справа от записи числа. Таким образом, получающееся в результате работы автомата число должно иметь в троичной записи в конце две одинаковые цифры.
10010 = 102013 — не может являться результатом работы алгоритма.
10110 = 102023 — не может являться результатом работы алгоритма.
10210 = 102103 — не может являться результатом работы алгоритма.
10310 = 102113 — может являться результатом работы алгоритма.
Таким образом, ответ — 103.
По каналу связи передавались данные в виде последовательности положительных целых чисел. Количество чисел заранее неизвестно, но не менее двух, признаком конца данных считается число 0. Контрольное значение равно такому максимально возможному произведению двух чисел из переданного набора, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Программа должна напечатать одно число — вычисленное контрольное значение, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит количество чисел N (1 ≤ N ≤ 100000). В каждой из N строк записано одно натуральное число, не превышающее 1000.
Пример организации исходных данных во входном файле:
Пример выходных данных для приведённого выше примера входных данных:
В ответе укажите два числа: сначала значение искомого произведения для файла А, затем для файла B.
Произведение двух чисел будет кратно 7 и не кратно 49 в том и только в том случае, когда один из сомножителей делится на 7 и при этом не делится на 49, а второй — не делится на 7. Произведение будет максимальным, если оба сомножителя будут максимально возможными в своих группах. Искомое произведение не существует (контрольное значение считается равным 1), если в одной из указанных групп не окажется ни одного числа.
Программа читает входные данные, не запоминая числа в массиве, и находит два максимальных значения: максимум из чисел, кратных 7 и при этом не кратных 49, и максимум из чисел, не кратных 7. Затем программа вычисляет контрольное значение, равное произведению этих двух максимумов, и сравнивает его с введённым контрольным значением.
Приведём решение задачи на языке Pascal.
while true do begin
if (k mod 7 <> 0) and (k>m) then m:=k;
if (k mod 7 = 0) and (k mod 49 <> 0) and (k>m7)
В результате работы данного алгоритма при вводе данных из файла A ответ — 847280, из файла B — 994000.
Приведём решение Романа Князева на языке Python.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится троичная запись числа N.
2. В конец записи (справа) дописывается остаток от деления числа N на 3.
3. Результат переводится из троичной системы в десятичную и выводится на экран.
Пример. Дано число N = 11. Алгоритм работает следующим образом:
1. Троичная запись числа N: 102.
2. Остаток от деления 11 на 3 равен 2, новая запись 1022.
3. На экран выводится число 35.
Какое наименьшее четырёхзначное число может появиться на экране в результате работы автомата?
Рассмотрим числа, большие 999, и определим наименьшее из них, которое может являться результатом работы алгоритма. Заметим, что остаток от деления числа на 3 — это последняя цифра троичной записи числа. В соответствии с заданным алгоритмом эта цифра дописывается справа от записи числа. Таким образом, получающееся в результате работы автомата число должно иметь в троичной записи в конце две одинаковые цифры.
100010 = 11010013 — не может являться результатом работы алгоритма.
100110 = 11010023 — не может являться результатом работы алгоритма.
100210 = 11010103 — не может являться результатом работы алгоритма.
100310 = 11010113 — может являться результатом работы алгоритма.
Таким образом, ответ — 1003.
Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.
3. Предыдущий пункт повторяется для записи с добавленной цифрой.
4. Результат переводится в десятичную систему.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 1101.
2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.
3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.
4. Результат работы алгоритма R = 54.
При каком наименьшем числе N в результате работы алгоритма получится R > 170? В ответе запишите это число в десятичной системе счисления.
Если изначально сумма разрядов была чётная, то в конец запишется 00, что эквивалентно 
Если же сумма была нечётная, то запишется 10, что эквивалентно 
В обоих случаях число получается чётным.
Посмотрим на чётные числа, превосходящие 170.
— на конце 00, но сумма остальных разрядов чётна. Число подходит под первый случай, значит, число, из которого оно было получено, равно 
Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.
3. Предыдущий пункт повторяется для записи с добавленной цифрой.
4. Результат переводится в десятичную систему.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 1101.
2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.
3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.
4. Результат работы алгоритма R = 54.
При каком наименьшем числе N в результате работы алгоритма получится R > 154? В ответе запишите это число в десятичной системе счисления.
Если изначально сумма разрядов была чётная, то в конец запишется 00, что эквивалентно
Если же сумма была нечётная, то запишется 10, что эквивалентно
В обоих случаях число получается чётным.
Посмотрим на чётные числа, превосходящие 170.
— на конце 00, но сумма остальных разрядов чётна. Число подходит под первый случай, значит, число, из которого оно было получено, равно 
Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Вместо последней (самой правой) двоичной цифры дважды записывается вторая слева цифра двоичной записи.
3. Результат переводится в десятичную систему.
Пример. Дано число N = 19. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 10011.
2. Вторая слева цифра 0, единица в конце записи заменяется на два нуля, новая запись 100100.
3. Результат работы алгоритма R = 36.
При каком наименьшем числе N в результате работы алгоритма получится R > 92? В ответе запишите это число в десятичной системе счисления.
Число на выходе должно превышать 9210 = 10111002. Заметим, что можно рассматривать только те числа, большие 9210, у которых в двоичной записи на конце стоят либо две единицы, либо два нуля. Также заметим, что для числа 9210 исходными числами могли быть либо 1011102, либо 1011112, ни одно из них нам не подходит, поскольку после работы алгоритма не получится числа, большего 92. Рассмотрим числа 1100002 и 1100012. Первое из них меньше, применим алгоритм к нему. В результате работы алгоритма получится число 11000112 = 99, что больше 92.
Таким образом, ответ — 1100002 = 4810.
Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Вместо последней (самой правой) двоичной цифры дважды записывается вторая слева цифра двоичной записи.
3. Результат переводится в десятичную систему.
Пример. Дано число N = 19. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 10011.
2. Вторая слева цифра 0, единица в конце записи заменяется на два нуля, новая запись 100100.
3. Результат работы алгоритма R = 36.
При каком наименьшем числе N в результате работы алгоритма получится R > 76? В ответе запишите это число в десятичной системе счисления.
Число на выходе должно превышать 7610 = 10011002. Заметим, что можно рассматривать только те числа, большие 7610, у которых в двоичной записи на конце стоят либо две единицы, либо два нуля. Также заметим, что для числа 7610 исходными числами могли быть либо 1001102, либо 1001112, ни одно из них нам не подходит, поскольку после работы алгоритма не получится числа, большего 76. Рассмотрим числа 1010002 и 1010012. Первое из них меньше, применим алгоритм к нему. В результате работы алгоритма получится число 10100002 = 80, что больше 76.
Таким образом, ответ — 1010002 = 4010.
Приведем другое решение.
Заметим, что в результате применения алгоритма к числам, различающимся только последней цифрой двоичной записи, получаются одинаковые результаты. В остальных случаях большим исходным числам соответствует больший результат. Рассмотрим числа, большие 7610 = 10011002, и выберем наименьшее из них, которое может являться результатом работы алгоритма:
7710 = 10011012 — не может являться результатом работы алгоритма.
7810 = 10011102 — не может являться результатом работы алгоритма.
7910 = 10011112 — не может являться результатом работы алгоритма.
8010 = 10100002 — может являться результатом работы алгоритма, может быть получено из числа 1010002 = 4010.
Таким образом, ответ — 1010002 = 4010.
Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:
Выполняя команду номер 1, КАЛЬКУЛЯТОР умножает число на экране на 2, а выполняя команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не более 5 команд, которая из числа 7 получает число 44. Укажите лишь номера команд.
Например, программа 11221 — это программа:
которая преобразует число 5 в число 32.
Умножение на число обратимо не для любого числа, поэтому, если мы пойдём от числа 44 к числу 7, тогда однозначно восстановим программу. Полученные команды будут записываться справа налево.
Так как нужно получить не более 5 команд, выгодно использовать деление на 2: 44 = 22 · 2 (команда 1). Подобное рассуждение не подходит для числа 22, так как ( 22 = 11 · 2) из числа 11 мы не сможем имеющимися операциями получить число 2, выполним при этом не более пяти команд. Тогда: 22 = 24 − 2 (команда 2). Повторим первое рассуждение для числа 24, второе для числа 12 и первое для числа 14.
Окончательный ответ: 12121.
Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу
Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?
Если робот пойдёт назад тем же путём, каким пришёл в конечную клетку, то он точно не разрушится. Группа команд 1324 круговая, поэтому её можно откинуть. До конечной клетки робот прошёл путём 132. Значит, чтобы попасть обратно, ему нужно заменить команды на противоположные (241) и записать их справа налево: 142.
Исполнитель КВАДРАТОР имеет только две команды, которым присвоены номера:
1. возведи в квадрат
Выполняя команду номер 1, КВАДРАТОР возводит число на экране в квадрат, а выполняя команду номер 2, прибавляет к этому числу 1. Напишите программу, содержащую не более 4 команд, которая из числа 1 получает число 17. Укажите лишь номера команд.
(Например, программа 12122 — это программа:
которая преобразует число 1 в число 6).
Не любое число является квадратом целого числа, поэтому, если мы пойдём от числа 17 к числу 1, тогда однозначно восстановим программу. Полученные команды будут записываться справа налево.
1) Число 17 не является квадратом, значит, оно получено добавлением единицы к числу 16: 17 = 16 + 1 (команда 2).
2) Т. к. мы хотим получить не более 4 команд, то для получения числа 16 возведём в квадрат 4: 16 = 4 2 (команда 1).
Повторим рассуждение 2) для числа 4: 4 = 2 2 (команда 1), а для числа 2 применим рассуждение 1): 2 = 1 + 1 (команда 2).
Тогда окончательно получаем ответ: 2112.
Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу
Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?
Если робот пойдёт назад тем же путём, каким пришёл в конечную клетку, то он точно не разрушится. Группа команд 3241 круговая, поэтому её можно откинуть. До конечной клетки робот прошёл путём 242. Значит, чтобы попасть обратно, ему нужно заменить команды на противоположные (131) и записать их справа налево: 131.
У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:
Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, причём на место освободившегося бита ставится 0. Выполняя вторую команду исполнитель вычитает из числа 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд 112112. Запишите результат в десятичной системе.
Если в старшем разряде двоичного числа нет единицы, то команда 1 удваивает число, если единица есть (т. е. десятичное число не меньше 128), то выводится остаток от деления удвоенного числа на 256. Таким образом, получим следующее:
1: 182 => 108 (остаток от 364 / 256 ),
1: 214 => 172 (остаток от 428 / 256 ),
Заметим, что в соответствии с условием программа работает с однобайтовыми числами. Если в старшем разряде числа стоит единица, то при сдвиге числа влево эта единица выходит за разрядную сетку и теряется. В результате при применении операции сдвига к числу, превышающему 127, то есть имеющему единицу в старшем разряде, получается остаток от деления данного числа на 256.
Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:
Вперед N (Кузнечик прыгает вперед на N единиц);
Назад M (Кузнечик прыгает назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?
Обозначим через 
количество команд «Вперед 3» в программе, а через 
– количество команд «Назад 2», причём и 
могут быть только неотрицательными целыми числами.
Всего кузнечик сделал 
команд. Отсюда найдём 
. Посчитаем, в какую точку попадёт Кузнечик после выполнения указанных команд:
В эту точку можно попасть из исходной, выполнив команду «Назад 5».
Какое наименьшее трехзначное число может появиться на экране в результате работы автомата
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.
1. Строится двоичная запись числа N.
2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.
3. Предыдущий пункт повторяется для записи с добавленной цифрой.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 1101.
2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.
3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.
4. На экран выводится число 54.
Какое наибольшее число, меньшее 100, может появиться на экране в результате работы автомата?
Рассмотрим числа, меньшие 100, и определим наибольшее из них, которое может являться результатом работы алгоритма:
9910 = 110 00112 — не может являться результатом работы алгоритма.
9810 = 110 00102 — не может являться результатом работы алгоритма.
9710 = 110 00012 — не может являться результатом работы алгоритма.
9610 = 110 00002 — может являться результатом работы алгоритма.
Какое наименьшее трехзначное число может появиться на экране в результате работы автомата
Факториалом натурального числа n (обозначается n!) называется произведение всех натуральных чисел от 1 до n. Например, 4! = 1 · 2 · 3 · 4 = 24.
Дано целое положительное число A. Необходимо найти ближайшее к A число, которое является точным факториалом какого-либо натурального числа. Если два точных факториала одинаково близки к A, нужно выбрать меньший из них. Например, для A = 15 нужно получить ответ 6, а для A = 20 – ответ 24.
Для решения этой задачи ученик написал программу, но, к сожалению, его программа неправильная.
Ниже эта программа для Вашего удобства приведена на пяти языках программирования.
DIM A, K, F AS INTEGER
WHILE F = F \ K − A THEN
while f = f div k − a
нц пока f = div(f,k) − a
using namespace std;
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе A = 5.
2. Приведите пример числа A, при котором программа выведет верный ответ. Укажите этот ответ.
3. Найдите в программе все ошибки (известно, что их не больше двух) и исправьте их. Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.
Достаточно указать ошибки и способ их исправления для одного языка программирования.
Обратите внимание: Вам нужно исправить приведённую программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять строки или добавлять новые. Заменять следует только ошибочные строки: за исправления, внесённые в строки, не содержащие ошибок, баллы будут снижаться.
1. При вводе A = 5 программа выведет число 3.
2. Программа выводит верный ответ при вводе A = 1 (ответ 1) или A = 2 (ответ 2).
3. Программа содержит две ошибки.
1) Ошибочная проверка. После завершения цикла гарантированно выполняется неравенство F ≥ A > F/A, поэтому в сравнении после цикла левая часть всегда неотрицательна, а правая — отрицательна. Сравнение оказывается всегда верным, в результате выбирается не ближайший к A точный факториал, а ближайший, не превосходящий A.
2) Ошибочный вывод. Вместо значения факториала F выводится «основание» факториала K.
Пример исправления для языка Паскаль:
if f − a >= f div k − a
if f − a >= a − f div k
Возможно также использование функции abs (модуль числа):
if f − a >= abs(f div k − a)
Функцию abs можно использовать и в левой части сравнения. Это ничего не меняет по сути, так как левая часть заведомо неотрицательна, но такое использование нельзя считать ошибкой:
if abs(f − a) >= abs(f div k − a)
При использовании модуля для исправлении фрагмента на алгоритмическом языке следует использовать функцию iabs (модуль для целых чисел):
если f − a >= iabs(div(f,k) − a)
Использование в алгоритмическом языке функции abs вместо iabs отмечается как ошибка, но не влияет на оценку работы.
В программах на других языках ошибочные строки и их исправления аналогичны.
Незначительной опиской, не влияющей на оценку, следует считать отсутствие служебных слов и знаков после содержательной части исправления.