Согласие на обработку персональных данных.

15.05.2020
Добавлен курс Тестировщик программного обеспечения.

12.09.2020
Новые видео и статья Процедура Include.

07.09.2020
Новый выпуск журнала Автоматизация и Программирование.

12.08.2020
Новые видео и статья Консоль ошибок для JavaScript.

09.07.2020
Новые видео и статья Операторы != и == против операторов !== и ===.



Раздел: Задачи / Простейшие /

Как найти количество уникальных элементов в массиве

Условие задачи 2.99

Задача 2.99
Дан одномерный массив А неупорядоченных целых чисел. Вывести на экран количество уникальных элементов в массиве.

Это не такая простая задача, как может показаться на первый взгляд. Даже мне пришлось немного поломать голову - с наскока сделать не удалось.

Но в этом и смысл задач - учиться искать решения.

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

То есть массив А содержит числа, а в массив В я буду записывать индексы массива А совпадающих (не уникальных) элементов. Для уникальных элементов индексы в массиве В будут равны нулю. Таким образом, после поиска совпадений, у меня получится массив В такой же размерности, как и исходный массив. Но элементы с нулевым значением в массиве В будут соответствовать уникальным элементам в массиве А. И, подсчитав нулевые элементы в массиве В, мы сможем определить количество уникальных элементов в массиве А.

Сложновато? Ну да, не очень красиво. Но это первое решение, которое пришло в голову. Обычно программы так и пишутся:

  • Сначала быстро создаётся версия, которая будет хоть как-то работать, чтобы можно было побыстрее начать её использовать.
  • А потом выпускаются новые версии с доработками. И так до бесконечности...

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

Подробно описывать решение не буду - см. комментарии в исходных кодах и видео выше.

Примеры программ на Паскале и С++.

Решение задачи 2.99 на Паскале
program mytask;

uses CRT;     //!!! Подключить этот модуль

//****************************************************************
// КОНСТАНТЫ
//****************************************************************
const
  MAX_A = 16;

//****************************************************************
// ТИПЫ ДАННЫХ
//****************************************************************
type TMas = array[1..MAX_A] of byte;

//****************************************************************
// ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
//****************************************************************
var
  i         : byte;        //Индекс
  UniqueNum : byte = 0;    //Количество уникальных элементов
  A         : TMas;        //Массив чисел
  B         : TMas;        //Массив индексов

//****************************************************************
// ФУНКЦИИ И ПРОЦЕДУРЫ
//****************************************************************

//****************************************************************
// Определяет количество уникальных элементов в массиве
// ВХОД:  В - глобальный массив индексов
// ВЫХОД: UniqueNum - глобальная переменная - количество
// уникальных элементов
//****************************************************************
procedure GetUnique;
var i : byte;
begin
  UniqueNum := 0;
  for i := 1 to MAX_A do
    if B[i] = 0 then Inc(UniqueNum);
end;

//****************************************************************
// Проверяет уникальность элемента в массиве
// ВХОД:  А и В - глобальные массивы
//        N - значение элемента
//        Ind - индекс элемента
//****************************************************************
procedure CheckUnique(N, Ind : byte);
var i   : byte;
begin
  for i := 1 to MAX_A do
    //Если найдено совпадение
    if (A[i] = N) and (i <> Ind) then B[i] := i;
end;

//****************************************************************
// ОСНОВНАЯ ПРОГРАММА
//****************************************************************
begin
  Randomize;                //Запустить генератор случайных чисел

  //Создать массив и вывести на экран
  for i := 1 to MAX_A do
    begin
      A[i] := Random(50);
      B[i] := 0;
      Write(A[i], ' ');
    end;

  //Найти одинаковые элементы
  for i := 1 to MAX_A do
    CheckUnique(A[i], i);

  WriteLn;
  GetUnique;  //Определить число уникальных элементов

  //Вывести массив с обнаруженными совпадениями
  for i := 1 to MAX_A do
    begin
      if B[i] > 0 then TextColor(Yellow)
      else TextColor(LightGray);
      Write(A[i], ' ');
    end;

  TextColor(LightGray);

  //Вывести решение на экран
  WriteLn(#10#13'Problem solution:');
  WriteLn('  Elements in the array: ', MAX_A);
  WriteLn('  Of them unique:        ', UniqueNum);

  WriteLn('The end. Press ENTER...');
  ReadLn;
end.
Решение задачи 2.99 на С++
#include <cstdlib>
#include <iostream>
#include <ctime>      //!!! Подключить, если будет ругаться на srand

//****************************************************************
// КОНСТАНТЫ
//****************************************************************
const int MAX_A = 16; 

//****************************************************************
// ТИПЫ ДАННЫХ
//****************************************************************
typedef short int TMas[MAX_A]; 

using namespace std;

//****************************************************************
// ГЛОБАЛЬНЫЕ ПЕРЕМЕННЫЕ
//****************************************************************
short int i;             //Индекс
short int UniqueNum = 0; //Количество уникальных элементов
TMas A;                  //Массив 
TMas B;                  //Массив 

//****************************************************************
// ФУНКЦИИ И ПРОЦЕДУРЫ
//****************************************************************

//****************************************************************
// Определяет количество уникальных элементов в массиве
// ВХОД:  В - глобальный массив индексов
// ВЫХОД: UniqueNum - глобальная переменная - количество 
// уникальных элементов
//****************************************************************
void GetUnique()
{
short int i;
  UniqueNum = 0;
  for (i = 0; i < MAX_A; i++)
    if (-1 == B[i]) UniqueNum++;
}

//****************************************************************
// Проверяет уникальность элемента в массиве
// ВХОД:  А и В - глобальные массивы
//        N - значение элемента
//        Ind - индекс элемента
//****************************************************************
void CheckUnique(short int N, short int Ind)
{
short int i;
  for (i = 0; i < MAX_A; i++)
    //Если найдено совпадение
    if ((A[i] == N) && (i != Ind)) B[i] = i;
}

//****************************************************************
// ОСНОВНАЯ ПРОГРАММА
//****************************************************************
int main(int argc, char *argv[])
{
  srand(time(0));         //Запустить генератор случайных чисел

  //Создать массив и вывести на экран
  for(i = 0; i < MAX_A; i++)
  {
    A[i] = (rand() % 50);
    B[i] = -1;
    cout << int(A[i]) << " ";
  }

  //Найти одинаковые элементы
  for(i = 0; i < MAX_A; i++)
    CheckUnique(A[i], i);

  cout << endl;
  GetUnique();  //Определить число уникальных элементов
  
  //Вывести массив с обнаруженными совпадениями
  for(i = 0; i < MAX_A; i++)
  {
    if (B[i] > -1) cout << "*";
    cout << A[i] << " ";
  }

  //Вывести решение на экран
  cout << endl << "Problem solution:" << endl;
  cout << "  Elements in the array: " << MAX_A << endl;
  cout << "  Of them unique:        " << UniqueNum << endl;
  
  system("PAUSE");
  return EXIT_SUCCESS;
}

Как найти количество уникальных элементов в массиве

ПРИМЕЧАНИЕ
Программа на С++ несколько отличается от программы на Паскале. Во-первых, вместо выделения цветом я использовал знак * для обозначения одинаковых чисел (потому как в С++ использовать цвет сложнее, чем в Паскале, если хотите знать как - читайте мою книгу “Основы С++”). Во-вторых, в С++ индексация массивов начинается с нуля, поэтому мы не можем использовать ноль в массиве В, и применяем -1. Есть и другие особенности, но о них я уже говорить не буду.

ВНИМАНИЕ!
Если вам что-то осталось непонятно, то советую почитать книги “Основы программирования” и “Основы С++”.


Основы C++ Основы C++

C++ - это один из самых популярных языков программирования. Не важно, на каком языке программируете лично вы. Но, если вы хотя бы в общих чертах не знаете С++, то это большой пробел в вашем образовании, который надо восполнить как можно быстрее... Подробнее...
Инфо-МАСТЕР ®
Все права защищены ©
e-mail: mail@info-master.su

Яндекс.Метрика