Анализ сигналов из Космоса. Задача 27

Содержание

1. Постановка задачи
2. Комментарии
3. Алгоритм А и его программная реализация
4. Алгоритм Б и его программная реализация

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

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны.
Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен).
Необходимо определить количество таких пар, для которых произведение элементов делится на 29.

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

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

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

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

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

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000).В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.
Пример входных данных:
7
58
2
3
5
4
1
29
Пример выходных данных для приведённого выше примера входных данных:
5

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

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

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

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

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

3. Алгоритм А и его программная реализация

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

2. Находим номера элементов, делящихся нацело на 29, заносим их (номера) в новый массив mak[ ] .Подсчет пар  показаний, между моментами передачи которых прошло не менее 4 минут, выполняем с учетом  временного лага (запаздывание).

3. Подсчет числа пар назад и вперед. При этом, чтобы не было двойного счета

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

using System;
using System.IO;
namespace Задача_27_1__массив
{
   class Program
   {
      static void Main(string[] args)
      {
        int N, k = 0, s = 0;
        string data = "data.txt"; // имя файла исходных данных
        StreamReader sr = new StreamReader(data);
        // число сигналов
        N = Convert.ToInt32(sr.ReadLine());
        // массив сигналов
        int[] mas = new int[N];
        // массив номеросигналов, кратных 29
        int[] mak = new int[N];
        // считывание данных
        for (int i = 0; i < N; i++)
           mas[i] = Convert.ToInt32(sr.ReadLine());
        // цикл выборки номеров сигналов
        for (int i = 0; i < N; i++)
        {
           if (mas[i] % 29 == 0)
           {
             mak[s] = i;
             s++;
           }
       }
       подсчет пар 
       if (s > 0)
       {
         for (int j = 0; j < s; j++)
         {
           if (mak[j] > 3)
              k = k + mak[j] - 3;
           if ((N - mak[j] - 4) > 0)
              k = k + (N - 4 - mak[j]);
           k = k - del(mak, j);
         }
       }
       else
          k = 0;
       // результат
       Console.WriteLine(k);
       Console.ReadKey();
    }
    // для удаления близких пар
     static int del(int [] mak, int j)
    {
       int p = 0;
       for (int q = 0; q < j; q++)
          if ((mak[j] - mak[q]) > 3)
             p++;
       return p;
    }
  }
}

3. Алгоритм Б и его программная реализация

Массив для хранения всех сигналов не объявляется. Если новое число кратно 29, то оно образует пару со всеми будушими числами, исключающими близлежащие, а также с предшествующими за вычетом близлежащих (номера в массиве m[ ]).

Программа:

using System;
using System.IO;
namespace Задача_27_1_
{
class Program
{
   static void Main(string[] args)
   {
   int N; // число элементов
   int k; // номер точки
   int r = 0; // число пар (ответ)
   int a; // текущий сигнал 
   int q=0; // кол-во кратных нарастанием
   int p = 0; // вспомогательная
   int[] m = new int[4]; // массив номеров
   int n_m = 0; // число элементов в m[4] 
   string data = "data.txt"; // исх.данные
   StreamReader sr = new StreamReader(data);
   N = Convert.ToInt32(sr.ReadLine());
   k = 0;
   while (! sr.EndOfStream)
   {
      a = Convert.ToInt32(sr.ReadLine());
      if (a % 29 == 0)
      {
         p = N - (k + 4);
         if (p > 0)
            r = r + p;
         p = k - 3;
        if (p > 0)
        r = r + p;
        r = r - q + povt(k, m, n_m);
        q++;
        sdvig4(k, m, ref n_m);
     }
     k++;
     Console.WriteLine("Число {0}", r); // пром печать
  }
  Console.WriteLine("Число пар = {0}", r);
  Console.ReadKey();
}
// заполнение или сдвиг/заполнение, изменяет n !
private static void sdvig4( int k, int [] m, ref int n) 
{
   const int g=4;
   if (n<g)
   {
      m[n] = k;
      n++;
   }
   else
   {
      for (int j = 0; j < g - 1; j++)
         m[j] = m[j + 1];
      m[g - 1] = k;
   }
}
// отнять повторы назад на расстояниях < 4
   private static int povt(int k, int[] m, int n)
   {
      int h = 0;
      for (int j = 0; j < n; j++)
         if (k - m[j] < 4)
      h++;
      return h;
   }
 }
}

Исседуйте программу для различных наборов данных.

Оставьте комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *