СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


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

На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое множество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является максимальным среди всех возможных множеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то основным считается то, которое содержит наибольшее количество элементов.

 

Вам предлагается написать программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.

 

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

 

Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.

Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.

 

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

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

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

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

Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

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

 

 

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

 

5

 

123

2

 

-1000

 

0

 

10

 

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

Пример выходных данных для приведённого выше примера входных данных:

 

1 2 5

Решение.

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

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

Ниже приведены примеры решения задания на языках Паскаль и Бейсик.

Допускаются решения, записанные на других языках программирования.

 

Пример правильной и эффективной программы на языке Паскаль

var n, i, j, k, c, min, a: longint;

begin

readln(n);

min := -1000000001;

k := 0;

j := 0;

c := 0;

for i := 1 to n do

begin

readln(a);

if a = 0 then j := i;

if a < 0 then

begin

c := c + 1;

if a > min then

begin

min := a;

k := i;

end

end

end;

for i := 1 to n do

if (i <> j) and ((c mod 2 = 0 ) or (i <> k)) then

write(i, ' ');

end.

 

Пример правильной и эффективной программы на языке Бейсик

 

INPUT n

min = 0

k = 0

j = 0

c = 0

FOR i = 1 TO n

INPUT a

IF a = 0 THEN j = i

IF a < 0 THEN

c = c +1

IF (min = 0) OR (a > min) THEN

min = a

k = i

END IF

END IF

NEXT i

FOR i = 1 TO n

IF (i <> j) AND ((C MOD 2 = 0) OR (i <> k)) THEN PRINT i

NEXT i

END

 

Пример правильной и эффективной программы на языке C++.

#include <iostream>

using namespace std;

int main (){

int N = 0;

cin >> N;

long min = -1000000001;

int j = 0, k = 0, c = 0;

for (int i = 1; i <= N; ++i)

{

int num;

cin >> num;

if (num == 0)

j = i;

if (num < 0)

{

c += 1;

if (min < num)

{

min = num;

k = i;

}

}

}

for (int i = 1; i <= N; ++i)

{

if (i != j && (c % 2 == 0 || i != k))

cout << i << ' ';

}

return 0;

}

 

Пример решения задачи А на языке Паскаль.

var

a: array[1..10000] of integer; {исходные данные}

N: integer; {количество чисел}

neg: integer; {количество отрицательных чисел}

maxneg: integer; {наибольшее отрицательное число}

i: integer;

begin

readln(N);

neg := 0;

maxneg := -1000000001;

for i := 1 to N do readln(a[i]);

for i := 1 to N do begin

if a[i]<0 then neg := neg + 1;

if (a[i]<0) and (a[i]>maxneg) then maxneg := a[i];

end;

if neg mod 2 <> 0 then

for i := 1 to N do

if (a[i]<>0) and (a[i]<>maxneg) then write(i, ' ');

if neg mod 2 = 0 then

for i := 1 to N do

if (a[i]<>0) then write(i, ' ');

end.


Аналоги к заданию № 5375: 5407 5439 5535 5567 Все

Источник: ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Дальний Восток. Ва­ри­ант 1.