Раздел: Задачи / Простейшие /
Как найти количество уникальных элементов в массиве
|
Основы программирования Каждый профессионал когда-то был чайником. Наверняка вам знакомо состояние, когда “не знаешь как начать думать, чтобы до такого додуматься”. Наверняка вы сталкивались с ситуацией, когда вы просто не знаете, с чего начать. Эта книга ориентирована как раз на таких людей, кто хотел бы стать программистом, но совершенно не знает, как начать этот путь. Подробнее... |
Условие задачи 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.
#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
Эта книга для тех, кто хочет стать программистом. На самом деле хочет, а не просто мечтает. И хочет именно стать программистом с большой буквы, а не просто научиться кулебякать какие-то примитивные программки… Подробнее... |
|
Помощь в технических вопросах
Помощь студентам. Курсовые, дипломы, чертежи (КОМПАС), задачи по программированию: Pascal/Delphi/Lazarus; С/С++; Ассемблер; языки программирования ПЛК; JavaScript; VBScript; Fortran; Python и др. Разработка (доработка) ПО ПЛК (предпочтение - ОВЕН, CoDeSys 2 и 3), а также программирование панелей оператора, программируемых реле и других приборов систем автоматизации. Подробнее... |