Разбор демоверсии ЕГЭ по информатике 2022 (1-5 Задание)
Привет! Сегодня порешаем демонстрационный вариант ЕГЭ по информатике 2022.
В этой статье представлены задания с 1-ого по 5.
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Б в пункт В и из пункта Г в пункт Д. В ответе запишите целое число.
В начале нужно понять, какой город под какой буквой находится в таблице.
Точка К — особая точка, т.е. она отличается от остальных, т.к. только она имеет 6 дорог. Поэтому её легко найти в таблице, она под номером 5.
Рисунок имеет симметричную структуру. Поэтому например точки A и E мы не сможем отличить друг от друга. Но найдём примерное их расположение.
Города A и E имеют по две дороги. Значит, им соответствуют номера 1 и 3.
Городам Б и Д соответствуют номера 2 и 4. Т.к. эти номера по таблице связаны с 1 и 3. Опять, какому номеру соответствует конкретная буква, мы не сможем узнать.
С номерами 2 и 4, должны быть связаны уже В и Г. Значит, городам В и Г соответствуют номера 6 и 7.
Получается, чтобы ответить на вопрос задачи, нужно суммировать расстояния между 2 и 6 И 4 и 7.
13+7=20
Ответ: 20
Миша заполнял таблицу истинности логической функции F
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция F задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.
В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.
Напишем шаблон для решения 2 задания на языке программирования Python.
Здесь мы перебираем все варианты с помощью вложенных циклов. И если наша функция превращается в истину, то печатаем значения переменных.
Отрицание меняется на not, следование представляем по формуле A->B = ¬A or B.
x y z w
0 1 0 1
1 1 0 0
1 1 1 0
Видно, что третий столбец — это y.
Т.к. у нас нет столбца, который состоит только из одних нулей, то в четвёртом столбце в пустой ячейке будет 1.
Получилась строчка из трёх 1. Значит, в первом столбце в пустой ячейке вверху будет 0. Следовательно, первый столбец — w.
Последний столбец достаётся z, т.к. из оставшихся переменных только у неё два 0 и одна 1. Второй столбец, по принципу исключения, — это x.
Ответ: wxyz
В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.
Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады июня 2021 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок, шт. занесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.
| ID операции |
Дата | ID магазина |
Артикул | Тип операции |
Количество упаковок, шт. |
Цена, руб./шт. |
Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Заголовок таблицы имеет следующий вид.
| Артикул | Отдел | Наименование | Ед. изм. |
Количество в упаковке |
Поставщик |
Таблица «Магазин» содержит информацию о местонахождении магазинов. Заголовок таблицы имеет следующий вид.
| ID магазина |
Район | Адрес |
На рисунке приведена схема указанной базы данных.
Используя информацию из приведённой базы данных, определите на сколько увеличилось количество упаковок яиц диетических, имеющихся в наличии в магазинах Заречного района, за период с 1 по 10 июня включительно.
В ответе запишите только число.
Откроем файл Excel. Внизу у нас три вкладки (три таблицы).
Есть магазины, есть товары, есть операции, какие товары, куда перемещаются.
Прочитаем ещё раз внимательно вопрос задачи. Переходим на вкладку Магазин. Выделим столбец «Район» и отсортируем по данному столбцу таблицу (кнопка сортировки находится обычно в правом верхнем углу). Если появится вопрос об автоматическом расширении выделенного диапазона, отвечаем утвердительно.
Теперь удобно посмотреть ID магазинов Заречного Района. Всего получается 4 ID: M3, M9, M11, M14.
Переходим на вкладку Товар. Нас интересует яйцо диетическое. Ищем по поиску (Ctrl + F) и получаем Артикул данного товара. Это номер 15.
Данные мы собрали, теперь переходим на вкладку Движение товаров.
Сначала подсчитаем сколько поступило указанного товара в указанные торговые точки за период 1-10 июня. Убедимся, что первая строчка не подходит нам по условию и в ячейке H2 ставим значение 0. Это число олицетворяет количество поступивших товаров.
В ячейке H3 пропишем формулу:
=ЕСЛИ(И(ИЛИ(C3= «M3» ;C3= «M9» ;C3= «M11» ; C3= «M14» ); D3=15; F3= «Поступление» );H2+E3;H2)
Эту формулу мы распространяем на весь столбец H. Тогда она будет анализировать каждую строчку и подсчитывать количество поступившего товара, учитывая все обстоятельства задачи. В самой последней ячейке столбца H получается число 1420. Это и есть то количество нашего товара, которое поступило в указанные торговые точки. Про дату в этой задаче думать не нужно, т.к. вся таблица по операциям происходит в пределах 1-10 июня.
Аналогично, подсчитаем в столбце I, какое количество убыло. Тогда формула получается:
=ЕСЛИ(И(ИЛИ(C3= «M3» ;C3= «M9» ;C3= «M11» ; C3= «M14» ); D3=15; F3= «Продажа» );I2+E3;I2)
Получаем количество проданных товаров 454.
Подсчитаем на сколько же увеличилось товаров:
Это и будет ответ.
В подобных задачах удобно воспользоваться фильтрами!
Выбираем вкладку Магазин и нажимаем кнопку Фильтр.
При этом должна быть выделена не пустая ячейка.
Кнопка Фильтр может находится и на главной панеле.
Теперь можно отфильтровать магазины Заречного района.
Нажмём «ОК», и у нас останутся только магазины Заречного района. Фиксируем их ID.
Переходим на вкладку Товар. Включаем фильтры. С помощью фильтров оставляем только яйцо диетическое и узнаём его Артикл.
Переходим на главную вкладку Движение товаров. Включаем фильтры. Фильтруем операции, которые подходят для наших магазинов и для нашего товара.
В начале найдём количество упаковок, которые поступили в магазины, поэтому в столбце Тип операции выбираем » Поступление«.
Выделяем ячейки столбца Количество упаковок для получившихся операций, и внизу смотрим сумму этих ячеек.
Здесь нельзя пользоваться стандартной функцией СУММ, потому что она суммируем ещё и скрытые ячейки. А так мы получаем сумму выделенных ячеек.
Получается количество поступивших упаковок равно 1420. Аналогично количество убывших получается 454.
1420-454=966
Ответ: 966
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв П и Р кодовые слова неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Т.к. никакое кодовое слово не является началом другого кодового слова, то, значит, выполняется условие Фано.
Следовательно, можно воспользоваться приёмом дерево Фано.
Разместим буквы для которых известны коды на дереве Фано.
При построении дерева Фано мы проращивает от корня две ветки 0 и 1. От каждой ветки тоже можно прорастить две ветки 0 и 1 и т.д. Если буква «села» на ветку, то она блокирует эту ветку, и больше нельзя проращивать новые ответвления от неё.
У нас остались две буквы П и Р, а прорастить можем только одну ветку (из 1 — прорастить 0). Мы проращиваем эту ветку и от неё проращиваем два ответвления, и теперь мы уже можем разместить оставшиеся буквы на дереве.
Для П выбираем код с меньшим числовым значением — 100, как написано в условии. Букве Р достаётся код — 101.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью результирующего числа R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
На вход поступает натуральное (обычное, не дробное, положительное) число N.
Это число алгоритм переводит в двоичную систему.
Сказано, что дописываются два разряда справа к тому двоичному числу, которое получили в первом пункте.
Про первый дополнительный разряд написано в пункте a второго правила: «складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001».
Если сказать более просто, то автомат подсчитывает количество единиц у первоначального двоичного числа N, полученного в первом пункте. Если количество чётное, то автомат в первый дополнительный разряд должен поставить 0. Если количество нечётное, то автомат в первый дополнительный разряд должен поставить 1.
Про второй дополнительный разряд сказано в пункте б второго правила. Автомат сделает тоже самое, что и в предыдущем пункте, только теперь подсчёт единиц будет происходить не только в двоичной записи числа N, но и в первом дополнительном разряде.
В вопросе просят указать входящее наименьшее число N, чтобы автомат выдал число R больше 77.
Т.к. число R должно быть больше 77, то переведём число 78 (77 + 1) в двоичный вид, чтобы можно было оценить входящее число N.
Это можно сделать стандартным калькулятором windows, переключив его в режим «Программиста» (Вид->»Программист»).
Получилось число 1001110. Будем рассматривать (начиная с 1001110) числа на выполнение правил, которые заданы для алгоритма. Если все правила будут выполнены, значит, мы получили то число, по которому вычислим изначальное N. Нам нужно получить именно минимальное число, поэтому мы и начали с минимального возможного претендента для числа R (78).
Здесь нам сразу повезло, сразу число 78 удовлетворяет всем условиям. Нас просили написать именно число N, поэтому от числа 1001110 отбрасываем два разряда и переводим в десятичную систему.
Примеры решения заданий 5 ЕГЭ по информатике на языке PYTHON
материал для подготовки к егэ (гиа) по информатике и икт (11 класс)
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2
дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше,
чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77.
В ответе это число запишите в десятичной системе счисления.
for n in range(21):
for i in range(2):
if sum(list(int(x) for x in s))%2==0:
№ 350 На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются разряды по следующему правилу:
а) если единиц больше, чем нулей, в конец дописывается 0,
б) иначе в начало строки дописывается две 1.
3) Повторяется пункт 2
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите минимальное число N, при вводе которого получится значение R больше, чем 500.
В ответе полученное число запишите в десятичной системе.
for n in range(150):
for i in range(2):
Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. В полученной записи все нули заменяются на единицы, все единицы – на нули. Из полученного числа удаляются ведущие нули.
3. Результат переводится в десятичную систему счисления.
4. Результатом работы алгоритма становится разность исходного числа N и числа, полученного на предыдущем шаге.
Укажите такое наименьшее число n для которого результат работы алгоритма больше 77
Укажите такое наименьшее число n для которого результат работы алгоритма больше 77
Тип 5 № 10468 
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью результирующего числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Если изначально сумма разрядов была чётная, то в конец запишется 00, что эквивалентно .
Если же сумма была нечётная, то запишется 10, что эквивалентно .
В обоих случаях число получается чётным.
Посмотрим на чётные числа, превосходящие 77.
— на конце 10, а сумма остальных разрядов нечётна. Число подходит под второй случай, значит, число, из которого оно было получено, равно .
ЕГЭ – 2021, задание 5, часть 3. Элементы теории алгоритмов: бит четности и др. Практика
При решении заданий 5 ЕГЭ-2021, часть 2 рассматриваются несколько типов задач на алгоритмизацию. При этом нужно учесть,, что алгоритм — это четкий порядок действий, подлежащих выполнению, то есть при решении задач на алгоритмизацию следует внимательно читать условие задачи и точно, аккуратно и без спешки (в этом залог быстрого и точного решения задачи!) выполнять описанные в нем действия.
При этом обратим внимание, что одни и те же действия в разных задачах могут описываться разными условиями, например:
— "складываются все цифры двоичной записи числа" или "считается количество единиц в двоичной записи числа": поскольку сумма цифр двоичной записи числа равна количеству единиц в двоичном числе, то при решении задач быстрее и проще посчитать количество единиц в записи и получить результат для данного условия;
— "остаток от деления суммы (количества единиц) на два", "бит чётности", "четное число или нет" — в результате проверки всех этих условий проверяется остаток от деления числа на 2: по умолчанию это ноль для четного числа и единица — для нечетного. Но в условии задач этот результат может меняться, поэтому следует точно выполнять действия, заданные в алгоритме!
Следует также внимательно смотреть, какое из чисел – N или R – следует искать в данной задаче.
Пример 1 (ДЕМО – 2021)
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Строится двоичная запись числа N.
К этой записи дописываются справа ещё два разряда по следующему правилу:
складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 77) — число 78:
78 = 2 6 + 2 3 + 2 2 + 2 1 = 10011102
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма
N = 100112 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
1 – верно, так как количество единиц в числе N равно трем;
0 – верно, так как теперь в полученном результате уже 4 единицы.
Так как условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 100112 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 100112 = 2 0 + 2 1 + 0 2 + 0 3 + 2 4 = 1 + 2 + 16 = 19.
Примечание: для быстрого и точного перевода числа из двоичной системы в десятичную я записываю степени с конца, чтобы не делать лишних действий и не допускать возможных ошибок.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Строится двоичная запись числа N.
К этой записи дописываются справа ещё два разряда по следующему правилу:
в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно;
к этой записи справа дописывается остаток от деления количества единиц на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает 31 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 31) — число 32:
32 = 2 5 = 1000002
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 10002 и цифры 00, которые получены в результате двух следующих шагов выполнения алгоритма:
0 – верно, так как количество единиц в числе N нечетно;
0 – неверно, так как остаток от деления количества единиц на 2 равен 1.
Так как условия выполнения алгоритма НЕ совпадают с полученным результатом, то берем следующее возможное число искомое число R = 33 и проверяем его.
1. Переведем число 33 в двоичную систему счисления: 33 = 2 5 = 1000012
2. Для проверки, может ли данное число R быть результатом работы алгоритма,
отделяем от него справа две последние цифры (которые являются результатом
выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 10002
и цифры 01, которые получены в результате двух следующих шагов выполнения
0 – верно, так как количество единиц в числе N нечетно;
1 – верно, так как результат от деления количества единиц на 2 равен 1.
Так как условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 110002 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 1100112 = 2 0 + 2 1 + 0 2 + 0 3 + 2 4 = 1 + 2 + 16 = 19.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
Строится двоичная запись числа N.
К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.
К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 96. В ответе это число запишите в десятичной системе.
Решение 1 – короткое:
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 96) — число 97:
97 = 2 6 + 2 5 + 2 0 = 11000012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и получаем, что для числа N = 110002 последними цифрами должны быть 00, но тогда число R = 11000002 = 96 не удовлетворяет условию задачи.
Числа с двумя последними цифрами 01 (97 = 11000012), 10 (98 = 11000102) и 11 (99=11000112) также не подходят. Это значит, что нужно увеличивать само число N, тогда получаем N = 110012 и в результате работы алгоритма получим R = 11001102 = 102.
Тогда искомое число N = 110012 = 25
Решение 2 – длинное (обычное):
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону:
Переведем в двоичную систему первое число, удовлетворяющее условию задачи (наименьшее число R, которое больше числа 96) — число 97:
97 = 2 6 + 2 5 + 2 0 = 11000012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:
0 – верно, так как количество единиц в числе N четно;
1 –неверно, так как количество единиц в числе N четно.
Так как условия выполнения алгоритма НЕ совпадают с полученным результатом, то берем следующее возможное число R = 98 и проверяем его.
Переведем в двоичную систему число 98:
98 = 2 6 + 2 5 + 2 1 = 11000102
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
1 – неверно, так как количество единиц в числе N четно;
0 – неверно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 99 и проверяем его.
Переведем в двоичную систему число 99:
= 2 6 + 2 5 + 2 1 + 2 0 = 11000112
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110002 и цифры 11, которые получены в результате двух следующих шагов выполнения алгоритма:
1 – неверно, так как количество единиц в числе N четно
1–верно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 100 и проверяем его.
Переведем в двоичную систему число100:
= 2 6 + 2 5 + 2 2 = 11001002
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 00, которые получены в результате двух следующих шагов выполнения алгоритма:
0 – неверно, так как количество единиц в числе N нечетно
0 – неверно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 101 и проверяем его.
Переведем в двоичную систему число 101:
= 2 6 + 2 5 + 2 2 + 2 0 = 11001012
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 01, которые получены в результате двух следующих шагов выполнения алгоритма:
0 – неверно, так как количество единиц в числе N нечетно
1 – верно, так как количество единиц в числе N нечетно.
Так как условия выполнения алгоритма опять НЕ совпадают с полученным результатом, то берем следующее возможное число R = 102 и проверяем его.
Переведем в двоичную систему число 102:
= 2 6 + 2 5 + 2 2 + 2 1 = 11001102
Для проверки, может ли данное число R быть результатом работы алгоритма, отделяем от него справа две последние цифры (которые являются результатом выполнения алгоритма) и проверяем исходное число до работы алгоритма N = 110012 и цифры 10, которые получены в результате двух следующих шагов выполнения алгоритма:
1 – верно, так как количество единиц в числе N нечетно
0 – верно, так как количество единиц в числе N четно.
Так как оба условия выполнения алгоритма совпадают с полученным результатом, то искомое число N = 100112 и будет искомым. Переводим его в десятичную систему счисления и получаем ответ:
N = 110012 = 2 0 + 0 1 + 0 2 + 2 3 + 2 4 = 1 + 8 + 16 = 25.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Складываются все цифры двоичной записи числа. Если сумма четная, то в конец числа (справа) дописывается 1, а если нечетная, то дописывается 0. Например, запись числа 10 преобразуется в запись 100;
3) К полученному результату применяется еще раз пункт 2 этого алгоритма.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите количество чисел R, которые могут быть получены в результате работы этого алгоритма, и лежат в диапазоне 16 ≤ R ≤ 32.
Так как в задании указан результат работы алгоритма, то выполняем действия строго по алгоритму, но в обратную сторону.
Переведем в двоичную систему первое число, удовлетворяющее условию задачи границы диапазона возможных чисел R:
Rmin = 2 4 = 100002
Rmax = 2 5 = 1000002
Соответственно получаем Nmin = 2 2 = 1002 и Nmax = 2 3 = 10002.
Далее берем все возможные числа N внутри данного диапазона (возможны только три варианта – 101, 110 и 111) и проверяем результат работы алгоритма над ними:
при N = 1012 возможно только одно R = 101102 = 22
при N = 1102 возможно только одно R = 110102 = 26
при N = 1112 возможно только одно R = 111002 = 28
Тогда всего получаем 5 подходящих чисел.
Автомат обрабатывает натуральное число N
1) Строится восьмибитная двоичная запись числа N–1.
2) Инвертируются разряды исходного числа (0 заменяется на 1, 1 на 0).
3) Полученное число переводится в десятичную систему счисления.
Для какого числа N результат работы алгоритма равен 113?
Переводим число 113 в двоичную систему счисления и получаем
N — 1 = 2 6 + 2 5 + 2 4 + 2 0 = 11100012
Дополняем его до восьми бит и инвертируем:
N — 1 = 011100012 = 100011102 = 2 1 + 2 2 + 2 3 + 2 7 = 142, тогда N = 142 + 1= 143.
Укажите такое наименьшее число n для которого результат работы алгоритма больше 77
Задание 1. Анализ информационных моделей
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе запишите целое число – так, как оно указано в таблице.
Анализируя таблицу, мы видим, что только между населенными пунктами 3 и 6, есть одна дорога 36, протяженностью 12 км, причем из пункта 6, кроме данной дороги, выходят еще три, это дороги 62,64 и 65. Рассуждая таким образом, получим граф:
Таким образом, протяженность дороги ГЖ (14) равна 9 км.
Ответ: 9
Задание 2. Построение таблиц истинности логических выражений
Миша заполнял таблицу истинности функции (x v y) & ¬(y≡z) & ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Ответ: ZYXW
Пример. Функция задана выражением ¬x v y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид. В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.
Задание 3. Базы данных. Файловая система
Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID женщины, ставшей матерью в наиболее молодом возрасте. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.
В таблице 2 удобно добавить колонку и посчитать возраст мамы, возраст пап считать не будем (ID родителя мужского пола).
| Таблица 2 | ||
| ID Родителя | ID_Ребёнка | Возраст мамы |
| 24 | 25 | — |
| 44 | 25 | 36 |
| 25 | 26 | — |
| 64 | 26 | 38 |
| 24 | 34 | — |
| 44 | 34 | 26 |
| 34 | 35 | 26 |
| 36 | 35 | — |
| 14 | 36 | 27 |
| 34 | 46 | 29 |
| 36 | 46 | — |
| 25 | 54 | — |
| 64 | 54 | 22 |
| … | … | … |
Таким образом, по таблице мы видим, что самой молодой маме было 22 года, это ID родителя 64
Ответ: 64
Задание 4. Кодирование и декодирование информации
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв – П и Р – кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Поскольку никакое кодовое слово не является началом другого кодового слова, код 10 использовать нельзя, значит получим два слова 100 и 101, из которых наименьшее 100 и будет ответом на вопрос задачи.
Ответ: 100
Задание 5. Анализ и построение алгоритмов для исполнителей
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем
в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
| 78 39 19 9 4 2 | 0 1 1 1 0 0 | 78 10 = 10011 10 2 ✓ 7910 = 10011 11 2 ✗ 8 010 = 10100 00 2 ✓ 8 110 = 10100 01 2 ✗ 8210 = 10100 10 2 ✗ |
| 1 |
Мы видим, что подходят по алгоритму числа 78 и 80, из которых 78 наименьшее. Чтобы найти искомое число N, отбросим два дополнительных разряда от найденного 1001110.
Правило: Если от двоичного числа отбросить младший разряд, то оно разделится на 2 целочисленным образом (т.е. делим на 2, если есть остаток, убираем его).
Уберём второй дополнительный разряд у числа 1001110, получается 78 / 2 = 39 (100111). Уберём ещё и первый дополнительный разряд , получается 39 / 2 = 19 (10011), следовательно двоичное представление искомого числа N равно 10011, а десятичное 19.
Ответ: 19
Задание 6. Анализ программ
Определите, при каком наибольшем введённом значении переменной s программа выведет число 64.
s = int(input())
s = s // 10
n = 1
while s < 51:
s = s + 5
n = n * 2
print(n)
Переменная n менялась в цикле от 1 до 64, на каждом шаге, увеличивалась в 2 раза. Построим трассировочную таблицу в обратном порядке.
| Трассировочная таблица | |
| n | s |
| 64 | 46-50 |
| 32 | 41-45 |
| 16 | 36-40 |
| 8 | 31-35 |
| 4 | 26-30 |
| 2 | 19-25 |
| 1 | 250-259 |
| 259 | |
Наибольшее значение s на первом шаге равно 259.
Ответ: 259
Задание 7. Кодирование и декодирование информации. Передача информации
Для хранения произвольного растрового изображения размером 128×320 пикселей отведено 20 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении?
N = 2 i , I = K · i , i = I/K
I = 20 · 2 13 бит
К = 2 7 · 2 5 · 10 = 5 · 2 13
i = (20 · 2 13 )/ ( 5 · 2 13 ) = 4 бита
N = 2 4 = 16 символов
Ответ: 16
Задание 8. Перебор слов и системы счисления
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?
Получим, 1 · 4 · 4 + 4 · 1 · 4 + 4 · 4 · 1 = 16 + 16 + 16 = 48
Ответ: 48
Задание 9. Работа с таблицами
Откройте файл электронной таблицы, содержащей вещественные числа — результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. Найдите разность между максимальным значением температуры и её средним арифметическим значением. В ответе запишите только целую часть получившегося числа.Файл с данными
При помощи формул найдем нужные значения:
И их разность, которую округляем до целого
=ЦЕЛОЕ(B94-B95)
Ответ: 14
Задание 10. Поиск символов в текстовом редакторе
С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «долг» или «Долг» в тексте романа в стихах А. С. Пушкина «Евгений Онегин». Другие формы слова «долг», такие как «долги», «долгами» и т. д., учитывать не следует. В ответе укажите только число.
В текстовом редакторе используем инструмент найти (по умолчанию он не учитывает регистр, в расширенном поиске есть кнопка больше, где можно проверить настройки). Ищем слово целиком. Оно встречается один раз во фразе «Цензуре долг свой заплачу».
Ответ: 1
Задание 11. Вычисление количества информации
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 24 байт на одного пользователя.
Определите объём памяти (в байтах), необходимый для хранения сведений о 20 пользователях. В ответе запишите только целое число — количество байт.
N : – всего 8 различных символов в наборе
N = 2 i , 8=2 3 , значит для кодирования одного символа нужно 3 бита
I = K · i I = 15 · 3 = 45 бит ≈ 6 байт – отводится на пароль
I = 6 + 24 = 30 байт – на одного пользователя (с доп. информацией)
I 20 = 20 · 30 = 600 байт – всего
Ответ: 600
Задание 12. Выполнение алгоритмов для исполнителей
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
ЕСЛИ условие
ТО команда 1
КОНЕЦ ЕСЛИ
выполняется команда 1 (если условие истинно).
ЕСЛИ условие
ТО команда 1
ИНАЧЕ команда 2
КОНЕЦ ЕСЛИ
выполняется команда 1 (если условие истинно) или команда 2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
35 раз каждые четыре символа будут заменены на два. Останется 22
Ответ: 22
Задание 13. Поиск путей в графе
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.Сколько существует различных путей из города А в город М, проходящих через город В?
Ответ: 24
Задание 14. Кодирование чисел. Системы счисления
Значение выражения 49 7 + 7 21 − 7? записали в системе счисления с основанием 7.
Сколько цифр «6» содержится в этой записи?
49 7 + 7 21 − 7 = 7 14 + 7 21 − 7=100000000000000 + 1000000000000000000000 — 1=
1000000100000000000000 — 1 = 100000006666666666666
В семеричной системе счисления 7 21 это число, состоящее из 1 и 21 нуля.
7 14 это число, состоящее из 1 и 14 нулей. При вычитании занимаем 1, и в предыдущих 13 разрядах останутся шестерки.
Ответ: 13
Задание 15. Преобразование логических выражений
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Ответ: 18
Задание 16. Рекурсивные алгоритмы
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n + F(n − 1), если n — чётно;
F(n) = 2 × F(n − 2), если n> 1 и при этом n — нечётно.
Чему равно значение функции F(26)?
F(1) = 1
| n | F(n) = 2 × F(n − 2), если n — нечётно |
F(n) = n + F(n − 1), если n — чётно |
| 2 | 2 | |
| 3 | 2 | |
| 4 | 4 | |
| 5 | 4 | |
| 6 | 6 | |
| 7 | 8 | |
| 8 | 14 | |
| 9 | 16 | |
| 10 | 30 | |
| 11 | 32 | |
| . | 62 |
Мы видим, что значения функции от нечетных n представляют из себя степени двойки.
F( 26 ) = 26 + F( 25 ) = 26 + 2 1 2 = 26 + 4096 = 4122
Ответ: 4122
Задание 17. Проверка на делимость
Рассматривается множество целых чисел, принадлежащих числовому отрезку [1016; 7937], которые делятся на 3 и не делятся на 7, 17, 19, 27.
Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа без пробелов и других дополнительных символов: сначала количество, затем максимальное число.
Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.
Ответ: 1568 7935
Задание 18. Робот-сборщик монет
Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.Пример входных данных:
| 1 | 8 | 8 | 4 |
| 10 | 1 | 1 | 3 |
| 1 | 3 | 12 | 2 |
| 2 | 3 | 5 | 6 |
Для указанных входных данных ответом должна быть пара чисел 41 и 22.
Найдём максимальную денежную сумму. Для этого найдём максимальную денежную сумму для каждой ячейки таблицы. В ячейку L1 запишем формулу =СУММ($A$1:A1) . Скопируем эту формулу во все ячейки в диапазоне M1:U1 и в диапазоне L2:L10. Для остальных ячеек будем сравнивать значение ячейки слева и значение ячейки сверху и присваивать текущей ячейке значение суммы той ячейки, в которой значение больше, и текущей ячейки. В M2 запишем формулу =ЕСЛИ(L2>M1;L2+B2;M1+B2) и скопируем эту формулу во все ячейки диапазона M2:U10 . Таким образом, в ячейке U10 получим значение максимальной денежной суммы — 1204.
Аналогичным образом найдём значение минимальной денежной суммы. Ячейки диапазонов L1:L10 и M1:U1 заполняются также, как при поиске максимальной денежной суммы. В M2 запишем формулу =ЕСЛИ(L2 < M1;L2+B2;M1+B2) и скопируем эту формулу во все ячейки диапазона M2:U10. Таким образом, в ячейке U10 получим значение минимальной денежной суммы — 502.
Ответ: 1204 502
Задание 19. Выигрышная стратегия. Задание 1
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Ваня выиграл первым ходом после неудачного хода Пети. Победителем считается игрок, сделавший последний ход, при которой в кучах будет 77 или больше камней. Нужно найти минимальное S , при котором возможна победа Вани.
Чтобы S было минимальным, Петя и Ваня удваивали S , значит, (77-7) /4 » 18 . Округляем до целого.
Ответ: 18
Задание 20. Выигрышная стратегия. Задание 2
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Значения S 35 и 36 не подходят, поскольку в этом случае Петя может выиграть своим первым ходом. Рассмотрим значение S = 34.
Рассматривая аналогично числа 33 и 32, из дерева мы видим, что комбинации (9, 33) и (9, 32) приведут к победе Вани.
Рассмотрим число 31. Если Петя выбирает комбинацию первого хода (14, 31), то видим на дереве, что она приводит к выигрышу Пети вторым ходом.
Ответ: 3134
Задание 21. Выигрышная стратегия. Задание 3
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Рассмотрим S=30. Из дерева видим, что данное число камней во второй куче приводит к выигрышу Вани первым или вторым ходом при любой игре Пети.
Ответ: 30
Задание 22. Анализ программы с циклами и условными операторами
Дан алгоритм. (код на языке Python). Получив на вход число x, этот алгоритм печатает два числа: L и M . Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 4, а потом 5.
x = int(input())
Q = 9
L = 0
while x >= Q:
L = L + 1
x = x — Q
M = x
if M < L:
M = L
L = x
print(L)
print(M)
Данный алгоритм ищет два числа: целую часть от деления x на 9 и остаток от деления x на 9. Если остаток от деления числа x на 9 меньше, чем целая часть, то алгоритм меняет местами значения L и M.
В результате работы алгоритма на экран будут выведены два числа: 4 и 5. Значит, чтобы найти наибольшее число x, число 5 должно являться целой частью от деления x на 9, а число 4 — остатком от деления x на 9. То есть, x = 9 · 5 + 4 = 49.
Ответ: 49
Задание 23. Анализ программы с циклами и условными операторами
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 20 и при этом траектория вычислений содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Данное дерево вариантов показывает программы получения 10 из 1. Всего мы видим 14 различных вариантов. Чтобы получить из числа 10 число 20, есть два варианта, последовательно прибавлять 1 или умножить на 2.
То есть 14 * 2 = 28
Ответ: 28
Задание 24. Анализ программы с циклами и условными операторами
Текстовый файл состоит не более чем из 10 6 символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.
Для выполнения этого задания следует написать программу.
for i in range(2,len(s)):
if s[i]!=s[i-1]:
k+=1
m=max(k,m)
else:
k=1
Ответ: 35
Задание 25. Анализ программы с циклами и условными операторами
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в два соседних столбца на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке также должны следовать в порядке возрастания.
Например, в диапазоне [5; 9] ровно два различных натуральных делителя имеют числа 6 и 8, поэтому для этого диапазона вывод на экране должна содержать следующие значения:
for i in range(174457, 174506):
D=[]
for j in range (2,i//2+1):
if i%j==0:
D.append(j)
if len(D)==2:
print(D)
Ответ:
[3, 58153]
[7, 24923]
[59, 2957]
[13, 13421]
[149, 1171]
[5, 34897]
[211, 827]
[2, 87251]
Задание 26. Анализ программы с циклами и условными операторами
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
with open(«26.txt», «r») as f:
st=f.readline().split()
print(st)
S=int(st[0]) # размер свободного места на диске
N=int(st[1]) # количество пользователей
I=0 # объем файлов пользователей
P=[] # массив файлов пользователей
for j in range(1,N+1):
i=int(f.readline())
P.append(i) #заполняем массив
P.sort() #сортируем по возрастанию
k=0 #количество файлов, которые смогут поместиться на диске
for j in P:
if I+j>S: break
I+=j
k+=1
m=0 # максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей
for x in P:
if x>j and x<=(S-I) + j: #ищем такой файл, добавляя оставшееся место на диске
print(x)
m=x
m=max(m,x)
Ответ: 568 50
Задание 27. Анализ программы с циклами и условными операторами
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
Для указанных входных данных значением искомой суммы должно быть число 32.В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
with open(«27-A.txt», «r») as f:
st=f.readlines() # создаем массив из строк файла
k=int(st[0]) # записываем количество строк в переменную k
s=0 # создаем переменную для суммы
min_r=1000 # определяем минимальную разницу в одной строке
del(st[0]) # удаляем первую строку
for i in range(k):
a, b =map(int, st[i].split()) #разделяем строку на две переменные
s+= max(a,b) # накапливаем сумму из максимальных значений
m=abs(a-b) #находим разницу между значениями одной строки
if m%3 !=0:
min_r=min(m,min_r) #мин. разница, которая не делится на 3
Информатика 11 класс
1. (демо-2021). На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления
2. (Демо-2023) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;
б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 6 = 1102 результатом является число 10002 = 8, а для исходного числа 4 = 1002 результатом является число 11012 = 13.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 40. В ответе запишите это число в десятичной системе счисления.
3. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число чётное, то к двоичной записи числа слева дописывается 10;
б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для исходного числа 410 = 1002 результатом будет являться число 2010 = 101002, а для исходного числа 510 = 1012 результатом будет являться число 5310 = 1101012.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее, чем 441. В ответе запишите это число в десятичной системе счисления.
4. На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Каждый разряд этой записи заменяется двумя разрядами по следующему правилу: если в разряде стоит 0, то вместо него пишется 00; если в разряде стоит 1, то 1 заменяется на 11.
Например, двоичная запись 1001 числа 9 будет преобразована в 11000011.
Полученная таким образом запись является двоичной записью числа R — результата работы данного алгоритма. Укажите минимальное число R, большее 63, которое может являться результатом работы алгоритма. В ответ это число запишите в десятичной системе счисления.
Показать ответ
5. Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N без ведущих нулей.
2. Если в полученной записи единиц больше, чем нулей, то справа приписывается единица. Если нулей больше или нулей и единиц поровну, справа приписывается ноль.
3. Полученное число переводится в десятичную запись и выводится на экран.
Какое наибольшее число, меньшее, чем 100, может получиться в результате работы автомата?