Вариант 8. Онлайн тесты ЕГЭ Информатика (Вопрос №27)

Информатика (Вариант 8)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Вопрос 27

Радиотелескоп пытается получать и анализировать сигналы, поступающие из различных участков космоса, при этом различные шумы переводятся в последовательность целых неотрицательных чисел. Чисел может быть очень много, но не может быть меньше трёх. Все числа различны. Хотя бы одно из чисел нечётно.

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

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

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

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

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

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

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

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

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

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

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

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

123

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

Ответ

Ответить Завершить тест Пояснение

Заметили ошибку в тексте?
Выделите её и нажмите Ctrl + Enter

Основное подмножество состоит из всех значений сигналов, кроме 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 mod 2 <> 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 MOD 2 <> 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

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

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

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 mod 2 <> 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 MOD 2 <> 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

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

var
  a: array[1..10000] of integer; {исходные данные}
  min: integer; {минимальное нечётное число}
  N: integer; {количество чисел}
  sum: integer; {максимальная сумма}
  i: integer;
begin
  readln(N);
  min := 1000000001;
  sum := 0;
  for i := 1 to N do readln(a[i]);
  for i := 1 to N do begin
    sum := sum + a[i];
    if (a[i] mod 2 <> 0) and (a[i]<min) then<p="">      min := a[i];
    end;
  if sum mod 2 = 0 then
    for i := 1 to N do
      if (a[i] <> min) and (a[i]<>0) then write(i, ' ');
  if sum mod 2 <> 0 then
    for i := 1 to N do
      if (a[i]<>0) then write(i, ' ');
end.

Пример правильной и эффективной программы на языке Паскаль:	Пример правильной и эффективной программы на языке Бейсик:
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 mod 2 <> 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 MOD 2 <> 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

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

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

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 mod 2 <> 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 MOD 2 <> 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

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

var
  a: array[1..10000] of integer; {исходные данные}
  min: integer; {минимальное нечётное число}
  N: integer; {количество чисел}
  sum: integer; {максимальная сумма}
  i: integer;
begin
  readln(N);
  min := 1000000001;
  sum := 0;
  for i := 1 to N do readln(a[i]);
  for i := 1 to N do begin
    sum := sum + a[i];
    if (a[i] mod 2 <> 0) and (a[i]<min) then<p="">      min := a[i];
    end;
  if sum mod 2 = 0 then
    for i := 1 to N do
      if (a[i] <> min) and (a[i]<>0) then write(i, ' ');
  if sum mod 2 <> 0 then
    for i := 1 to N do
      if (a[i]<>0) then write(i, ' ');
end.

Регистрация

Зарегистрироваться через VK

Личный кабинет

Войти через VK

Информатика (Вариант 8)

Ответ

Регистрация

Email

Фамилия

Имя Отчество

Пароль

Повторите пароль

Телефон

Личный кабинет

Email или телефон

Пароль (Забыли?)