Гравитационное поле Земли. Задача 27

Содержание

1. Постановка задачи
2. Комментарии
3. Алгоритмы решения
4. Программная реализация
5. Помощь школьнику и преподавателю

1. Постановка задачи

(дословное воспроизведение задания)

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли.
По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2019».
Количество передаваемых чисел в серии известно и не превышает 10 000.
Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.

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

Задание А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве,
после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А – 2 балла.

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

Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.

НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора.
Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.
Пример входных данных:
11
12
45
5
3
17
23
21
20
19
18
17
Программа должна вывести одно число — описанное в условии произведение либо –1, если получить такое произведение не удаётся.
Пример выходных данных для приведённого выше примера входных данных:
54

2. Комментарии

1. По опыту подготовки школьников к сдаче Единого государственного экзамена (ЕГЭ) по информатике и ИВТ реальные трудности содержатся в последней задаче с номером 27. Причем решение задания А программирующий школьник записывает в несколько операторов, а вот задание Б (за которое можно получить первичные 4 балла, а фактически 8) вызывает определенные трудности. С учетом стрессовой ситуации на экзамене это задание часто остается без решения.

2. Первое обсуждаемое понятие,  это эффективность программы по времени. На примере задач Линейного и бинарного поиска и Сортировки оцениваем число операций сравнения, когда число элементов массива N > 1000000000. Второе понятие — эффективность по памяти с разбором примеров, когда данные можно обрабатывать в темпе с процессом их поступления,  не используя их накопление в массиве.

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

4. Важно помнить, что получения правильного ответа в тесте, приведенном в качестве примера, не гарантирует правильности программы. При проверке может быть использован широкий набор тестов (как на международной студенческой олимпиаде по программированию ACM/ICPC), так и ручной просмотр текста и анализ логики программы (чаще всего, к сожалению).

5. Решение задания начинаем с имитации последовательного ввода данных, считываемых из файла. Далее решаем задание А, после чего переходим к заданию Б. Уделяем внимание типу поступающих данных (целое положительное число), количеству данных, результату — минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут.

6. При подготовке к ЕГЭ необходимо запрограммировать оба алгоритма — А и Б. Алгоритм А основан на полном переборе, более прост, и его результаты мы используем для тестирования алгоритма Б (до полного совпадения результатов). С точки зрения получаемых баллов (за вариант А — 2 балла, за вариант Б — до 4-х, берется максимум из двух) ошибки в варианте Б могут результат обнулить, но решенный правильно вариант А гарантирует минимум 2 балла.

3. Алгоритмы решения

1. Имитация ввода данных. Считаем, что исходные данные хранятся в текстовом файле: одно число — одна строка, причем первое число — количество переданных показаний. Фактически часто это количество данных в серии неизвестно, но тем не менее это число считывается из файла первым. Имя файла может быть жестко зафиксировано. Пример работы с текстовыми файлами приведен в статье  Чтение и запись текстовых файлов. Данные заносим в одномерный массив, индекс элемента которого соответствует времени ежеминутного поступления сигнала (начальное время t = 0), а значение которого и есть сам сигнал.

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

3. После вывода результата  — значение произведения или признака его отсутствия (-1) решение задания А завершено. Оформляем его в методе Main().

4. Для демонстрации решения задания Б создадим дугой метод Main2( ), в котором запишем решение задания Б. Понятно, что по критерию «эффективности по памяти» создавать массив из N чисел нельзя, поэтому будем создавать в темпе с процессом два массива ArC и ArN (с четными и нечетными значения сигналов соответственно), хранящих экземпляры структуры zam:

public struct zam
{
   public int q;  // время поступления сигнала
   public int a;  // значение сигнала
}

Максимальная размерность этих массивов — 7, так как по условию задачи требуется искать такую пару сигналов, лаг между которыми не менее 6. В эти массивы ArC[7] и ArN[7] будем заносить четные и нечетные значения сигналов (поле a) вместе со временем поступления (поле q). Напомним, что время, измеряемое в минутах, можно также задавать целым числом: 0, 1, 2…. . Очевидно, что для размещения этих массивов 1 кбайта памяти будет более чем достаточно (нужно всего 56 байт).
В процессе поступления сигналов мы будем в каждый из массивов заносить только такое значение, которое меньше уже имеющегося в массиве максимального значения сигнала, и каждый раз при необходимости упорядочения данных в массивах ArC и ArN будем запускать сортировку по возрастанию  поля a.

После завершения серии мы получим три возможных варианта (по условию задачи число сигналов не менее 7):
1) в массиве ArC нет ни одного реального сигнала. Это будет означать, что требуемая пара не найдена (гравитационная волна не поймана). Ожидаемый ответ: -1.
2) число зафиксированных сигналов в массиве ArC равно 1. Тогда может быть найдена пара сигналов, удовлетворяющих заданному условию (нечетный элемент — ArN[j].q, j=0.1.2….6).
3) Если сигналов в массиве ArC более одного, то они могут коррелировать с  сигналами из массива ArN.

5. Решением задачи также является число: значение искомой пары либо -1.

4. Программная реализация

Файл Program.cs:

// ЕГЭ по информатике 2019 Задача 27
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading.Tasks;
namespace Cosmos27
{
class Program
{
// вариант А
   static void Main(string[] args)
   {
      string data = "data.txt";
      StreamReader sr = new StreamReader(data);
      int n = Convert.ToInt32(sr.ReadLine());
      Console.WriteLine(" -- {0} ", n);
      int[] a = new int[n];
      int k = 0;
      int b = 0;
      while (!sr.EndOfStream)
      {
         b = Convert.ToInt32(sr.ReadLine());
         Console.WriteLine(b);
         a[k] = b;
         k++;
      }
      // поиск пары в цикле
      int minp = 1000001;
      int p = 0;
      for (int i = 0; i < n - 6; i++)
         for (int j = i + 6; j < n; j++)
         {
            p = a[i] * a[j];
            if ((p % 2 == 0) && (p < minp))
            minp = p;
         }
      if (minp < 1000001)
        Console.WriteLine("минимальное произведение A = {0}", minp);
      else
         Console.WriteLine("минимальное произведение A = -1");
      // Вызов варианта В из варианта А
      Main2(); 
   }
   // Вариант Б, без цикла
   static void Main2()
   {
      string data = "data.txt";
      StreamReader sr = new StreamReader(data);
      int n = Convert.ToInt32(sr.ReadLine());
      // Вспомогательные массивы минимальных четных и нечетных чисел
      zam[] ArC = new zam[7];
      zam[] ArN = new zam[7];
      for (int i=0; i<7; i++)
      {
         ArC[i].a = 1001;
         ArN[i].a = 1001;
      }
      int kc = 0; // кол-во четных чисел
      int kn = 0; // кол-во нечетных чисел
      int k = 0; // общее кол-во сигналов нарастающим итогом
      int b = 0; // очередной сигнал 
      int minp = 1000001; // для старта
      while (!sr.EndOfStream) // поступление N сигналов
      {
         b = Convert.ToInt32(sr.ReadLine()); // прием сигнала
         if (b % 2 == 0) // делим на четные и нечетные числа
         {
            if (kc < 6) // первые шесть четных чисел
            {
               ArC[kc].q = k;
               ArC[kc].a = b;
               Sort7(ArC); // сортировка по возрастанию
               kc++;
           }
           else // последующие числа
           {
              if (ArC[6].a > b)
              {
                ArC[6].q = k;
                ArC[6].a = b;
                Sort7(ArC);
              }
           } 
         }
         else
         {
            if (kn < 6) // первые шесть нечетных чисел
            {
               ArN[kn].q = k;
               ArN[kn].a = b;
               Sort7(ArN);
               kn++;
            }
            else // последующие числа
            {
               if (ArN[6].a > b)
               {
                  ArN[6].q = k;
                  ArN[6].a = b;
                  Sort7(ArN);
               }
            }
         }
         k++; // текущее количество полученных сигналов
         // Нахождение минимальной пары
         for (int i = 0; i < 6; i++)
            for (int j = i + 1; j < 7; j++)
               if ((ArC[i].a * ArC[j].a < minp) && (Math.Abs(ArC[i].q - ArC[j].q) > 5))
                  minp = ArC[i].a * ArC[j].a;
               for (int i = 0; i < 7; i++)
               for (int j = 0; j < 7; j++)
                  if ((ArC[i].a%2==0)&&(ArC[i].a * ArN[j].a < minp) && (Math.Abs(ArC[i].q - ArN[j].q) > 5))
                     minp = ArC[i].a * ArN[j].a;
      } // конец поступления сигналов
      // Результат
         if (minp < 1000001)
            Console.WriteLine("минимальное произведение Б = {0}", minp);
         else
            Console.WriteLine("минимальное произведение Б = -1");
         Console.ReadKey();
      } // end метода Main2 - Вариант Б

      // структура для варианта Б
      public struct zam
      {
         public int q;
         public int a;
      } 
      // Сортировка для варианта Б
      static void Sort7(zam [] z)
      {
         zam p;
         for (int i =6; i>0; i--)
           for (int j=0; j<i; j++)
             if (z[j].a > z[j+1].a)
             {
                p = z[j];
                z[j] = z[j + 1];
                z[j + 1] = p;
             }
      }
   }
}

Результат:

5. Помощь школьнику и преподавателю

Консультирую по всем задачам ЕГЭ по скайпу, пишите комментарии к статье, обращайтесь лично в почту сайта.

---

NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.

---

Помощь проекту: