Как решить задачу 11 экзамена по информатике 2020 и экзамена по информатике 2020. Как решить задачу 23!

Урок посвящён 11 заданию из ЕГЭ по информатике нового формата 2022. Проанализируем основные примеры и научимся решать это задание!

В 11 задании из ЕГЭ по информатике часто даются задачи на умение работать с количеством информации.

Приступим к делу! Раньше это задание было под номером тринадцать.

Задача (Демонстрационный вариант ЕГЭ по информатике, 2018)

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число – количество байт.

У каждого пользователя есть пароль, состоящий из 10 символов. Это значит, длина пароля 10 символов!

И в каждую ячейку мы может выбрать символ из 26 букв!

Здесь важно различать длину пароля и количество символов из которых пользователь выбирает для каждой ячейки пароля.

Теперь нужно определить: сколько бит занимает одна ячейка (1 символ пароля!).

Когда речь идёт о количестве бит, применяем формулу, которую мы использовали в 7 задании из ЕГЭ по информатике. Там мы кодировали цвета для одного пикселя, а здесь нужно закодировать 26 букв для одного поля пароля.

N = 2ⁱ = 26

Целого числа нету для i (количества бит), чтобы равенство было верным. Значит берём столько количество бит, сколько точно будет достаточно, чтобы закодировать 26 букв (символов).

N = 2⁵ > 26

Получаем одна ячейка (одно поле) пароля занимаем 5 бит! А в пароле их 10! Значит, весь пароль будет занимать:

V_пароля = 5 бит * 10 символов = 50 бит (в одном пароле!)

В условии сказано: для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. Это означает, что мы не может выделять память по одному биту. Память выделяется блоками по 8 бит (по одному байту).

Если взять 7 блоков по 8 бит (1 байту), то нам хватит этого на один пароль.

7 блоков (байт) * 8 бит = 56 бит > 50 бит

Таким образом, на 1 пароль потребуется 7 байт!

Тогда на 50 пользователей потребуется:

50 пользователей * 7 байт = 350 байт (для 50 пользователей).

Ответ: 350

Разберём задачу, которая была на реальном экзамене в Москве

Задача (ЕГЭ по информатике, 2020, Москва)

При регистрации в компьютерной системе каждому пользователю выдаётся
пароль, состоящий из 11 символов. В качестве символов используют 26
прописных букв из латинского алфавита и десять цифр. В базе
данных для хранения каждого пароля отведено одинаковое и минимально
возможное целое число байт. При этом используют посимвольное
кодирование паролей, все символы кодируют одинаковым
и минимально возможным количеством бит.
Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения.
Для кодирования данных о 30 сотрудниках было выделено 750 байт. Сколько памяти(в байтах) выделено для хранения дополнительных сведений об одном пользователе. В ответ запишите только целое число — количество байт.

Здесь длина пароля составляет 11 символов!

Найдём сколько бит занимает одна ячейка пароля.

N = 2ⁱ = 36

N = 2⁶ = 64 > 36

Значит, 6 бит — минимальное количество бит, которое нужно, чтобы была возможность разместить любой из 36 символов в одной ячейке пароля.

Найдём сколько бит нужно на весь пароль.

V_пароля = 6 бит * 11 символов = 66 бит (в одном пароле!)

Теперь найдём, а сколько байт нужно на 1 пароль:

9 * 8 бит = 72 бит > 66 бит

Следовательно, 9 байт достаточно, чтобы покрыть 66 бит на 1 пароль.

Сказано, что для 30 сотрудников выделено 750 байт. Подсчитаем, сколько байт будет выделено на одного сотрудника.

V_{пользователя} = 750 байт / 30 = 25 байт (приходится на одного пользователя)

Мы выяснили, что на пароль из этих 25 байт потребуется 9 байт. Тогда на дополнительную информацию о каждом пользователе потребуется:

V_{доп. о 1 пол.} = 25 байт — 9 байт = 16 байт

Это и будет ответ.

Ответ: 16

Ещё один важный пример из запасов тренировочных задач ЕГЭ по информатике.

Задача (Номера спортсменов)

В велокроссе участвуют 48 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда все спортсмены прошли промежуточный финиш? (Ответ дайте в байтах.)

Узнаем сколько бит потребуется выделить на каждого спортсмена, чтобы была возможность записать любой номер от 1 до 48.

В этой задаче сказано: записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена . Это означает что у нас есть 48 различных позиций (номеров), которые нужно закодировать с помощью определённого количества бит. В предыдущей задаче, у нас было 62 различные позиции (символа), которые нужно было закодировать с помощью определённого количества бит. Мы там использовали формулу N = 2ⁱ.

Поэтому будем опять применять формулу N = 2ⁱ.

На рисунке показано, как может происходить кодирование чисел. Например, для двух номеров потребуется 1 бит (2¹ = 2), для четырёх номеров потребуется два бита (2² = 4). Нам нужно закодировать 48 чисел! Причём для каждого участника отведено одинаковое количество бит!

Можно сказать, что здесь работает формула, которую рассматривали в 8 задании. Всего нужно составить 48 различных комбинаций (закодировать 48 номеров). В каждой ячейке можно писать либо 0, либо 1 (Свойство бита информации). Какова должна быть длина «слова» (количество бит) ?

N = 2ⁱ = 2^{6 бит} = 64 > 48

Получается 6 бит потребуется для того, чтобы была возможность записать любой номер от 1 до 48 для каждого спортсмена. Если взять пять бит, то мы будем иметь возможность записать номера только от 1 до 2⁵ = 32 для каждого спортсмена (этого не хватает).

Т.к. все участники пересекли финиш, а на каждого участника выделено по 6 бит, то получается:

6 бит * 48 = 288 бит = 36 байт

Ответ: 36

Задача (Автомобильный номер)

В некоторой стране автомобильный номер состоит из 7 символов: сначала 2 буквы, затем 3 цифры, затем ещё 2 буквы. При этом буквы могут быть выбраны только из 12 строчных букв местного алфавита. Среди цифр не используются цифры 6 и 9. Автоматизированная система хранит номера автомобилей следующим образом. Используется посимвольное кодирование. В памяти системы для кодирования каждого символа используется минимально возможное и одинаковое целое количество бит (для букв и цифр отдельно). А для номера используется минимально возможное целое количество байт. Какое количество информации (в байтах) требуется для хранения номеров 160 автомобилей ?

Найдём сколько бит потребуется для кодирования 4-х букв.

N = 2ⁱ = 2^{4 бита} = 16 > 12

4 бита хватит для кодирования 12 букв. Всего таких ячейки 4! Поэтому в одном номере на все буквы уйдёт 4 * 4 бита = 16 бит.

Найдём сколько бит потребуется на кодирование 3 ячеек, где находятся цифры.

N = 2ⁱ = 2^{3 бита} = 8

Для кодирования одной ячейки, где находится цифра, потребуется 3 бита.

Все цифры в одном номере будут закодированы 3 бита * 3 = 9 битами.

Всего на один номер уйдёт 16 бит + 9 бит = 25 бит.

Найдём сколько байт потребуется для кодирования одного номера.

4 * 8 бит (1 байт) = 32 бита > 25 бит

4-х байт достаточно, чтобы закодировать 25 бит. Если взять 3 байта, то 3 * 8 бит (1 байт) = 24 бита. Этого будет не достаточно.

Найдём количество байт, которое нужно для кодирования 160 автомобилей

160 автомобилей * 4 байта = 640 байт

Это и будет ответ.

Ответ: 640

Задача (Закрепление формулы)

Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного наблюдения является целое число от 0 до 100%, записываемое при помощи минимально возможного количества бит. Станция сделала 800 измерений. Определите информационный объем результатов наблюдений. (Ответ дайте в байтах.)

Здесь, нужно закодировать сто одно число (от 0 до 100). Ситуация похоже на ту, где мы кодировали номера спортсменов.

N = 2ⁱ = 2^{7 бит} = 128 > 101

Получается, что 7 бит потребуется, чтобы полностью закодировать 101 число.

Всего было сделано 800 таких измерений

800 * 7 бит = 5600 бит = 700 байт

Ответ: 700

На этом всё! Удачи при решении 11 задания на ЕГЭ по информатике!

Мужик, твой сайт — настоящая находка для меня. Все подробно расписано, разобрано большинство возможных вариаций каждого задания. Огромное спасибо, мужик

Продолжаем разбирать задачи из досрочного ЕГЭ по информатике 2023.

Ещё лучше подготовится к ЕГЭ по информатике, Вы можете по материалам сайта Code-Enjoy.

Досрочный ЕГЭ по информатике 2023 (Задания 1-10)
Досрочный ЕГЭ по информатике 2023 (Задания 22-27)

Файлы, ответы и формулировки могут не совпадать с реальным досрочным экзаменом, а данная статья лишь примерно показывает прототипы задач.

При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 35 символов и содержащий только символы
из 8-символьного набора. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит.

Определите объём памяти (в Кбайтах), необходимый для хранения сведений о 20 480 объектах. В ответе запишите только целое число – количество Кбайт.

Воспользуемся формулой для 11-ого задания из ЕГЭ по информатике.

Вместо N подставляем 8 символов, которые претендуют в одну ячейку. Тогда

8 = 2³

Т.е. 3 бита точно хватит, чтобы закодировать 8 символов.

В идентификаторе всего 35 ячеек. Найдём сколько будет «весить» один идентификатор: 3 * 35 = 105 бит. Узнаем, сколько байт потребуется для одного идентификатора 105 / 8 = 14 байт (округляем в большую сторону, чтобы точно хватило).

У нас всего 20480 идентификаторов. Тогда нам потребуется 20480 * 14 = 286720 байт. Переведём в Кб: 716800 / 1024 = 280 Кб.

Ответ: 280

Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

НАЧАЛО ПОКА нашлось (25) ИЛИ нашлось (333) ИЛИ нашлось (555) ЕСЛИ нашлось (25) ТО заменить (25, 3) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (355) ТО заменить (355, 52) КОНЕЦ ЕСЛИ ЕСЛИ нашлось (555) ТО заменить (555, 23) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «3», а затем содержащая n цифр «5» (n > 3).

Определите наименьшее значение n, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, равняется 18.

Напишем программу на языке Python.

 F(s): sm=0 x s: sm=sm+(x) sm n (4, 300): s = + n* s s s: s: s=s.replace(, , 1) s: s=s.replace(, , 1) s: s=s.replace(, , 1) F(s) == 18: (n)

Функция F() подсчитывает сумму цифр в строке.

Пробуем с помощью цикла for использовать разное количество пятёрок в первоначальной строке s. Если после выполнения программы для редактора, строка будет удовлетворять условию задачи, значит, печатаем то количество пятёрок (переменная n), при котором это произошло.

Более подробно, как решать задачи из 12 Задания, можете почитать в этой статье.

Наименьшее n равно 9.

Ответ: 9

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К, Л, М, Н, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Н?

Решим по известной технике для 13 задания из ЕГЭ по информатике, о которой Вы можете прочитать на страницах данного сайта.

Ответ: 63

Операнды арифметического выражения записаны в системе счисления с осно-ванием 15.

97968×21₁₅ + 7×23₁₅

В записи чисел переменной x обозначена неизвестная цифра из алфавита 15-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 14. Для найденного значения x вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.

Как решать такой «новый тип» задания 14 из ЕГЭ по информатике, читатели моего сайта отлично знают. Об этом мы говорили в этой статье.

 x (0, 15): a=1*15**0+2*15**1+x*15**2+8*15**3+6*15**4+9*15**5+7*15**6+9*15**7 b=3*15**0+2*15**1+x*15**2+7*15**3 (a+b)%14==0: ((a+b)//14)

Последнее выведенное число соответствует наибольшему значению x.

Ответ: 116047226

Для какого наименьшего целого неотрицательного A выражение

(x ≥ 9) ∨ (2x < y) ∨ (xy < A)

тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?

Из 4 шаблонов выбираем нужный!

 A (0, 300): k=0 x (0, 300): y (0, 300): (x >= 9) (2*x < y) (x*y < A): k=k+1 k==300*300: (A)

Наименьшее значение A будет равно 129.

Ответ: 129

Алгоритм вычисления значения функции F(n), где n – натуральное число, за-дан следующими соотношениями:

F(n) = n при n ≥ 2025;

F(n) = n + F(n + 2), если n < 2025.

Чему равно значение выражения F(2020) — F(2023)?

Здесь мы видим большие числа, которые передаются функции F(), поэтому будем решать с помощью инструмента lru_cache.

 functools lru_cache
@lru_cache() (n): n>=2025: n n<2025: n+F(n+2) i (2025, 0, -1): F(i)
(F(2020)-F(2023))

Функция возрастающая, поэтому мы запускаем функцию в цикле в начале с большими числами, а потом числа убывают.

В файле содержится последовательность натуральных чисел. Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар последовательности, в которых только одно число является двузначным, а сумма пары кратна минимальному двузначному числу во всём файле. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

В начале найдём минимальное двухзначное число во всём файле.

f=()
mn=10**10 s f.readlines(): x=(s) x>9 x<100: mn=(mn, x)
(mn)

Получается число 32.

Теперь найдём ответы на вопросы, связанные с парами чисел.

f=()
mx=0
k=0
n1=(f.readline()) s f.readlines(): n2=(s) ((10<=n1<=99) != (10<=n2<=99)) ((n1+n2)%32==0): k=k+1 mx = (mx, n1+n2) n1=n2
(k, mx)

Если первое число двухзначное, то второе не должно быть двухзначным или наоборот, если второе число двухзначное, то первое не должно быть двухзначным. Эта операция называется «исключающее ИЛИ». Мы логические операции разбирали в этой статье. Исключающее ИЛИ может быть представлено, как отрицание равносильности.

Так же сумма элементов пары должна делиться на 32 (наименьшее двухзначное число всей последовательности).

В остальном же решаем по схеме, о которой мы говорили в этой статье по 17 заданию из ЕГЭ по информатике.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета до-стоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

Открываем файл в программе Excel.

Выделим все ячейки с числами, нажмём «вырезать», используя контекстное меню. Вставим данные на 1 столбец вправо. Это делаем потому, что будем использовать для решения формулу, которая будет обращаться к ячейке слева.

Мысленно представим пространство на 1 строчку ниже, чем область, где находятся числа. Это пространство будет таким же по размерам, как и область с числами. В этом пространстве и будет наше решение.

Отметим особым цветом те ячейки, которые «спрятаны» от движения Робота стенками.

Для этих ячеек будем составлять другие формулы, в отличии от обычных ячеек.

Цвет ячейки можно поменять, нажав на кнопку «Цвет заливки» на главной вкладке программы.

Т.к. Робот направляется из левой верхней ячейки, то мы сначала и напишем формулу для этой ячейки. Пишем для ячейки B22:

=МАКС(;)+

Робот в любую ячейку может прийти либо сверху, либо слева. Для подсчёта максимального количества монет, мы должны выбрать максимальное предыдущее значение. Это и делаем формула. Плюс Робот должен взять монеты с текущей клетки.

Распространим формулу на всё пространство, не трогая закрашенные клетки.

Получается такая картина:

Для вертикальных подкрашенных полосок, Робот может попасть только сверху! Поэтому пишем формулу для ячейки, к примеру, для E25:

=+

Распространяем формулу по всему закрашенному столбцу. Аналогично делаем для всех вертикальны подкрашенных полосок.

В ячейки для горизонтально подкрашенных полосок, Робот может попасть только слева! Поэтому пишем формулу, к примеру, для ячейки I35:

=+

Распространяем формулу по всей закрашенной строчке. Аналогично делаем со всеми горизонтальными полосками.

В правом нижнем углу нашего рабочего пространства получается максимальное количество монет, которое может собрать Робот. В ячейке U41 получается число 2502.

Чтобы получить минимальную возможную сумму, в главной формуле функцию МАКС нужно заменить на МИН!

Удобно воспользоваться автоматической заменой через Ctrl+F.

Минимальная сумма равна 1124.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, четыре камня или увеличить количество камней в куче в три раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 46. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 46 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 45.

Будем говорить, что игрок имеет выигрышную стратегию, если он может вы-играть при любых ходах противника.

Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Решим задачу с помощью шаблона на Python.

def (x, p): if x>=46 and p==3: return True if x<46 and p==3: return False if x>=46: return False if p%2==1: return F(x+1, p+1) and F(x+4, p+1) and F(x*3, p+1) else: return F(x+1, p+1) or F(x+4, p+1) or F(x*3, p+1)for s in (1, 46): if F(s, 1): (s)

Ответ: 15

Для игры, описанной в предыдущем задании, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как бу-дет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

немного подправим прошлый шаблон и получаем 20 задачу.

def (x, p): if x>=46 and p==4: return True if x<46 and p==4: return False if x>=46: return False if p%2==0: return F(x+1, p+1) and F(x+4, p+1) and F(x*3, p+1) else: return F(x+1, p+1) or F(x+4, p+1) or F(x*3, p+1)for s in (1, 46): if F(s, 1): (s)

Для игры, описанной в задании 19, найдите минимальное значение S, при ко-тором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Об этих шаблонах мы говорили в этой статье.

def (x, p): if x>=46 and (p==3 or p==5): return True if x<46 and p==5: return False if x>=46: return False if p%2==1: return F(x+1, p+1) and F(x+4, p+1) and F(x*3, p+1) else: return F(x+1, p+1) or F(x+4, p+1) or F(x*3, p+1)def (x, p): if x>=46 and p==3: return True if x<46 and p==3: return False if x>=46: return False if p%2==1: return F1(x+1, p+1) and F1(x+4, p+1) and F1(x*3, p+1) else: return F1(x+1, p+1) or F1(x+4, p+1) or F1(x*3, p+1)for s in (1, 46): if F(s, 1): (s)
()for s in (1, 46): if F1(s, 1): (s)

Ответ: 10

Досрочный ЕГЭ по информатике 2023 (Задания 1-10)
Досрочный ЕГЭ по информатике 2023 (Задания 22-27)

В 17 задаче у вас ошибка
условие в программе должно быть:
if ((n1>9 and n19 and n2

Автор материалов — Лада Борисовна Есакова.

Рекурсия — это способ определения объектов (понятий), при котором определение объекта строится, опираясь на само понятие объекта.

Для того, чтобы задать рекурсию, необходимо описать:

— условие остановки рекурсии (базовый случай);

— рекуррентную формулу.

В программировании если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным.

Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия — основной прием программирования).

Классическим примером рекурсивного алгоритма является описание вычисления факториала:

Рекурсивные алгоритмы вычисления одной функции

Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n – на­ту­раль­ное число, задан сле­ду­ю­щи­ми ре­кур­рент­ны­ми со­от­но­ше­ни­я­ми:

F(n) = 1 при n = 1;

F(n) = F(n − 1) · n при n ≥ 2.

Чему равно зна­че­ние функ­ции F(6)?

В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.

По­сле­до­ва­тель­но на­йдём зна­че­ния функции от базового случая F(1) до искомого значения F(6):

F(1) = 1

F(2) = 2

F(3) = 6

F(4) = 24

F(5) = 120

F(6) = 720

Рекурсивные алгоритмы вычисления нескольких функций

Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = F(n–1) – G(n–1),

G(n) = F(n–1) + 2*G(n–1), при n >=2

Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.

По­сле­до­ва­тель­но на­йдём зна­че­ния функций от базового случая F(1), G(1) до искомых значений F(5), G(5):

F(1) = 1; G(1) = 1;

F(2) = F(1) – G(1) = 1 – 1 = 0;

G(2) = F(1) + 2*G(1) = 1+2 = 3;

F(3) = F(2) – G(2) = 0 – 3 = -3;

G(3) = F(2) + 2*G(2) = 0+6 = 6;

F(4) = F(3) – G(3) = -3 – 6 = -9 ;

G(4) = F(3) + 2*G(3) = -3+12 = 9;

F(5) = F(4) – G(4) = -9 – 9 = -18;

G(5) = F(4) + 2*G(4) = -9+18 = 9.

F(5)/G(5) = -18/9 = -2

Рекурсивные алгоритмы выполнения процедур

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­сан ре­кур­сив­ный ал­го­ритм F.

Чему равна сумма всех чисел, на­пе­ча­тан­ных на экра­не при вы­пол­не­нии вы­зо­ва F(1)?

Выпишем последовательно все действия, которые выполнят запускаемые процедуры:

(1) выполнит следующие действия: Вывод числа 1, F(2), F(4)

(2) выполнит следующие действия: Вывод числа 2, F(3), F(5)

(4) выполнит следующие действия: Вывод числа 4, F(5), F(7)

(3) выполнит следующие действия: Вывод числа 3, F(4), F(6)

(5) выполнит следующие действия: Вывод числа 5

(5) выполнит следующие действия: Вывод числа 5

(7) выполнит следующие действия: Вывод числа 7

(4) выполнит следующие действия: Вывод числа 4, F(5), F(7)

(6) выполнит следующие действия: Вывод числа 6

(5) выполнит следующие действия: Вывод числа 5

(7) выполнит следующие действия: Вывод числа 7

Просуммируем все числа, выведенные на экран: 1+2+4+3+5+5+7+4+6+5+7 = 49

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­са­ны две ре­кур­сив­ные функ­ции (процеду­ры): F и G.

Сколь­ко сим­во­лов «звёздоч­ка» будет на­пе­ча­та­но на экра­не при вы­пол­не­нии вы­зо­ва F(11)?

Выпишем последовательно все действия, которые выполнят запускаемые процедуры:

F(11)  G(10) * F(7) G(6) * F(3) G(2) * F(-1)

Всего на экране будет напечатано 3 «звездочки».

Дан рекурсивный алгоритм:

procedure F(n: integer);

 if n > 0 then begin

   F(n div 2);

   F(n div 2);

Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(6)?

Для наглядности изобразим схему работы алгоритма в виде дерева:

Причем, распишем до конца каждое значение F(n)  только один раз. Например, расписав один раз F(1), мы видим, что она напечатает в результате 5 звездочек. Т.е. F(1) = 5.

Проанализировав дерево, видим, что

F(0) = 1

F(2) = 3 + 2*F(1) = 13

F(3) = 1 + F(0) + 3*F(1) = 1 + 1 + 15 = 17

F(4) = 1 + F(1) + 3*F(2) = 1 + 5 + 3*13 = 45

F(6) = 1 + 3*F(3) + F(4) = 1 + 3*17 + 45 = 46 + 51 = 97

Благодарим за то, что пользуйтесь нашими публикациями.
Информация на странице «Задача №11. Использование рекурсивных алгоритмов.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать нужные и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из разделов нашего сайта.

Публикация обновлена:
08.05.2023

Вчера прошла основная волна ЕГЭ по информатике. Экзаменационная работа ничем не удивила, кроме 23-й задачи. Задача была не столько сложная, сколько необычная. Мне, например, она больше напомнила 10-ю задачу на элементы комбинаторики. Наверняка, будет предложено много самых разных решений. Предложу свое, которое возникло в голове при первом взгляде на задачу и заняло не более 10 минут (включая первый шок от прочтения).

Найти количество решений системы логических уравнений:

Где 1 ≤ i ≤ 8, 1 ≤ j ≤ 5;

Решим уравнение для i=1

Точно так же будет выглядеть решение для других значений i. Т.е. нам подойдут все наборы, кроме наборов:

Посчитаем общее число наборов и вычтем из него не подходящие. Это и будет ответом задачи.

Поскольку 1 ≤ i ≤ 8 ; 1 ≤ j ≤ 5, то общее число наборов равно

Наборы переменных , содержащие 10, это все наборы, кроме наборов:

Т.е. наборов.

Наборы переменных , содержащие 10 или 11, это все наборы, кроме наборов:

Т.е. наборов.

Наборы переменных , содержащие 11, но не содержащие 10 (т.к. мы их уже учли) это наборы:

Их 7 штук.

Наборы переменных , содержащие 10, это все наборы, кроме наборов:

Т.е. наборов.

Итак, ответ задачи: .

Спасибо за то, что пользуйтесь нашими статьями.
Информация на странице «ЕГЭ по информатике 2020. Как решалось задание 23!» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать нужные и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из разделов нашего сайта.

Публикация обновлена:
11.05.2023

Лада Есакова, преподаватель информатики и математики, автор книги «Информатика. Полный курс подготовки к ЕГЭ».

Забила необходимые цифры и написала формулу

ту формулу растянула до конца, и теперь мне необходимо просто посчитать числа, и вот у меня получилась сумма

А наибольшее число увидели, наложив фильтр по таблице и посмотрели, что отображено в нижней ячейке. Такое решение тоже можно использовать на экзамене тем, кто хорошо пользуется Excel, но не очень программирует. Наш ответ: количество – 314, а наибольшее число – 8993.

Задача № 18:
«Квадрат разлинован на NxN клеток (1˂N˂20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. При попытке выхода за границы квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета от 1 до 100. Посетив клетку, робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером NxN, каждая ячейка которой соответствует клетке квадрата.

пример входных данных:

Для указанных входных данных ответом должна быть пара чисел.»

Входящие данные приведены в виде таблицы Excel. Можно загрузить это в двумерный массив и написать код, а можно внимательно подумать, что же от нас хотят.

Нам нужно пройти из левого нижнего угла в правый верхний, перемещаться можно только либо вправо, либо вверх. Давайте для каждой клеточки посчитаем максимальное количество монет, которое можно собрать, попав в не, ведь в каждую клетку можно попасть несколькими путями.

В клетке А4 (в первой клетке) сумма собранных монет будет равна сумме монет, которая там лежит, то есть 2.
В клетку

В4 мы можем попасть только из соседней, из А4, потому что робот не умеет никак иначе двигаться, только вверх и вправо. Таким образом у нас получается 9 монет.

В клетку С4 мы можем попасть только из В4, суммируем монеты, 12+9=21.

И наконец в D4 попадаем из С4 и получаем 24 монеты.

То же самое касается клеток столбика А.

В А3 можно попасть только из А4, получаем 8 монет, в клетке А2 получаем 12 монет, а в А1 – 15.

А дальше у меня заинтересованность в том, чтобы, находясь в клетке В3 количество монет было максимальным. В нее можно попасть из А3 или из В4. Смотрим, в какой клетке у нас больше денег, через ту клетку и идем. Больше денег в В4, из нее и пойдем в В3 и получим 18 монет.

Аналогично в клетку С3 можно попасть из клетки С4 или из клетки В3. Больше монет в клетке С4, пойдем через нее и получим 25 монет.

На всех остальных клетках, кроме столбца А и строки 4, у меня стоит выбор взять источник монет слева или снизу. Берем тот, который больше.

Вот именно это я и написала в формуле Excel.
В нижний столбик пишем формулу предыдущего и плюс содержание самой ячейки

В левый пишу формулу нижнего плюс сама ячейка

А вот на этой картинке изображено самое интересное

Здесь у нас формула

Это значит, что если левый сосед больше, суммирую его, если нижний больше, то суммирую его.
Размножаем эту формулу до ячейки D

Вверху у меня в итоге оказалось 1178, это и месть наибольшее количество.

Аналогично делаем второй лист таблицы и считаем наименьшее количество. Делаем формулу наоборот: берем соседнюю клетку, в которой меньше монет. Далее растягиваем формулу до верхнего правого угла и получаем ответ 539.

Ответ задачи: наибольшее количество монет, которе смог собрать Робот – 1178, а наименьшее количество – 539.

Задача №24:
«Текстовый файл состоит не более чем из 1 000 000 символов – цифр т 0 до 9. Определите длину самой длинной возрастающей последовательности (количество подряд идущих цифр, каждая из которых строго больше предыдущей). Для выполнения этого задания следует написать программу.»

Приведу вам пример программы на Pascal

Закачиваем файл, считываем в С1 предыдущее значение, в С2 – последующее значение. В случае, если С2 больше С1, счетчик увеличивается на 1. Как только последовательность перестает возрастать или даже повторно цифра пошла, счетчик обнуляется, но длина цепочки запоминается и сравнивается с максимальным значением.

В k храним текущее значение возрастающей последовательности, а в переменной max храню максимальное значение. Как только последовательность закончила возрастать, k больше не увеличиваем, сравниваем, не стала ли последовательность больше максимального значения, максимальное запоминаем, обнуляем и начинаем сначала.

Тут все очень просто.

Все видео по информатике

Публикация обновлена:
08.05.2023

Пройти тестирование по 10 заданиям
Пройти тестирование по всем заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Производится звукозапись музыкального фрагмента в формате стерео (двухканальная запись) с частотой дискретизации 32 кГц и 32-битным разрешением. Результаты записываются в файл, сжатие данных не производится; размер полученного файла 40 Мбайт. Затем производится повторная запись этого же фрагмента в формате моно (одноканальная запись) с частотой дискретизации 16 кГц и 16-битным разрешением. Сжатие данных не производилось.

Укажите размер файла в Мбайт, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно.

Производится звукозапись музыкального фрагмента в формате стерео (двухканальная запись) с частотой дискретизации 32 кГц и 32-битным разрешением. Результаты записываются в файл, сжатие данных не производится; размер полученного файла – 64 Мбайт. Затем производится повторная запись этого же фрагмента в формате моно (одноканальная запись) с частотой дискретизации 16 кГц и 16-битным разрешением. Сжатие данных не производилось. Укажите размер файла в Мбайт, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно.

Музыкальный фрагмент был записан в формате квадро (четырёхканальная запись), оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла без учёта размера заголовка файла  — 12 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате моно и оцифрован с разрешением в 2 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Укажите размер в Мбайт файла, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно. Искомый объём не учитывает размера заголовка файла.

Музыкальный фрагмент был записан в формате стерео (двухканальная запись), оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла без учёта размера заголовка файла  — 48 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате моно и оцифрован с разрешением в 1,5 раза выше и частотой дискретизации в 3 раза меньше, чем в первый раз. Сжатие данных не производилось. Укажите размер в Мбайт файла, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно. Искомый объём не учитывает размера заголовка файла.

Для проведения эксперимента записывается звуковой фрагмент в формате квадро (четырёхканальная запись) с частотой дискретизации 32 кГц и 32-битным разрешением. Результаты записываются в файл, сжатие данных не производится; дополнительно в файл записывается служебная информация, необходимая для эксперимента, размер полученного файла 97 Мбайт. Затем производится повторная запись этого же фрагмента в формате моно (одноканальная запись) с частотой дискретизации 16 кГц и 16-битным разрешением. Результаты тоже записываются в файл без сжатия и со служебной информацией, размер полученного файла 7 Мбайт. Объём служебной информации в обоих случаях одинаков. Укажите этот объём в мегабайтах. В ответе укажите только число (количество Мбайт), единицу измерения указывать не надо.

Пройти тестирование по этим заданиям