27-я егэшная (c4). проверьте, правильно ли написана программа и является ли она как можно более эффективной по времени и по памяти. для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. значение каждого элемента последовательности не превышает 1000. количество элементов последовательности не превышает 10000. напишите программу для решения поставленной , которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности n, т.е. при увеличении n в k раз время работы программы должно увеличиваться не более чем в k раз. программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа n и не превышает 1 килобайта. входные данные представлены следующим образом. в первой строке задаётся число n — общее количество элементов последовательности. гарантируется, что n > 8. в каждой из следующих n строк задаётся одно неотрицательное целое число – очередной элемент последовательности. пример входных данных: 10 100 45 55 245 35 25 10 10 10 26 программа должна вывести одно число — описанное в условии произведение. пример выходных данных для выше примера входных данных: 2600. решение: var n,max,max2,i,a: integer; begin readln(n); max: =8; max2: =0; for i: =1 to n do begin readln(a); if a> max then if max-a> =8 then begin max2: =max; max: =a end else max: =a else if (max-a> =8)and(a> max2) then max2: =a; end; writeln(max*max2); end.

212

379

Посмотреть ответы 2

Ответы на вопрос:

MFINN23

Информатика

4,6(39 оценок)

Программа работает неверно: даже на примере из условия вместо 2600 выводится 55*245 = 13475. в программе происходит что-то странное, например, сравниваются элементы последовательности и 8 (зачем? ) подумаем, как можно было бы решать . - наивный способ: сохранить все числа в массив и пробежаться по нему в двойном цикле, в псевдокоде это выглядит примерно так: max = 0 for i = 1 to n do for j = 1 to n do if |i - j| > = 8 and max < a[i] * a[j] then max = a[i] * a[j] это нехорошо и по времени (время выполнения порядка n^2), и по памяти (количество памяти растет с ростом n пропорционально n). - немного ускоряем: у нас пары i, j и j, i ничем не отличаются, так что будем считать, что j < i. учитывая условие, что |i - j| > = 8, получаем, что j < = i - 8. переписываем: max = 0 for i = 9 to n do for j = 1 to i - 8 do if max < a[i] * a[j] then max = a[i] * a[j] это решение работает в 2 раза быстрее, но этого недостаточно. памяти тоже слишком много. - продолжаем ускорять. пусть i зафиксировано. мы пытаемся сравнить a[i] * a[j] с max для всех j от 1 до i - 8. очевидно, произведение будет максимально, если a[j] - максимум среди a[1], a[2], a[i - 8]. возможное решение: создадим массив из максимумов среди первых k чисел, и будем сравнивать уже с максимумом. maximums[1..n] maximums[1] = a[1] for i = 2 to n do maximums[i] = max(maximums[i - 1], a[i]) max = 0 for i = 9 to n do if max < a[i] * maximums[i - 8] then max = a[i] * maximums[i - 8] это решение уже работает быстро, но остались проблемы с большим расходом памяти. - последний рывок. заметим, что для того, чтобы разобраться с числом под номером i, нам совсем не нужен массив a, а из массива maximums достаточно знать только maximums[i - 8], maximums[i - 1] - 8 чисел. так что большие массивы не нужны, их можно убрать. тогда программа будет эффективна и по времени, и по памяти. у меня максимумы хранятся в массиве maxs[0..7], все номера берутся по модулю 8. в вашей программе это может быть реализовано иначе. pascal: var i, n, t, max: integer; maxs: array[0..7] of integer; begin read(n); read(t); max : = 0; maxs[1] : = t; for i : = 2 to n do begin read(t); if (i > 8) and (max < t * maxs[i mod 8]) then max : = t * maxs[i mod 8]; if t > maxs[(i + 7) mod 8] then maxs[i mod 8] : = t else maxs[i mod 8] : = maxs[(i + 7) mod 8]; end; write(max); end.

sharperdimas

Информатика

4,4(25 оценок)

3 бита

Объяснение:

Есть 8 разных событий.

$8 = 2^{3}$

Для кодирование одного из 8 событий нужно 3 бита, поэтому событие несёт в себе 3 бита информации.

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Информатика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

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