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

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

Основы программирования 2.0 Основы программирования
Каждый профессионал когда-то был чайником. Наверняка вам знакомо состояние, когда “не знаешь как начать думать, чтобы до такого додуматься”. Наверняка вы сталкивались с ситуацией, когда вы просто не знаете, с чего начать. Эта книга ориентирована как раз на таких людей, кто хотел бы стать программистом, но совершенно не знает, как начать этот путь. Подробнее...

Условие задачи 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. Есть и другие особенности, но о них я уже говорить не буду.

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


Как стать программистом 2.0 Как стать программистом 2.0

Эта книга для тех, кто хочет стать программистом. На самом деле хочет, а не просто мечтает. И хочет именно стать программистом с большой буквы, а не просто научиться кулебякать какие-то примитивные программки… Подробнее...
Помощь в технических вопросах Помощь в технических вопросах

Помощь студентам. Курсовые, дипломы, чертежи (КОМПАС), задачи по программированию: Pascal/Delphi/Lazarus; С/С++; Ассемблер; языки программирования ПЛК; JavaScript; VBScript; Fortran; Python и др. Разработка (доработка) ПО ПЛК (предпочтение - ОВЕН, CoDeSys 2 и 3), а также программирование панелей оператора, программируемых реле и других приборов систем автоматизации. Подробнее...

Инфо-МАСТЕР ®
Все права защищены ©
e-mail: mail@info-master.su

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