сборник заданий №5 ЕГЭ. Выполнение и анализ простых алгоритмов
 Скачать 1.15 Mb.
|
|
Е. Джобс) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописывается 1, в противном случае справа дописывается 0. 3) Пункт 2 повторяется ещё один раз. Например, двоичная запись 1001 числа 9 будет преобразована в 100101. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа – результата работы данного алгоритма. Укажите максимальное число N, для которого результат работы алгоритма будет меньше 171. В ответе это число запишите в десятичной системе счисления. 237) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоичная запись числа N. 2) К этой записи справа дописывается 0, если число нечетное, и слева 1 в обратном случае. 3) Если единиц в двоичном числе получилось четное количество, справа дописывается 1, иначе 0. Например, двоичная запись 1010 числа 10 будет преобразована в 110100. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа – результата работы данного алгоритма. Укажите минимальное число N, для которого результат работы алгоритма будет больше 228. В ответе это число запишите в десятичной системе счисления. 34 238) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) К десятичной записи справа приписывается последняя цифра числа N. 2) Получившееся число переводится в двоичное представление. 3) К двоичной записи этого числа справа дописывается бит четности, единица, если количество единиц в двоичной записи нечетно, 0 - если четно. 4) Полученное в результате этих операций число переводится в десятичную систему счисления. Пример. Дано число 13. Оно преобразуется следующим образом: 13 133 10000101 2 100001011 2 267. Укажите минимальное число N, после обработки которого получится число, превышающее 413. 239) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) В шестеричной записи числа N дублируется последняя цифра. 2) Получившееся число переводится в двоичное представление. 3) В получившейся записи дублируется последняя цифра. 4) Полученное в результате этих операций число переводится в десятичную систему счисления. Пример. Дано число 13. Оно преобразуется следующим образом: 13 21 6 211 6 1001111 2 10011111 2 159. Укажите максимальное число, которое может являться результатом выполнения алгоритма, меньшее 344. 240) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Строится двоично-десятичное представление – каждый разряд десятичного числа кодируется с помощью 4 битов, затем полученные коды записываются друг за другом с сохранением незначащих нулей. 2) Полученная двоичная последовательность инвертируется – все нули меняются на единицы, а все единицы на нули. 3) Полученное в результате этих операций число переводится в десятичную систему счисления. Пример. Дано число 13. Оно преобразуется следующим образом: 13 00010011 ДД 11101100 2 236. Здесь нижний индекс «ДД» обозначает двоично-десятичную систему. Укажите число N, в результате обработки которого с помощью этого алгоритма получается число 151. 241) На вход алгоритма подаётся натуральное число N < 256. Алгоритм строит по нему новое число R следующим образом. 1) Строится восьмибитная двоичная запись числа. 2) Полученное в п.1 число записывается справа налево (переворачивается), 3) Из первого числа вычитается второе, результат записывается в десятичной системе счисления. Найдите максимальное возможное число, которое может являться результатом работы алгоритма. 242) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наименьшем исходном числе N > 65 в результате работы алгоритма получится число, кратное 4? 243) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наименьшем исходном числе N > 80 в результате работы алгоритма получится число, кратное 4? 35 244) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наименьшем исходном числе N > 95 в результате работы алгоритма получится число, кратное 4? 245) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 100 в результате работы алгоритма получится число, кратное 4? 246) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 90 в результате работы алгоритма получится число, кратное 4? 247) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 70 в результате работы алгоритма получится число, кратное 4? 248) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наименьшем исходном числе N > 100 в результате работы алгоритма получится чётное число, которое не делится на 4? 249) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наименьшем исходном числе N > 90 в результате работы алгоритма получится чётное число, которое не делится на 4? 36 250) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наименьшем исходном числе N > 60 в результате работы алгоритма получится чётное число, которое не делится на 4? 251) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 100 в результате работы алгоритма получится чётное число, которое не делится на 4? 252) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 80 в результате работы алгоритма получится чётное число, которое не делится на 4? 253) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 750 в результате работы алгоритма получится чётное число, которое не делится на 4? 254) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 100 в результате работы алгоритма получится число, которое делится на 4 и не делится на 8? 255) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 500 в результате работы алгоритма получится число, которое делится на 4 и не делится на 8? 37 256) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления. При каком наименьшем исходном числе N > 100 в результате работы алгоритма получится число, которое делится на 4 и не делится на 8? 257) (Е. Джобс) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2. 3. Если количество единиц в двоичной записи числа N больше количества нулей, справа дописывается 0, иначе 1. 4. Результат переводится в десятичную систему счисления. Какое наименьшее число, большее 80, может получиться в результате работы автомата? 258) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2. 3. Если количество единиц в двоичной записи числа N больше количества нулей, справа дописывается 0, иначе 1. 4. Результат переводится в десятичную систему счисления и выводится на экран. Сколько различных чисел, принадлежащих отрезку [50; 80], может получиться в результате работы автомата? 259) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. В этой записи последний ноль заменяется на первые две цифры полученной записи. Если нуля нет, алгоритм аварийно завершается. 3. Запись записывается справа налево (в обратную сторону). 4. Результат переводится в десятичную систему счисления. Для какого максимального значения N в результате работы алгоритма получится число 119? 260) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. В этой записи последний ноль заменяется на первые две цифры полученной записи. Если нуля нет, алгоритм аварийно завершается. 3. Запись записывается справа налево (в обратную сторону). 4. Результат переводится в десятичную систему счисления. Для какого минимального значения N в результате работы алгоритма получится число 123? 261) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N. 2. В этой записи последний ноль заменяется на первые две цифры полученной записи. Если нуля нет, алгоритм аварийно завершается. 3. Запись записывается справа налево (в обратную сторону). 4. Результат переводится в десятичную систему счисления. Для скольких значений N в результате работы алгоритма получится число 127? 262) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1) Если исходное число кратно 2, оно делится на 2, иначе из него вычитается 1. 2) Если полученное на предыдущем шаге число кратно 3, оно делится на 3, иначе из него вычитается 1. 3) Если полученное на предыдущем шаге число кратно 5, оно делится на 5, иначе из него вычитается 1. 4) Число, полученное на шаге 3, считается результатом работы алгоритма. Сколько существует различных натуральных чисел N, при обработке которых получится R = 3? 38 263) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1) Если исходное число кратно 2, оно делится на 2, иначе из него вычитается 1. 2) Если полученное на предыдущем шаге число кратно 3, оно делится на 3, иначе из него вычитается 1. 3) Если полученное на предыдущем шаге число кратно 7, оно делится на 7, иначе из него вычитается 1. 4) Число, полученное на шаге 3, считается результатом работы алгоритма. Сколько существует различных натуральных чисел N, при обработке которых получится R = 2? 264) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1) Если исходное число кратно 2, оно делится на 2, иначе из него вычитается 1. 2) Если полученное на предыдущем шаге число кратно 5, оно делится на 5, иначе из него вычитается 1. 3) Если полученное на предыдущем шаге число кратно 7, оно делится на 7, иначе из него вычитается 1. 4) Число, полученное на шаге 3, считается результатом работы алгоритма. Сколько существует различных натуральных чисел N, при обработке которых получится R = 6? 265) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1) Если исходное число кратно 3, оно делится на 3, иначе из него вычитается 1. 2) Если полученное на предыдущем шаге число кратно 7, оно делится на 7, иначе из него вычитается 1. 3) Если полученное на предыдущем шаге число кратно 11, оно делится на 11, иначе из него вычитается 1. 4) Число, полученное на шаге 3, считается результатом работы алгоритма. Сколько существует различных натуральных чисел N, при обработке которых получится R = 6? 266) Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1) Если исходное число кратно 3, оно делится на 3, иначе из него вычитается 1. 2) Если полученное на предыдущем шаге число кратно 5, оно делится на 5, иначе из него вычитается 1. 3) Если полученное на предыдущем шаге число кратно 11, оно делится на 11, иначе из него вычитается 1. 4) Число, полученное на шаге 3, считается результатом работы алгоритма. Сколько существует различных натуральных чисел N, при обработке которых получится R = 8? 267) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1) Число N переводим в двоичную запись. 2) Инвертируем все биты числа кроме первого. 3) Переводим в десятичную запись. 4) Складываем результат с исходным числом N. Полученное число является искомым числом R. Укажите наименьшее нечетное число N, для которого результат работы данного алгоритма больше 99. В ответе это число запишите в десятичной системе счисления. 268) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи справа дописывается один разряд по следующему правилу: если количество единиц в двоичной записи числа больше количества нулей, то справа дописывается единица, иначе дописывается 0. 3. К полученной записи повторно применяется алгоритм п. 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите наибольшее число R, меньшее 57, которое может быть получено в результате работы данного алгоритма. В ответе это число запишите в десятичной системе счисления. 269) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "1", а справа - "11". В противном случае слева приписывается "11", а справа "00". Например, N = 5 10 = 101 2 => 110111 2 = 55 10 = R Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите наибольшее число R, меньшее 127, которое может быть получено с помощью описанного алгоритма. В ответ запишите это число в десятичной системе счисления. 39 270) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "10", а справа - "11". В противном случае слева приписывается "1", а справа "00". Например, N = 5 10 = 101 2 => 1010111 2 = 87 10 = R Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите наименьшее число R, большее 1023, которое может быть получено с помощью описанного алгоритма. В ответ запишите это число в десятичной системе счисления. 271) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится четверичная запись числа N. 2. К этой записи дописывается ещё три или четыре разряда по следующему правилу: если N нечётное, то слева к нему приписывается "2", а справа - "11". В противном случае слева приписывается "13", а справа "02". Например, N = 45 10 = 231 4 => 223111 4 = 2773 10 = R Полученная таким образом запись (в ней на три или четыре разряда больше, чем в записи исходного числа N) является четверичной записью искомого числа R. Укажите наименьшее число R, большее 1000, которое может быть получено с помощью описанного алгоритма. В ответ запишите это число в десятичной системе счисления. 272) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится шестнадцатеричная запись числа N // 2, где "//" - операция деления нацело. 2. К этой записи дописывается ещё три разряда по следующему правилу: если N не делится на 4, то слева к нему приписывается "F", а справа - "A0". В противном случае слева приписывается "15", а справа "C". Например, N = 4 10 => 2 16 => 152C 16 = 5420 10 = R. Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является шестнадцатеричной записью искомого числа R. Укажите наибольшее число N, для которого результат работы алгоритма меньше 65536. В ответ запишите это число в десятичной системе счисления. 273) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. Если N нечетное, то в конец полученной записи (справа) дописывается 0, в начало 1; если N четное в конец и начало дописывается по две единицы. 3. Результат переводится в десятичную систему и выводится на экран. Пример: Дано число N = 14. Алгоритм работает следующим образом. Двоичная запись числа N: 1110. Число четное, следовательно, добавляем по две единицы по краям – 11111011. На экран выводится число 251. Укажите наибольшее число, меньшее 126, которое может являться результатом работы автомата |