Посчитать, сколько в списке различных элементов, не изменяя самого списка

@PascalProgram · Регистрация: 16.12.2018

Студворк — интернет-сервис помощи студентам

Дан список. Посчитайте, сколько в нем различных элементов, не изменяя самого списка.

входные данные
3 2 1 2 3
выходные данные
3

@Kitayets · 16.03.2019, 23:35

задачу можно решить различными способами в зависимости от ограничений на входные данные

@PascalProgram · 16.03.2019, 23:39 **[ТС]**

Здесь ограничений тоже нет.

@Kitayets · 17.03.2019, 00:10

ну в общем виде нужна динамическая структура со свойствами set-a но можно использовать и обычный TStringList что-бы не изобретать велосипед.

например так:

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
program num_uniq;
{по заданию с https://www.cyberforum.ru/free-pascal/thread2420140.html
Дан список. Посчитайте, сколько в нем различных элементов, не изменяя самого списка.
 
входные данные
3 2 1 2 3
выходные данные
3}
{$mode objfpc}{$H+}
 
uses
  Classes, sysutils;
var
  num: Integer;
  list: TStringList;
 
begin
  list:= TStringList.Create;
  list.sorted:= True; // If the stringlist is not sorted, the Duplicates setting is ignored.
  list.Duplicates:= dupIgnore; // Duplicate values will not be added to the list, but no error will be triggered.
  while not EOF do begin
    read(num);
    list.Add(IntToStr(num));
  end;
  writeln(list.Count);
  FreeAndNil(list);
end.

@PascalProgram · 17.03.2019, 00:54 **[ТС]**

А с массивом?

@Kitayets · 17.03.2019, 22:04

Сообщение от PascalProgram

А с массивом?

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

если ограничений нет, то теоретически входной поток может быть размером в несколько гигабайт и каждое значение элемента может принять значение от -(MaxInt - 1) до MaxInt. Никаким массивом такую задачу не решить, впрочем как и списком.

Т.е. можно говорить о том что задача не корректно поставлена, как и большинство других, которые вы постите на форум. Либо ваш преподаватель не грамотен, либо вы утаиваете часть условий.

Например допустим входной поток содержит в 10 раз больше элементов, чем доступно у вас в ПК памяти, а количество не повторяющихся значений на 1 меньше чем можно представить в диапазоне -(MaxInt - 1) до MaxInt. Т.е. -2147483648 .. 2147483647, так вот, что бы узнать что следующее число встречалось уже или нет нам нужно хранить все уже встретившиеся уникальные элементы. Чтобы сохранить в памяти все значения которые можно представить в типе integer (longint) нам потребуется 4 гигабайта в памяти. Врятли ваш преподаватель хотел что-бы вы использовали массив такого размера. По этому должны быть какие-то ограничения на входные данные либо явные, либо не явные, которые так или иначе подразумеваются.

Добавлено через 10 минут
если что - компилятор freepascal не дает определить статический массив который займет в памяти больше 2 гб. Можно использовать динамический, но все же не думаю что это правильно.

@bormant · 17.03.2019, 22:12

Сообщение от Kitayets

-(MaxInt - 1)

Нет, -MaxInt-1. Вам хотелось записать -(MaxInt+1), но MaxInt+1 не имеет смысла, а -(MaxInt-1) больше минимального значения аж на 2, то есть даже хуже, чем -MaxInt.

@Kitayets · 17.03.2019, 23:07

bormant, ок, Вы правы, диапазон получается -(MaxInt+1) .. MaxInt
но по другим соображениям замечания есть?

@bormant · 17.03.2019, 23:55

Kitayets,
другие соображения -- вечный компромисс память-процессор. Если нельзя использовать дополнительную память -- остается квадратичный алгоритм: просматриваем назад в поисках текущего элемента, если нашли, то не считаем дубль:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const nMax=32767;
var
  a: array [0..nMax-1] of Integer;
  n, i, t: Integer;
begin
  while not EoLn do begin
    Read(t); i:=0;
    while (i<n) and (a[i]<>t) do Inc(i);
    if i=n then begin
      if n<nMax then begin
        a[n]:=t; Inc(n);
      end else begin
        WriteLn('ошибка: исчерпана память'); Halt;
      end;
    end;
  end;
  WriteLn(n);
end.

Последовательный поиск здесь легко заменить на поддержку списка сортированным и бинарный поиск.

@Kitayets · 18.03.2019, 00:36

ну это же тоже самое о чем я писал - надо где-то хранить все уже встреченные уникальные элементы. В Вашем примере всего 32767 уникальных элементов, автор же утверждает что для входных данных:

Сообщение от PascalProgram

Здесь ограничений тоже нет.

@bormant · 18.03.2019, 11:26

Сообщение от Kitayets

В Вашем примере всего 32767 уникальных элементов

Это пример. Тип элемента массива в виде Integer в подобном случае тоже должен был вызвать сомнение. Уникальных значений не может быть больше, чем позволяет тип.
Для Byte или ShortInt достаточно 256 элементов массива,
для Word или SmallInt -- 65536,
для LongWord или LongInt достаточно 4294967296 элементов.
А для QWord или Int64 -- 18446744073709551616 :-)
Поэтому можно сделать морду кирпичом, написав:

Pascal
1
2
type TElement=Word;
var a: array [0..High(TElement)-Low(TElement)] of TElement;

Для элементов типа Word этого достаточно ;-) Не подходит под условие? Так множество целых чисел не ограничено, найти то, что больше предусмотренного в программе, не составит труда.

Добавлено через 19 минут
Правда с полностью покрытым диапазоном все еще намного проще:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
type TElement=LongInt;
var
  a: bitpacked array [Low(TElement)..High(TElement)] of Boolean;
  t: TElement;
  n: LongWord;
begin
  while not EoLn do begin
    Read(t);
    if not a[t] then begin
      Inc(n); a[t]:=True;
    end;
  end;
  WriteLn(n);
end.

Добавлено через 13 минут
Ну и SizeOf(a) = 4/8 ГБ = 0,5 ГБ, вполне терпимо.

@PascalProgram · 18.03.2019, 16:51 **[ТС]**

Спасибо всем!

@Kitayets · 19.03.2019, 00:48

И все же она не вертится?

@bormant · 19.03.2019, 07:18

Kitayets,
хотелось бы узнать версию и разрядность компилятора.
FPC 3.0.4 x86_64 проблем не видит. В Win 10 x86_64 с 4 ГБ на борту успешно исполняется.

Добавлено через 5 минут
Интересно увидеть вывод

Pascal
1
2
3
4
5
type
  TBits = bitpacked array [Low(LongInt)..High(LongInt)] of Boolean;
begin
  WriteLn(SizeOf(TBits));
end.

@Kitayets · 20.03.2019, 00:02

Сообщение от bormant

Интересно увидеть вывод

та же ошибка на строке с объявлением типа

Версия компилятора на скриншоте. Не смотря на то что компилятор 32битный - полугигабайтный массив он мог бы использовать.

@volvo · 20.03.2019, 00:26

Компилятор 3.0.4 32-битный - так же история. Хоть в доках и написано, что

The size of bitpacked records and arrays is limited:

On 32 bit systems the maximal size is 2²⁹ bytes (512 MB).

, но реально переполнение возникает даже в случае:

Pascal
1
2
type
  TBits = bitpacked array [0..High(LongInt)] of Boolean;

а вот

Pascal
1
2
type
  TBits = bitpacked array [0..High(LongInt) - 1] of Boolean;

уже компилируется. Так что не более 256 Мб принимается в действительности под 32 битами.

@bormant · 20.03.2019, 07:17

Надо бы в исходниках компилятора глянуть, такое ощущение, что решение о превышении размера принимается ДО применения bitpacked...

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@PascalProgram 0 / 0 / 0 Регистрация: 16.12.2018 Сообщений: 45

	Посчитать, сколько в списке различных элементов, не изменяя самого списка 16.03.2019, 21:56. Показов 4931. Ответов 16 Метки нет (Все метки) Дан список. Посчитайте, сколько в нем различных элементов, не изменяя самого списка. входные данные 3 2 1 2 3 выходные данные 3 0

@Kitayets 445 / 373 / 133 Регистрация: 09.09.2011 Сообщений: 1,343
	16.03.2019, 23:35
	задачу можно решить различными способами в зависимости от ограничений на входные данные 0

@PascalProgram 0 / 0 / 0 Регистрация: 16.12.2018 Сообщений: 45
	16.03.2019, 23:39 [ТС]
	Здесь ограничений тоже нет. 0

@PascalProgram 0 / 0 / 0 Регистрация: 16.12.2018 Сообщений: 45
	17.03.2019, 00:54 [ТС]
	А с массивом? 0

@Kitayets 445 / 373 / 133 Регистрация: 09.09.2011 Сообщений: 1,343
	17.03.2019, 23:07
	bormant, ок, Вы правы, диапазон получается -(MaxInt+1) .. MaxInt но по другим соображениям замечания есть? 0

@PascalProgram 0 / 0 / 0 Регистрация: 16.12.2018 Сообщений: 45
	18.03.2019, 16:51 [ТС]
	Спасибо всем! 0

@Kitayets 445 / 373 / 133 Регистрация: 09.09.2011 Сообщений: 1,343
	19.03.2019, 00:48
	И все же она не вертится? Миниатюры 0

@bormant Модератор 7816 / 4635 / 2837 Регистрация: 22.11.2013 Сообщений: 13,158 Записей в блоге: 1
	20.03.2019, 07:17
	Надо бы в исходниках компилятора глянуть, такое ощущение, что решение о превышении размера принимается ДО применения bitpacked... 0

Посчитать, сколько в списке различных элементов, не изменяя самого списка

Решение