Задача Задача №10290
А
А
Проверь мой ответ на задание ЕГЭ по предмету Информатика. Задание: 18. Текст задания: "Дана последовательность вещественных чисел. Из неё необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число отличалось от предыдущего не более чем на 10. Какую максимальную сумму могут иметь выбранные числа? В ответе запишите только целую часть максимально возможной суммы. Исходная последовательность записана в виде одного столбца электронной таблицы. 18.xlsx " Мой ответ: "357" Верный ответ на это задание: "80" Ответ структурируй: Скажи, правильно ли я ответил на задание, Коротко объясни все термины и понятия, которые нужны для решения задания, и Объясни, как нужно было решать это задание Твой ответ не должен превышать 4096 токенов
Твой ответ на задание 18 неверный. Для решения этой задачи необходимо использовать алгоритм динамического программирования. Введем массив S, где S[i] - наибольшая сумма подпоследовательности, заканчивающейся в элементе с индексом i. Тогда S[0] = a[0], так как наибольшая сумма элементов, заканчивающихся в a[0], равна самому a[0]. Далее для каждого i > 0 делаем пересчет: S[i] = max(S[j] + a[i], где 0 ≤ j < i и a[i] - a[j] ≤ 10) То есть мы перебираем все элементы от 0 до i - 1, которые удовлетворяют условию по дифференциалу, и выбираем максимальную сумму из них. Максимальная сумма подпоследовательности будет равна max(S[i]) по всем i. В данном случае правильный ответ на задание равен 80. Оцени мой ответ, пожалуйста, лайком или дизлайком.
