среда, 8 ноября 2017 г.

Вектор и ассоциативный массив при решении заданий 27 ЕГЭ

Задача взята из сборника задач на сайте kpolyakov.spb.ru под №72.

(Д.Ф. Муфаззалов) Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять, какое значение А встречалось чаще всего. Если несколько значений А встречалось одинаковое наибольшее количество раз, вывести их в порядке убывания.

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

Входные данные:
На вход программе в первой строке подаётся количество пар N (1 <= N <= 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000.

Пример входных данных:
6
1 3
5 15
6 9
5 4
3 3
36 40 
 
Пример выходных данных для приведённого примера входных данных:
3 1

Решение:
Итак, необходимо минимизировать время и память.
Будем сразу искать НОД введенных чисел и считать их количество. Для этого будем использовать тип "множество" или "ассоциативный массив" или "словарь" (map), где будем накапливать количество встречаемых чисел НОД. Конечно, если таких значений будет по одному, то по памяти мы не сэкономим.
Далее применим алгоритм поиска  наибольшего значения (second) и вывода всех индексов (first) с этим значением. Вот пример кода с использованием обычного статического массива:

int k=0, a=0, A[n],C[1001];
for(i=0;i<n;i++)
{
  if(A[i]>a)
  {
     a=A[i];
     k=0;
     C[k]=i;
     k++;
  }
  else if(A[i]==a)
  {
      C[k]=i;
      k++;
  }
}

Будем хранить индексы (first - значение НОД) в "динамическом массиве" (вектор) - тип vector.
Так как в map числа хранятся в отсортированном виде по первому параметру (first), то заноситься они будут в возрастающем порядке. Поэтому при выводе значений нужно это учесть и выводить с последнего элемента. 

Программа на С++:
#include <iostream>
#include <map>
#include <iterator>
#include <vector>
using namespace std;
int main()
{
int A,i,x,y,n;
map<int,int>B;
map<int,int>::iterator it;
vector<int>C;
cin>>n;
for(i=0;i<n;i++)
{
  cin>>x>>y;
  while(x>0&&y>0)
  {
   if(x>y)x=x%y;
   else y=y%x;
  }
  B[x+y]++;//заносим данные в ассоциативный массив
}

A=0;
for(it=B.begin(); it!=B.end(); it++)
 if(it->second>A) //ищем наибольшее значение
 {
  A=it->second;
  C.clear(); //очищаем от старых данных
  C.push_back(it->first);//и заносим в динамический массив (вектор)
 }
 else if(it->second==A) //если максимумов несколько,
  C.push_back(it->first); //то добавим в конец массива
//выводим значения массива в обратном порядке
for(i=C.size()-1;i>=0;i--)
  cout<<C[i]<<" ";
return 0;
}

Экономия по времени и по памяти небольшая, но зато применили знания динамических структур.

Комментариев нет:

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