Определите наименьшее значение n при котором сумма чисел которые будут выведены при вызове f n

Определите наименьшее значение n при котором сумма чисел 3200000

Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 3 при n ≤ 1
F(n) = F(n–1) + 2·F(n–2) – 5, если n > 1
Чему равно значение функции F(22)?

Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 0;
F(n) = F(n/2), если n > 0 и при этом n чётно;
F(n) = 1 + F(n – 1), если n нечётно.
Назовите минимальное значение n, для которого F(n) = 12.

Ответ: 4095

Определите, сколько символов * выведет эта процедура при вызове F(35):
def F( n ):
print(‘*’)
if n >= 1:
print(‘*’)
F(n-1)
F(n-2)
print(‘*’)

Ответ: 96631265

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n*n + 5*n + 4, при n > 30
F(n) = F(n+1) + 3*F(n+4), при чётных n ≤ 30
F(n) = 2*F(n+2) + F(n+5), при нечётных n ≤ 30
Определите количество натуральных значений n из отрезка [1; 1000], для которых сумма цифр значения F(n) равна 27.

Информатика 11 класс пробный вариант №9 решу ЕГЭ 2022 задания с ответами

1)На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице звёздочками обозначено наличие дорог. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Найдите номера пунктов F и H. В качестве ответа запишите найденные номера в порядке убывания без разделителей.

Ответ: 63

2)Логическая функция F задаётся выражением a ≡ b ∨ b → c. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

Ответ: bca

3)В файле 3-40.xls приведён фрагмент базы фрагмент базы данных «Города и страны», описывающей различные страны, города и языки. База данных состоит из трех таблиц. Таблица «Страны» (код, название, континент, регион, площадь, год получения независимости, население, ОПЖ – ожидаемая продолжительность жизни, ВНД – валовый национальный доход, предыдущее значение ВНД, форма правления, идентификатор столицы). Таблица «Города» (идентификатор, название, код страны, район, население). Таблица «Языки» (код языка, код страны, название, является ли официальным, процент использования в стране). По некоторым значениям данных нет, в этом случае в таблице внесено значение NULL. На рисунке приведена схема базы данных. Используя информацию из приведённой базы данных, определите количество городов, расположенных в странах с населением более 100 000 000.

Ответ: 1897

4)По каналу связи передаются сообщения, содержащие только шесть букв: А, В, Г, У, С, Т; для передачи используется двоичный код, удовлетворяющий условию Фано. Буквы Т, У, С, А имеют коды 10, 000, 11, 001 соответственно. Укажите наименьшую возможную длину закодированной последовательности для слова СУСТАВ.

Ответ: 15

5)Автомат обрабатывает натуральное число N<256 по следующему алгоритму: 1) Строится восьмибитная двоичная запись числа N. 2) Инвертируются все разряды исходного числа (0 заменяется на 1, 1 на 0). 3) К полученному двоичному числу прибавляют единицу. 4) Полученное число переводится в десятичную систему счисления. Чему равен результат работы алгоритма для N = 80?

Ответ: 176

6)Определите наименьшее и наибольшее введённое значение переменной s, при котором программа выведет число 56. В ответ запишите оба числа в порядке возрастания без пробелов и других разделителей.

Ответ: 2427

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

Ответ: 512

8)Все 5-буквенные слова, составленные из букв А, З, Н, С, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ААААА 2. ААААЗ 3. ААААН 4. ААААС 5. АААЗА … Какое количество слов находятся между словами САЗАН и ЗАНАС (включая эти слова)?

Ответ: 496

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

Ответ: 1033

10)В файле 10-141.docx приведена книга Н.В. Гоголя «Вечера на хуторе близ Диканьки». Сколько раз предлог «Под» (с заглавной буквы) встречается в тексте повести «Страшная месть» (не считая сносок)? В ответе укажите только число.

Ответ: 3

11)Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код, состоящий из двух частей. Первая часть кода содержит 10 символов, каждый из которых может быть одной из 26 заглавных латинских букв. Вторая часть кода содержит 8 символов, каждый из которых может быть одной из десятичных цифр. При этом в базе данных сервера формируется запись, содержащая этот код и дополнительную информацию о пользователе. Для представления кода используют посимвольное кодирование, все символы в пределах одной части кода кодируют одинаковым минимально возможным для этой части количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Для хранения данных о 60 пользователях потребовалось 1980 байт. Сколько байтов выделено для хранения дополнительной информации об одном пользователе? В ответе запишите только целое число – количество байтов.

Ответ: 22

12)Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. 1. заменить (v, w) 2. нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось(01) ИЛИ нашлось(02) ИЛИ нашлось(03) заменить(01, 302) заменить(02, 3103) заменить(03, 20) КОНЕЦ ПОКА КОНЕЦ Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 28 единиц, 34 двойки и 45 троек. Сколько единиц было в исходной строке?

Ответ: 17

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

Ответ: 24

14)Значение выражения 5∙2161256 – 5∙361146 + 4∙61053 – 1087 записали в системе счисления с основанием 6. Найдите сумму цифр получившегося числа и запишите её в ответе в десятичной системе счисления.

Ответ: 12642

15)На числовой прямой даны два отрезка: P=[2,10] и Q=[6,14]. Какова максимальная длина отрезка A, при выборе которого формула ((x ∈ А) → (x ∈ P)) ∨ (x ∈ Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

Ответ: 12

16)Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями: F(n) = 1, при n < 2, F(n) = F(n/3) + 1, когда n ≥ 2 и делится на 3, F(n) = F(n — 2) + 5, когда n ≥ 2 и не делится на 3. Назовите минимальное значение n, для которого F(n) равно 73.

Ответ: 5101

17)В файле 17-10.txt содержится последовательность целых чисел. Элементы последовательности могут принимать значения от 0 до 10000 включительно. Определите сначала количество троек элементов последовательности, из которых можно составить прямоугольный треугольник, а затем сумму всех гипотенуз треугольников в подходящих тройках. Под тройкой подразумевается три идущих подряд элемента последовательности.

Ответ: 370 209813

18)Квадрат разлинован на N×N клеток (1 < N < 20), в каждой клетке записано целое число. В левом нижнем углу квадрата стоит Робот. За один ход Робот может переместиться в пределах квадрата на одну клетку вправо или на одну клетку вверх. Выходить за пределы квадрата робот не может. При этом ведётся подсчёт суммы по следующим правилам: число в очередной клетке, через которую проходит робот, включается в сумму, если оно больше числа в предыдущей клетке на пути робота. Если число в очередной клетке не больше числа в предыдущей, сумма не изменяется. Число в начальной клетке всегда включается в сумму. Определите минимальную и максимальную сумму, которую может получить Робот при перемещении из левого нижнего угла в правый верхний. Исходные данные для Робота записаны в файле 18-109.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата. В ответе запишите сначала максимальную сумму, затем – минимальную.

Ответ: 1536 666

22)Ниже записана программа, которая вводит натуральное число x, выполняет преобразования, а затем выводит результат. Укажите наименьшее значение x, при вводе которого программа выведет число 45.

Ответ: 106

23)Исполнитель Калькулятор преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера: 1. Умножь на 2 2. Умножь на 2 и прибавь 1 Сколько различных результатов можно получить из исходного числа 1 после выполнения программы, содержащей ровно 15 команд?

Ответ: 32768

24)Текстовый файл 24-171.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Файл разбит на строки различной длины. Определите максимальную длину цепочки символов, состоящей из повторяющихся фрагментов XYZ. Цепочка должна начинаться с символа X и заканчиваться символом Z. Например, для строки SAZZXYZXYZXZQW длина цепочки равна 6: XYZ+XYZ.

Ответ: 51

25)Обозначим через M разность максимального и минимального числа среди простых делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю. Напишите программу, которая перебирает целые числа, большие 450000, в порядке возрастания и ищет среди них такие, для которых значение M при делении на 29 даёт в остатке 11. Выведите первые 4 найденных числа в порядке возрастания, справа от каждого числа запишите соответствующее значения M.

26)В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Рассматриваются пары с чётной суммой, такие что: — хотя бы половина чисел набора меньше среднего арифметического пары — хотя бы четверть чисел набора больше среднего арифметического пары Определите количество таких пар и наименьшее из средних арифметических таких пар. Входные данные представлены в файле 26-50.txt следующим образом. Первая строка содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 109. В ответе запишите два целых числа: сначала количество пар, затем наименьшее среднее арифметическое.

27)Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно два числа так, чтобы сумма всех выбранных чисел оканчивалась либо на 3 в семеричной записи, либо на 5 в десятичной записи, но не оканчивалась на 3 в семеричной записи и на 5 в десятичной записи одновременно, и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (N ≤ 250000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

Определите наименьшее натуральное значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 3200000. Запишите в ответе.

Определите наименьшее натуральное значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 3200000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел. нужен ответ

Изображение Ответ

Ответы

Ответ

даром ничто не дается: судьба

жертв искупительных просит

в стремленье к идеалу дурного, впрочем, нет.

воля и труд человека дивные дивы творят!

знай: сила не в богатстве, не в том – велик ли, мал ли чин а в равенстве и братстве!

Задание 16. Вычисление значения рекурсивной функции

Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число.

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

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

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

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

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

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

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

Найдите сумму чисел, которые будут выведены при вызове F(1).

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

Найдите сумму чисел, которые будут выведены при вызове F(1)

Ниже записаны две рекурсивные процедуры: F и G:

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

Ниже записана рекурсивная процедура:

Что будет напечатано на экране при выполнении вызова F(11)?

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

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

Определите, сколько символов * выведет эта процедура при вызове F(22):

В данной программе НЕЛЬЗЯ. применять декоратор lru_cache, т.к. вместо того, чтобы выполнять пользовательскую функцию и увеличивать значение k, программа будет брать уже вычисленные значения из cache, а значит, значение счетчика увеличиваться не будет (хорошо демонстрирует уменьшение количества необходимых вычислений)

Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 500000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.

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

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

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

Чему равно значение функции F(99) + F(100)?

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

Чему равно значение F(14) + G(14)?

Определите, сколько символов * выведет эта процедура при вызове F(35):

Определите наибольшее трехзначное значение n, при котором значение F(n), будет больше числа 7. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующее значение F(n).

Определите наименьшее значение n такое, что последнее выведенное число при вызове F(n) будет больше числа 32. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующее значение F(n).

Определите наименьшее значение суммы n + m такое, что значение F(n, m) больше числа 15 и выполняется условие: n и m – разные натуральные числа. Запишите в ответе сначала значения n и m, при которых указанная сумма достигается, в порядке неубывания, а затем – соответствующее значение F(n, m). Числа в ответе разделяйте пробелом.

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

Чему равна сумма цифр значения функции F(18) ?

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

Определите количество натуральных значений n, при которых F(n) меньше, чем 10 7 .

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

Определите количество натуральных значений n из отрезка [1;1000], для которых все цифры значения F(n) чётные.

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

Здесь «//» обозначает деление нацело. Определите количество натуральных значений n из отрезка [1;1000], для которых значения F(n) содержит не менее двух цифр 8.

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

Вычислите значение F(34).

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

Вычислите значение F(17).

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

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

Ручное решение:

Программное решение:

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

Чему равно значение выражения F(2008) – F(2006)?

Ручное решение:

Программное решение:

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

Чему равно значение выражения F(4850) + F(5000)?

Решения задач:

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

Чему равно значение выражения F(3516) / F(3513)?

Чему равно значение выражения F(2073) / F(2070)

Чему равно значение выражения F(3303) / F(3300)? В ответе укажите только целую часть числа.

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

Чему равно значение выражения (F(1006) – F(1004)) / F(1005)?

Чему равно значение выражения F(2254) – F(2252)?

Чему равно значение выражения F(1900) / 2 1890 ?

Чему равно значение выражения F(12345) · (F(10) − F(12)) / F(11) + F(10101)?

Чему равно значение выражения 1000 · F(7) / F(4)?

Примечание. Факториал числа n, который обозначается как n!, вычисляется по формуле
n! = 1 · 2 · … · n

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

Чему равно значение выражения F(174) – F(3)?

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

Чему равно значение выражения F(9950) – F(9999)?

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

Чему равно значение выражения F(107864, 3)?

Значение функции увеличивается на единицу, когда m является делителем числа n. Результатом программы будет количество делителей числа 107864, в диапазоне от 3 и до 107864, включительно.

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

Чему равно значение выражения F(4952) + 2 ⋅ F(4958) + F(4964)?

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

Чему равно значение выражения F(4500) + F(5515)? В ответе запишите только целое число.
Примечание: операция a % b находит остаток от деления числа a на число b.

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

Чему равно значение выражения F(1025) / F(1030)? В ответе запишите только целое число.
Примечание: операция a % b находит остаток от деления числа a на число b.

(А. Богданов) Обозначим частное от деления натурального числа a на натуральное число b как a // b, а остаток как a % b. Например, 17 // 3 = 5, 17 % 3 = 2. Алгоритм вычисления функции F(n), где n – неотрицательное число, задан следующими соотношениями:

Найдите количество таких чисел, не превышающих 10 10 , для которых F(n) = 9.

Все числа, начинающиеся на 9 и окачивающиеся на 0 дают F(n) = 9 (можно убедиться, выполнив программу с числами в указанных диапазонах, например от 900 до 990, с шагом 10).

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

Найдите количество таких чисел в диапазоне от 100 000 000 до 200 000 000, для которых F(n) не делится на 3.

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

Найдите количество таких чисел в диапазоне от 189 456 678 до 567 654 321, для которых F(n) не делится на 7.

Числа, для которых F(n) делится на 7 — это n, с остатком 6 от деления на 7 или кратные 7. Находим все такие n в указанном диапазоне (первое с остатком 6 — 189456679, последнее кратное 7 — 56765319). Затем из общего количества чисел вычитаем найденное количество чисел.

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

Найдите количество таких чисел в диапазоне от 865 432 015, 1 585 342 628, для которых F(n) > F(n+1).

F(n) > F(n + 1) только для чисел, оканчивающихся на 9:

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

Найдите количество таких чисел a, для которых можно найти число b, такое что F(a, b) = 2744000

Проанализируем рекурсивную функцию, выполнив вычисления для значения F(4, 4).

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

Назовите максимальное значение n, для которого возможно вычислить F(n).

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

Назовите количество значений n на отрезке [1;100000], для которых F(n) равно 16.

тождественно истинно (то есть принимает значение 1 при любых натуральных значениях переменных х, y, z).

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

Сколько различных значений может принимать функция F(n) при n, принадлежащих отрезку [1; 1000]?

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

Определите четыре последние цифры числа F(47)

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

Определите сумму значений, являющихся результатом вызова функции для значений n в диапазоне [40; 50].

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

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

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

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

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

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

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

Для какого значения n значение F(n) будет равно 25?

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

Сколько существует чисел n, меньших 1000, для которых значение F(n) будет равно 0?

Определите сумму четных значений F(n) для всех n на отрезке [35,50]. В качестве ответа запишите количество цифр в десятичной записи этой суммы.

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

Определите количество значений n на отрезке [1, 500 000 000], для которых F(n) = 3.

Нам подходят все числа у которых в двоичной СС только две единицы

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

Чему равно значение F(23) — F(21)?

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

Чему равно значение F(2022) — F(2023)?

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

Чему равно значение выражения F(2024) – F(2021)

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

Чему равно значение выражения F(2024) – F(2020)

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

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

��Решим задачу кодом:
•будем проверять текущую сумму чисел вызова f(n) через цикл while: если сумма меньше или равно 5000000, увеличиваем число n. Иначе выходим — нашли наименьшее значение.
•подсчет текущей суммы вынесем в отдельную функцию f(n)

��Функция f(n):
•воспользуемся переменной s для нахождения суммы чисел
•все выводы чисел суммируем в s, в том чисел и сумму чисел от вызовов f(n-1) и f(n-4)

Оптимизационные алгоритмы в языке программирования Python в решении задач компьютерного ЕГЭ по информатике

Единый государственный экзамен по информатике необходим тем, кто планирует поступать в российские вузы на специальности, связанные с IT-технологиями. Этот экзамен нужен тем, кто хочет стать программистом, разработчиком, специалистом по информационным технологиям.

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

В настоящее время все большую популярность приобретает язык Python . Одна из причин популярности Python – более простое и компактное оформление, чем в других языках. Это самый популярный язык общего назначения: он используется для машинного обучения, аналитике, разработке игр и в науке о данных. В данной работе будет применение языка Python в решении задач компьютерного ЕГЭ по информатике, где особое внимание я уделила решению задачи 25 на поиск делителей, простых чисел, а также соответствия маскам чисел. Данное задание необходимо выполнять с помо

Объект работы – оптимизированные алгоритмы в процессе решения задач компьютерного ЕГЭ по информатике.

Предмет работы – средства решения задач компьютерного ЕГЭ по информатике.

Цель работы – провести обзор возможностей языка программирования Python при решении задач компьютерного ЕГЭ по информатике, с помощью оптимизированных алгоритмов.

— рассмотреть основы языка программирования Python ;

— выделить типы задач компьютерного ЕГЭ по информатике и, по возможности, решить их с помощью оптимизированных алгоритмов средствами языка программирования Python .

1. Основы языка программирования Python

Сценарии исходного кода Python состоят из так называемых логических строк , каждая из которых в свою очередь состоит из физических строк . Для обозначения комментариев используется символ #. Комментарии и пустые строки интерпретатор игнорирует.

Физические строки разделяются самим символом конца строки. Для выделения блоков кода используются исключительно отступы. Логические строки с одинаковым размером отступа формируют блок, и заканчивается блок в том случае, когда появляется логическая строка с отступом меньшего размера. Именно поэтому первая строка в сценарии Python не должна иметь отступа.

Других радикальных отличий от других языков программирования в синтаксисе Python нет. Также используются стандартные правила для заданий идентификаторов переменных, методов и классов – имя должно начинаться с подчеркивания или латинского символа любого регистра и не может содержать символов @, $, %. Также не может использоваться в качестве идентификатора только один символ подчеркивания.

Типы данных, используемых в Python, совпадают с другими языками – целые и вещественные типы данных; дополнительно поддерживается комплексный тип данных – с вещественной и мнимой частью. Python поддерживает строки, которые могут быть заключены в одинарные, двойные или тройные кавычки, при этом строки являются immutable-объектами, т.е. не могут изменять свое значение после создания.

Есть в Python и логический тип данных bool c двумя вариантами значения – True и False. Для повышения читаемости кода рекомендуется использовать для логических переменных тип bool.

В Python определены три типа коллекций для хранения наборов данных:

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

Список – это изменяемая упорядоченная последовательность элементов. Элементы списка также разделяются запятыми, но задаются уже в квадратных скобках. Для создания списков предлагается функция list().

Словарь является хеш-таблицей, сохраняющей элемент вместе с его идентификатором-ключом. Последующий доступ к элементам выполняется тоже по ключу, поэтому единица хранения в словаре – это пара объект-ключ и связанный с ним объект-значение. Словарь – это изменяемая, но не упорядоченная коллекция, так что порядок элементов в словаре может меняться со временем. Задается словарь в фигурных скобках, ключ отделяется от значения двоеточием, а сами пары ключ/значение разделяются запятыми. Для создания словарей доступна функция dict().

В листинге 1 приведены примеры различных коллекций, доступных в Python.

Листинг 1. Виды коллекций, доступные в Python

(‘w’,‘o’,‘r’,‘l’,‘d’) # кортеж из пяти элементов

(2.62,) # кортеж из одного элемента

[“test”,’me’] # список из двух элементов

< 5:‘a’, 6:‘b’, 7:‘c’ ># словарь из трех элементов с ключами типа int

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

Синтаксис определения функций в Python крайне простой; с учетом изложенных выше требований (листинг 2).

Листинг 2. Виды коллекций, доступные в Python

Как видно, необходимо использовать служебное слово def, двоеточие и отступы. Вызвать функцию также очень просто:

Есть только несколько моментов, специфичных для Python, которые стоит учитывать. Параметры могут передаваться как просто по порядку перечисления, так и по именам, в этом случае не нужно указывать при вызове те параметры, для которых есть значения по умолчанию, а передавать только обязательные или менять порядок параметров при вызове функции (листинг 3).

Листинг 3. Виды коллекций, доступные в Python

#функция, выполняющая деление нацело – с помощью оператора //

def foo(delimoe, delitel):

return delimoe // delitel

print divide(50,5) # результатработы : 10

print divide(delitel=5, delimoe=50) # результатработы : 10

Функция в Python обязательно возвращает значение – это делается либо явно с помощью оператора return, за которым следует возвращаемое значение, либо, в случае отсутствия оператора return, возвращается константа None, когда достигается конец функции. Как видно из примеров объявлений функций, в Python нет необходимости указывать, возвращается что-либо из функции или нет, однако если в функции имеется один оператор return, возвращающей значение, то и другие операторы return в этой функции должны возвращать значения, а если такого значения нет, то необходимо явно прописывать return None.

Если функция очень простая и состоит из одной строки, то ее можно определить прямо на месте использования, в Python подобная конструкция называется лямбда-функцией (lambda). lambda-функция – это анонимная функция (без собственного имени), телом которой является оператор return, возвращающий значение некоторого выражения. Такой подход может оказаться удобным в некоторых ситуациях, однако стоит заметить, что повторное использование подобных функций невозможно.

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

2. Обзор задач компьютерного ЕГЭ по информатике и их решение на языке Python

В компьютерного ЕГЭ (далее КЕГЭ) по информатике предлагаются десять типов заданий на следующие темы.

2. Решение уравнений численными методами

3. Перебор целых чисел. (Разбиение числа на цифры)

4. Перебор чисел. Проверка делимости

5. Перебор целых чисел. Количество делителей

6. Символьные строки. Цепочки символов

7. Функции двух аргументов. Таблицы значений

8. Электронные таблицы. Встроенные функции (не решается средства Python )

9. Рекурсия. Рекурсивные функции

10. Исследование моделей. Оптимизация

1. Пример задания на вычисление

С помощью программы Калькулятор или электронных таблиц вычислите значение выражения. В ответе запишите только целую часть результата. Можно также написать программу.

Программа на языке Python

print ( ((1 + cos (3.53* pi )*10)*310) ** 2 )

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

Основные математические функции языка Python представлены в таблице 1. Прежде чем использовать математические функции, необходимо в начале программы написать инструкцию import math, однако тогда перед упоминанием каждой функции необходимо будет добавлять имя модуля — math, например, y=math.sin(x). Другой способ, который позволит избежать многократного вызова модуля math, — сделать следующую запись в начале программы: from math import *.

Таблица 1. Общие математические функции модуля Math

Запись на Python

Возвращает значение функции Sin от числа х

Возвращает значение функции Cos от числа х

math.tan (x) или math.sin (x)

Возвращает значение функции Tg от числа х

math.cos (x) / math.sin (x)

Возвращает значение функции Ctg от числа х

Возвращает абсолютную величину числа х

Возвращает результат возведения числа е в степень X

Возвращает натуральный логарифм от х+1

Возвращает результат извлечения квадратного корня числа х

Возвращает логарифм числа х по основанию

math.cos (x) * math.cos (x)

Возвращает результат возведения функции

Cos х в квадрат

Возвращает значение функции арккосинус от числа х

Возвращает значение функции арксинус от числа х

Возвращает значение функции арктангенс от числа х

Преобразует радианы в градусы

Преобразует градусы в радианы

Возвращает значение, округленное до ближайшего меньшего целого

Возвращает значение, округленное до ближайшего большего целого

Возвращает факториал числа. 3 != 1 *2*3

В таблице 2 представлены некоторые встроенные функции для работы с числами, не требующие подключения модуля math.

Таблица 2. Функции для работы с числами

Запись на Python

Возвращает результат округления числа х до ближайшего меньшего целого значения для чисел с дробной частью меньше 0.5 или результат округления числа х до ближайшего большего целого значения для чисел с дробной частью больше 0.5

другой вариант х**у

Возвращает результат возведения числа х в степень у

m ах(список чисел через запятую)

Возвращает большее значение из списка чисел

min (список чисел через запятую)

Возвращает меньшее значение из списка чисел

sum(список K чисел через запятую)

Возвращает сумму значений элементов последовательности

Преобразует объект (например, строковое значение, целое значение) в вещественное число

2. Пример задания на решение уравнения численным методом

Известно, что уравнение на отрезке [0; 1,5] имеет единственный корень. Найдите его приблизительное значение с точностью не менее 0,00001 и запишите в ответе найденное значение ровно с пятью значащими цифрами после запятой.

Программа на языке Python:

from math import cos, exp # подключить функции cos, exp

def f(x): # это функция f(x)

return 0.01*exp(x) — cos(3*x)

a , b = 0, 1.5 # границыотрезка

while b-a > 1e-6: # пока ширина отрезка >= 10^(-6)

c = (a + b) / 2 # середина отрезка

if f(a)*f(c) <= 0: # сдвигаем правую или левую границу

# вывод с 5 знаками в дробной части

print( «<:.5f>«.format((a + b) / 2) )

3. Пример задания на перебор целых чисел. Разбиение числа на цифры

Назовём натуральное четырёхзначное число N (1000 £ N £ 9999) счастливым, если суммы двух его первых и двух последних цифр различаются не более, чем на 3. Найдите количество таких чисел.

Программа на языке Python

for n in range(1000, 10000):

d0 = n % 10; n //= 10

d1 = n % 10; n //= 10

if abs(d3+d2-d1-d0) <= 3:

Поскольку заданный отрезок [1000; 9999] содержит всего 9000 чисел, можно решать задачу простым перебором. Для этого сначала нужно разбить число на цифры с помощью операций деления нацело и остатка от деления; цифры помещаем в переменные d0, d1, d2, d3. Затем проверяем «счастливость» числа: число счастливое при выполнении условияв этом случае увеличиваем счётчик найденных счастливых чисел.

4. Пример задания на перебор целых чисел. Проверка делимости

Рассматривается множество целых чисел, принадлежащих отрезку [1033; 7737], которые делятся на 5 и не делятся на 11, 17, 19 и 23. Найдите количество таких чисел и максимальное из них. В ответе запишите два числа через пробел: сначала количество, затем максимальное число.

Программа на языке Python

for n in range(1033, 7737+1):

if (n % 5 == 0) and (n % 11 != 0) and \

(n % 17 != 0) and (n % 19 != 0) and (n % 23 != 0):

print(count, maxGood)

Поскольку заданный отрезок [1033; 7737] содержит не так много чисел, можно решать задачу простым перебором. Условие будем понимать так: интересующие нас числа делятся на 5 и не делятся ни на одно из чисел 11, 17, 19 и 23. Нам выгоднее перебирать числа в порядке возрастания, тогда последнее найдённое число – это и есть искомое максимальное подходящее число (если требуется найти наименьшее подходящее число, удобнее перебирать числа в порядке убывания)

Ответ: 1040 7730

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [194455; 194500], числа, имеющие ровно 4 различных делителя. Выведите эти четыре делителя для каждого найденного числа в порядке возрастания.

Программа на языке Python

for n in range(194455, 194500+1):

for d in range(1,n+1):

divs.append(d)

if len(divs) == 4:

print( *divs )

При написании программы на языке Python можно поступить так

for для всех чисел n в интервале:

divs = массив всех делителей n

if len(divs) == 4:

вывести массив делителей

5. Пример задания на работу с простыми числами

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [3532000; 3532160], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку.

Программа на языке Python

from math import sqrt

for n in range(3532000, 3532160+1):

prime = True

for d in range(2, round(sqrt(n))):

prime = False

print( count, n )

6. Пример задания на работу с символьными строками

В текстовом файле k7.txt находится цепочка из символов латинского алфавита A, B, C, D, E. Найдите количество цепочек длины 3, удовлетворяющих следующим условиям:

· 1-й символ – один из символов B, C или D;

· 2-й символ – один из символов B, D, E, который не совпадает с первым;

· 3-й символ – один из символов B, C, E, который не совпадает со вторым.

Программа на языке Python

s = open(‘k7.txt’).read()

for i in range(len(s)-2):

if s[i] in ‘BCD’ and s[i+1] in ‘BDE’ \

and s[i+2] in ‘BCE’ and s[i]!=s[i+1] \

1) Считываем из файла и перебираем символы.

2) Перебираем все тройки символов. Примем, что переменная i будет хранить номер первого элемента в тройке, то есть, будем рассматривать тройки (s[i], s[i+1], s[i+2]).

3) Организуем цикл который перебирает значения i от 1 до len(s)-2

for i in range(len(s)-2):

4) Проверяем символы в каждой тройке на соответствие условию. Проверка принадлежности символов набору аналогична заданию 1. Дополнительно необходимо указать условия неравенства символов, указанных в условии задачи. Если условия выполняются, то к переменной количества прибавляется единица.

7. Пример задания на вычисление значения функции от двух переменных

С помощью редактора электронных таблиц создайте таблицу вещественных значений выражения для следующих вещественных значений x и y:

x = 5,5; 6,0; …; 8,5; y = 10,0; 10,3; …; 13,0.

Вычислите сумму получившихся значений и запишите её целую часть в ответе.

Для выполнения этого заданий также можно написать программу.

1) Чтобы написать программу, нужно использовать вложенный цикл: в одном цикле будем перебирать значения x, а во втором (вложенном) – значения y; учитывая, что цикл с переменной ( for . in . ) работает только с целыми последовательностями чисел, придётся использовать циклы с условием:

s = 0 # это неправильная программа

x = 5.5 # это неправильная программа

while x <= 8.5: # это неправильная программа

while y <= 13:

# print(x, y) # отладочная печать, см. обсуждение ниже

s += 2* x **3/( y +1)

y += 0.3

x += 0.5

print ( s )

сумма значений функции накапливается в переменной s

2) однако эта программа выводит неверный ответ.

3) Дело в том, что вещественные числа, которые нельзя представить в виде суммы целых (в том числе и отрицательных) степеней числа 2, в двоичной системе счисления представляют собой бесконечную дробь и поэтому не могут быть точно записаны в памяти двоичного компьютера; при выполнении вычислений с такими числами ошибка накапливается, и к последнему шагу (это можно проверить с помощью отладочной печати) значение y равно не 12,7, а чуть больше:

12.700000000000006

из-за этого следующее значение, равное 13,000000000000006, уже больше, чем 13, и не удовлетворяет условию работы цикла; таким образом, на каждом шаге цикла по x мы теряем одно значение y, и соответствующее значение функции не включается в сумму.

4) с переменной x подобных проблем нет, так как шаг изменения x равен 0,5 = 2 –1

5) исправить ситуацию можно так: организовать перебор только целых значений, используя вспомогательные целочисленные переменные x₁₀ = x × 10 и y ₁₀ = y × 10:

for x10 in range(55, 86, 5):

for y10 in range(100, 131, 3):

s += 2*( x 10/10)**3/( y 10/10+1)

8. Пример задания на вычисление значения рекурсивной функции

Первое, что может прийти в голову – вызывать приведённую процедуру при разных значениях параметра и увеличивать это значение до тех пор, пока сумма выведенных чисел не превысит заданное значение 500000; это тупиковый подход, поскольку чисел очень много и сложение займет очень много времени при низкой вероятности правильного ответа

Можно попробовать изменить программу так, чтобы сумма выводимых чисел считалась автоматически: добавим в программу глобальную переменную s и будем увеличивать её при выводе каждого числа на значение этого числа; при этом для ускорения (значительного!) работы программы сразу закомментируем вывод чисел на экран:

global s # если не объявить s глобальной – ошибка!

F ( n -1)

Дальше можно написать такую программу и запускать её при различных значениях переменной n:

F ( n )

print ( n , s )

Увеличивая каждый раз значение n на 1, мы в конце концов найдём первое (минимальное) значение n , при котором сумма чисел, которые будут выведены при вызове F( n ), будет больше 500000 – это F(24) = 531864

Ответ: 24 531864.

9. Пример задания на оптимизацию

На покупку мебели выделено 500 тыс. рублей. Стоимость одного комплекта составляет 18 тыс. рублей. Запишите наборы вариантов покупки максимального количества комплектов мебели, при условии, что производитель М продает мебель упаковками по 6 комплектов в упаковке, а производитель N – по 4 комплекта в упаковке.

Запишите в ответ пары чисел: количество упаковок производителя М далее через пробел количество упаковок производителя N. Каждую пару записывайте с новой строки. Пары должны быть отсортированы по возрастанию значений в первом столбце.

В простейшем варианте можно просто вывести на экран все варианты сочетаний a и b с соответствующими значениями K , в конце программы вывести мак c имальное значение K; затем вручную найти все строки, где значение K равно максимальному.

S0 = 500000 # доступная сумма

cost1 = 18000 # стоимость одного комплекта

packM = 6 # количество комплектов в упаковке M

packN = 4 # количество комплектов в упаковке N

# максимальное значение a

aMax = int(S0 / (packM*cost1))

# поиск максимального K по всем вариантам

for a in range(aMax+1):

Sb = S0 — a*packM*cost1 # сумманазакупкуу N

b = int(Sb / (packN*cost1))

K = packM*a + packN*b # общее количество

maxK = K # новыймаксимум

print(maxK, maxK*cost1)

3. Практическая часть – решение задачи 25.

Изучив базовые навыки работы в языке программирования Python в 8-9 классах, в дальнейшем данный язык стал основным инструментом работы на уроках информатики по теме: «Алгоритмизация и программирование». Мне повезло, я учусь в классе, где информатика является профильной дисциплиной и у меня есть возможность изуить Python углубленно.

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

Я вместе с учителем задалась вопросом, а реально ли ускорить, или оптимизировать быстроту выполнения программы. Тем более, скорее всего для меня эта проблема станет актуальной при сдае КЕГЭ по информатике.

Свой практический эксперимент я проводила над решением задачи 25, а именно обработкой целочисленной информации болших размеров.

Первая задача: Нахождение делителей числа.

В принципе алгоритм несложныйи вполне изучен – это переборный алгоритм с помощью цикла for :

Обратите внимание на число — это 1_000_000_000, так вот при нахождении всех делителей этого числа, программа выполнялась 7 минут. Здесь проблема заключается в том, что чем длинее число, тем дольше время на обработку. То есть здесь прослеживается линейная зависимость О(х), где О – сложность процесса, x – объем данных.

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

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

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

И для закрепления своих рассуждений мною была выполнена задача, взятая из сборников заданий на сайте kpolyakov . spb . ru :

Мои предположения подтвердились, задача выполнена успешна и очень быстро – за доли секунд.

Вторая задача: Простые числа.

Простое число – это целое число, строго больше единицы и имеет всего два делителя 1 и само число, то есть у него нет делителей на промежутке от 2 до целой части от квадратного корня из числа.

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

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

Заключение

Девяносто процентов задач компьютерного ЕГЭ по информатике решается с помощью программирования.

В процессе выполнения работы были решены следующие задачи:

— рассмотрены основы языка программирования Python ;

— выделены типы задач компьютерного ЕГЭ по информатике. Задачи решены средствами языка программирования Python ;

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

Это только начало моей работы. В дальнейшем планирую достаточно подробно заняться самой сложной задачей КЕГЭ по информатике – это задача 27. Где обрабатываются текстовые файлы с большим массивом целых чисел.

Определите наименьшее значение n при котором сумма чисел которые будут выведены при вызове f n

Определите наименьшее значение n при котором сумма чисел 3200000

Информатика 11 класс пробный вариант №9 решу ЕГЭ 2022 задания с ответами

Определите наименьшее натуральное значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 3200000. Запишите в ответе.

Ответы

Задание 16. Вычисление значения рекурсивной функции

Решения задач:

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

Оптимизационные алгоритмы в языке программирования Python в решении задач компьютерного ЕГЭ по информатике

1. Основы языка программирования Python

2. Обзор задач компьютерного ЕГЭ по информатике и их решение на языке Python

3. Практическая часть – решение задачи 25.

Заключение

Добавить комментарий Отменить ответ