Системный администратор раз в неделю создает архив пользовательских файлов однако объем диска
Задание 16 № 5213
Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(n) = 3*F(n−1) − 2*F(n−2) при n >2.
Чему равно значение функции F(7)? В ответе запишите только натуральное число.
Таким образом, ответ F(7) = 128.
Задание 16 № 4653
Последовательность чисел Люка задается рекуррентным соотношением:
F(n) = F(n–2) + F(n–1), при n >2, где n – натуральное число.
Чему равно десятое число в последовательности Люка?
В ответе запишите только натуральное число.
F(10) = F(8) + F(9) = 76.
Десятое число в последовательности Люка равно 76.
Задание 16 № 5057
Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(n) = 5*F(n-1) − 4*F(n−2) при n >2.
Чему равно значение функции F(15)? В ответе запишите только натуральное число.
Заметим, что значение функции F(n) равно 3 при любом n, следовательно, F(15) = 3.
Таким образом, ответ 3.
Задание 16 № 5089
Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(n) = 5*F(n − 1) − 4*F(n − 2) при n >2.
Чему равно значение функции F(13)? В ответе запишите только натуральное число.
Таким образом, ответ 5.
Задание 16 № 16386
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(1). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Первым действием процедура F(1) вызовет процедуру F(4), которая вызовет процедуру F(7). Процедура F(7) выведет на экран число 7. Следующим шагом своего алгоритма процедура F(4) выведет на экран число 4.
Следующим шагом своего алгоритма процедура F(1) выведет на экран число 1, после чего будет вызвана процедура F(2), которая вызовет процедуру F(5). После этого процедура F(5) выведет на экран число 5. Далее процедура F(2) следующим шагом своего алгоритма выведет на экран число 2 и вызовет процедуру F(4). Процедура F(4) вызовет процедуру F(7). Процедура F(7) выведет на экран число 7. Следующим шагом своего алгоритма процедура F(4) выведет на экран число 4.
Задание 16 № 16440
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(1). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Первым действием процедура F(1) вызовет процедуру F(2), которая вызовет процедуру F(4). Процедура F(4) выведет на экран число 4. Следующим шагом своего алгоритма процедура F(4) вызовет процедуру F(7), которая выведет на экран число 7. После этого процедура F(2) выведет на экран число 2 и вызовет процедуру F(5), которая выведет на экран число 5.
Следующим шагом своего алгоритма процедура F(1) выведет на экран число 1 и вызовет процедуру F(4). Далее процедура F(4) выведет на экран число 4 и вызовет процедуру F(7), которая выведет на экран число 7.
Задание 16 № 17329
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(1). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Первым действием процедура F(1) вызовет процедуру F(4), которая вызовет процедуру F(7). Процедура F(7) выведет на экран 7. Далее процедура F(4) следующим шагом своего алгоритма выведет на экран 4.
Далее процедура F(1) следующим шагом своего алгоритма выведет на экран 1 и вызовет процедуру F(3), которая вызовет процедуру F(6), которая вызовет процедуру F(9), после чего на экран будет выведено число 9. После этого процедура F(6) выведет на экран число 6. Далее процедура F(3) следующим шагом своего алгоритма выведет на экран 3 и вызовет процедуру F(9), которая выведет на экран число 9.
Задание 16 № 18559
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(1). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Первым действием процедура F(1) выведет на экран число 1, после этого будет вызвана процедура F(4), которая выведет на экран число 4 и вызовет процедуры F(7) и F(8), которые выведут на экран числа 7 и 8 соответственно. Следующим шагом своего алгоритма процедура F(1) вызовет процедуру F(2), которая выведет на экран число 2 и вызовет процедуру F(5), которая выведет на экран число 5. После этого процедура F(2) следующим шагом своего алгоритма вызовет процедуру F(4), которая выведет на экран число 4 и вызовет процедуры F(7) и F(8), которые выведут на экран числа 7 и 8 соответственно.
Задание 16 № 18587
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(1). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Первым действием процедура F(1) выведет на экран число 1, после этого будет вызвана процедура F(2), которая выведет на экран число 2 и вызове процедуру F(4). Она выведет на экран число 4 и вызовет процедуру F(8), которая выведет на экран число 8. После этого процедура F(4) вызовет процедуру F(7) и на экран будет выведено число 7. После этого процедура F(2) следующим шагом своего алгоритма вызовет процедуру F(5), которая выведет на экран число 5.
Далее процедура F(1) следующим шагом своего алгоритма вызовет процедуру F(4), которая выведет на экран число 4 и вызовет процедуру F(8), после чего не экран будет выведено число 8. После этого процедура F(4) вызовет процедуру F(7), которая выведет на экран число 7.
SkillPro | школа программирования запись закреплена
Разбор задачи №26 ЕГЭ по информатике 2021 года:
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 3000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
2 50
Алгоритм:
1.Открываем файл
2.Считываем первую строку для того, чтобы узнать размер свободного места на диске и количество пользователей
3.Считываем в список все данные пользователей
4.Сортируем данные по возрастанию, чтобы в начале находились пользователи с наименьшим объёмом файла для хранения данных наибольшего количества пользователей
5.Добавляем объемы файлов в переменную для нахождения общего объема до тех пор, пока есть свободное место, одновременно с этим при добавлении данных пользователя увеличиваем количество пользователей на 1.
6.Если занятое место равняется максимально свободному месту на диске, то выводим количество пользователей и объём последнего добавленного файла.
7.Если еще имеется место для добавления данных, то вычитаем из общего объема последний файла и начиная с самого крупного объёма начинаем перебирать информацию и пробуем её добавить к занятому месту, если умещается, то добавляем и заканчиваем перебор.
Выводим количество пользователей и найденный объём файла.
Программа на языке Python:
f = open('27883.txt')
startData = f.readline()
spacePosition = startData.index(' ')
freeSpace = startData[:spacePosition]
numberOfUsers = startData[spacePosition+1
dataUsers = []
for data in range(0, int(numberOfUsers)):
dataUsers.append(int(f.readline()))
memoryOccupied=0
countUsers=0
for i in range(0, len(dataUsers)):
if memoryOccupied+dataUsers[i] memoryOccupied = memoryOccupied+dataUsers[i]
countUsers=countUsers+1
else:
break
if memoryOccupied==int(freeSpace):
print(countUsers, dataUsers[countUsers-1])
else:
maxMemory=0
memoryOccupied = memoryOccupied-dataUsers[countUsers-1]
for i in range(len(dataUsers)-1, countUsers-1, -1):
if memoryOccupied+dataUsers[i] maxMemory = dataUsers[i]
break
print(countUsers, maxMemory)
Информатика XXII век запись закреплена
Разбираем задание 26 ЕГЭ по информатике.
Задача 1. Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также
максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не
превышающее 1000).
В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Подсказка. Задачка на первый взгляд проста - нужно банально упорядочить список пользователей по размеру файлов, и
потом попробовать набрать нужную сумму.
Но таким образом мы получим правильно только число пользователей.
Скорее всего, будет так: сумма файлов пользователей будет несколько меньше свободного места. Это означает, что в список "спасённых" можно включить вместо последего пользователя по упорядоченному списку одного из следующих за ним, с бо́льшим размером файла. Таким образом, место в архиве будет использовано рациональнее.
Сегодняшний урок посвящён 26 заданию из ЕГЭ по информатике 2021. На нём мы будем тренировать умение обрабатывать целочисленную информацию с использованием сортировки.
Сортировка - это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.
Приступим к практике 26 задания из ЕГЭ по информатике.
Задача (Демонстрационный вариант, 2021)
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 | 4 |
80 | |
30 | |
50 | |
40 |
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
Напишем решение на Pascal ABC.
Каждое значение, которое показывает размер файла, сохраним в массиве.
Количество файлов можно посмотреть в самом файле к задаче. Это второе число в первой строчке. В нашей случае это число 970.
Затем отсортируем массив по возрастанию с помощью метода Пузырька. По данному методу есть статья на моём сайте.
Суммарный размер файлов не должен превышать значения 8200 (первое число в первой строчке). Нам нужно понять, а сколько максимум файлов можно сохранить. Т.к. после сортировки у нас в начале массива числа самые маленькие, то мы начинаем их суммировать в переменную sum, проверяя, чтобы значение этой переменной не превышало 8200. Так мы в переменной count получим максимальное количество файлов, которое можно уместить на диске.
Нам нужно написать так же написать в ответе максимальный размер файла при максимальном количестве файлов, который можно сохранить. Это не значит, что мы должны искать максимальный размер только среди тех чисел, которые участвовали, когда мы подсчитывали максимальное количество файлов. Возможно, найдётся один файл такой, при котором, количество будет такое же, но сам размер файла будет больше, чем те, которые мы рассматривали.
Чтобы найти максимальный размер файла проходим массив уже с наибольших чисел. Если количество файлов будет таким же, как и с исследуемым файлом, то мы нашли то что нужно.
(№ 2639) (А.М. Кабанов) Спутник «Фотон» проводит измерения солнечной активности, результат каждого измерения представляет собой натуральное число. Перед обработкой серии измерений из неё исключают K наибольших и K наименьших значений (как недостоверные). По заданной информации о значении каждого из измерений, а также количестве исключаемых значений, определите наибольшее достоверное измерение, а также целую часть среднего значения всех достоверных измерений.
Продолжаем анализ демонстрационного варианта ЕГЭ по информатике 2022.
В этой статье разберём с 22-ого по 27 задание.
ЕГЭ по информатике 2022 будет повержено!
Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 4, а потом 5.
Решение данного задания будет похоже на решение 6 задания из ЕГЭ по информатике 2022.
С помощью перебора на языке Python найдём при каких значениях переменная L=4 И переменная M=5 в конце программы.
Наибольшее значение равно 49.
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Решим задачу c помощью шаблона на языке Python.
Число x, это то число, с которым мы работаем. Число y - это куда нужно прийти.
Если число x достигло пункта назначения, то возвращаем 1. Если оно перескочило y, то возвращаем 0. А если ещё не дошло до y, то продолжаем вычисления с помощью рекурсии.
У нас число 10 обязательное, поэтому разбиваем функцию следующим образом F(1, 10)*F(10, 20), через умножение. Это и будет ответ. Получается 28.
Текстовый файл состоит из символов P, Q, R и S.
Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет идущих подряд символов P. Для выполнения этого задания следует написать программу.
Напишем решение на языке Python.
Подсчитываем символы, пока не встретилась комбинация двух P подряд. Как только встретилась данная комбинация, сбрасываем счётчик на 1. Здесь мы сбрасываем счётчик на значение 1, чтобы учесть один символ, которые находится в самой комбинации PP. И в начале мы тоже устанавливаем счётчик в значение 1 по этой же причине.
Мы проходим в цикле for до длины строки минус один. Значение 1 в счётчике при сбросе и в начале программы так же компенсирует и тот момент, что мы не подсчитываем последний символ!
При изменении счётчика, сохраняем максимальное значение в переменной mx
Если бы у нас была вместо PP другая комбинация, состоящая к примеру из 5 символов, то мы бы тогда в начале и при сбросе писали в счётчик значение 5-1=4.
В этой задаче получается ответ 188.
Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 700 000, в порядке возрастания и ищет среди них такие, для которых значение M оканчивается на 8. Выведите первые пять найденных чисел и соответствующие им значения M.
Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем – значение М. Строки выводятся в порядке возрастания найденных чисел.
Количество строк в таблице для ответа избыточно.
На ЕГЭ по информатике 2022 удобно писать программы на языке Python.
В данной программе перебираются числа в цикле for, начиная с 700001.
Переменная b-считается наибольшим делителем числа i. Затем, с помощью ещё одного цикла for перебираются числа с 2 до корня числа i (включительно). Ищем тем самым наименьший делитель.
Если до корня числа включительно не встретился ни один делитель, значит, у числа нет делителей, кроме 1 и самого числа.
Пусть у нас есть число A. Если у этого числа есть делитель d1, то он находится до корня этого числа. А вот то число (так же делитель), на которое умножается это число d1, чтобы получить A, будет находиться после корня A.
Получается, что у каждого делителя есть своя пара. У единицы - это само число. Причём один делитель из пары находится до корня, другой после корня. Исключением будет тот случай, когда из числа А извлекается целый корень. Тогда для этого корня не будет пары (парой и будет само это число √A * √A = A).
Таким образом, первый найденный делитель будет являться наименьшим делителем. А вот делительный, который находится в паре с наименьшим делителем, будет наибольшим.
После того, как мы нашли наименьший делитель (он будет сидеть в переменной j) и наибольший делитель b, выходим из второго цикла for.
Если переменная b осталась равна нулю, то, значит, у числа i нет указанных делителей, и переменная M должна равняться 0. Если b не равна нулю, то M=j+b.
Проверить, на что оканчивается число, можно узнав остаток от деления числа на 10.
Переменная count следит, чтобы было распечатано ровно 5 чисел, которые удовлетворяют условию задачи.
Ответ:
700005 | 233338 |
700007 | 100008 |
700012 | 350008 |
700015 | 140008 |
700031 | 24168 |
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое – в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем – максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов – 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
Решим задачу с помощью Excel. Чтобы открыть текстовый файл в программе Excel, выбираем Файл->Открыть, выбираем нужную папку и указываем, чтобы в папке были видны все типы файлов.
И выбираем наш текстовый файл.
Выскочит окно Мастер текстов (импорт). Здесь оставляем выбранный пункт с разделителями и кликаем Далее.
В следующем окне поставим ещё галочку пробел. В итоге Символами-разделителем будут знак табуляции и пробел.
Кликаем ещё раз Далее и Готово.
Наши данные вставятся, как нужно!
Число 8200 (размер свободного места) нужно запомнить или записать на черновике. Число 970 (количество файлов) нам в принципе не нужно при таком подходе решения.
Теперь удаляем первую строчку. Выделяем две ячейки в первой строчке, через контекстное меню мыши нажимаем Удалить. . Выбираем ячейки, со сдвигом вверх.
1. Найдём максимальное количество файлов.
Выделяем весь столбец A и сортируем его по возрастанию.
Теперь выделяем ячейки сверху мышкой, а справа в нижней части программы будет показываться сумма выделенных ячеек.
Мы должны выделить максимальное количество ячеек, но чтобы сумма не превышала число 8200.
Получается максимальное количество файлов, которое можно сохранить, равно 568.
2. Найдём максимальный размер файла при максимальном количестве файлов.
Если мы сохраним максимальное количество файлов, то у нас ещё останется свободное место 8200-8176=24, т.к. сумма выделенных ячеек равна 8176.
Мы можем заменить наибольший файл (последняя выделенная ячейка равная 29) ещё большим файлом, размер которого не превышает 24+29=53.
Если покрутим таблицу вниз, то найдём такой файл размером 50. Это и будет наибольший файл при максимальном количестве файлов.
Ответ:
568 | 50 |
Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем – для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Напишем программу на Python.
Переменная s - это сумма от первого до текущего элемента i. На каждом шаге вычисляется остаток от деления s на 43. И записывается в массив sum_ost эта сумма s для каждого остатка.
Тогда кандидатом для ответа будет цепочка, которая получается, если от цепочки с суммой s "отрезать" цепочку с суммой из массив sum_ost, которая соответствует текущему остатку (переменная ost).
В массив sum_ost для каждого остатка записывается сумма только один раз, т.к. нам нужна именно минимальная сумма для каждого остатка, чтобы кандидат для ответа был как можно больше.
В начале массив sum_ost инициализируется очень большим числом 1096594666. Это число больше, чем сумма всех элементов в файле. Оно было найдено до основного решения, с помощью простой программы.
В процессе решения мы ищем среди кандидатов для ответа цепочку с максимальной суммой. Делаем это стандартным образом: кто больше, то и победил. Мы инициализируем большими числом 1096594666 элементы массива sum_ost для того, чтобы условие нормально сработало, когда в массиве sum_ost ещё нет суммы для данного остатка.
Так же мы сохраняем индексы элементов в массив k, когда записываем суммы для различных остатков в массив sum_ost. Это делается для того, чтобы можно было вычислить длину цепочки.
Для случая, когда остаток равен 0, устанавливаем сумму в массиве sum_ost равной нулю, потому что кандидатом на ответ будет цепочка от самого первого до i-ого элемента. Это, можно сказать, исключительный случай. И чтобы правильно вычислялась длина цепочки, для случая, когда остаток равен нулю, индекс в массив k делаем равным -1.
Читайте также: