Раздел: Задачи / Простейшие /
Как найти количество уникальных элементов в массиве
Основы программирования Каждый профессионал когда-то был чайником. Наверняка вам знакомо состояние, когда “не знаешь как начать думать, чтобы до такого додуматься”. Наверняка вы сталкивались с ситуацией, когда вы просто не знаете, с чего начать. Эта книга ориентирована как раз на таких людей, кто хотел бы стать программистом, но совершенно не знает, как начать этот путь. Подробнее... |
Условие задачи 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), а также программирование панелей оператора, программируемых реле и других приборов систем автоматизации. Подробнее... |