1 Востаннє редагувалося Torbins (19.04.2015 22:42:25)

Тема: Підрахувати кількість повторів у масиві

Поясніть толково як знайти числа які повторюються більше ніж 3 рази в масиві. Один масивю

Подякували: budda1

2

Re: Підрахувати кількість повторів у масиві

Робите 2 вкладених цикли. В першому берете конкретну цифру, а в другому перевіряєте скільки вона разів повторюється.

Подякували: koala1

3

Re: Підрахувати кількість повторів у масиві

Які вкладені цикли? Все робиться за один прохід. Потрібна ще одна додаткова структура для зберігання даних. Ви будете записувати туди кожну цифру, яку зустріли і додавати одиницю, коли зустріли її ще раз.

Подякували: Arete1

4

Re: Підрахувати кількість повторів у масиві

А можно код ?

5

Re: Підрахувати кількість повторів у масиві

А можна хоч трішки спробувати саменькому? А ми підправимо, допоможемо

6

Re: Підрахувати кількість повторів у масиві

begin

b:=Memo1.Lines.Count;
for i:=1 to b do
massiv[i]:=StrToInt(Memo1.Lines[i-1]);


for i:=1 to b do
begin
for k:=1 to i+1 do
if massiv[i] = massiv[k] then

    Memo2.Lines.Add(Inttostr(i));
end;
end;

Ось що вийшло

7

Re: Підрахувати кількість повторів у масиві

Master_Sergius написав:

Які вкладені цикли? Все робиться за один прохід. Потрібна ще одна додаткова структура для зберігання даних. Ви будете записувати туди кожну цифру, яку зустріли і додавати одиницю, коли зустріли її ще раз.

А справді, можна код?

8

Re: Підрахувати кількість повторів у масиві

Код будь ласка

Подякували: budda1

9

Re: Підрахувати кількість повторів у масиві

По-перше, навіть для дельфі є наробки щодо "асоціативного масиву". По-друге, можна зробити свій об'єкт, де одним значенням (ключем) буде - цифра, а іншим - кількість зустрічей. Наприклад, дано масив:

1 2 5 4 2 1 2

Тоді ваша структура матиме вигляд:
1 2 5 4  (цифри)
2 3 1 1  (кількість зустрічей)

Пошук ключа у структурі можна оптимізувати багатьма способами. І навіть це буде в рази швидше, ніж вкладені цикли. Уявіть, що елементів 10 000, то цикли ганятимуть 100 000 000 разів

Подякували: ex.jedii1

10

Re: Підрахувати кількість повторів у масиві

Master_Sergius написав:

По-перше, навіть для дельфі є наробки щодо "асоціативного масиву". По-друге, можна зробити свій об'єкт, де одним значенням (ключем) буде - цифра, а іншим - кількість зустрічей. Наприклад, дано масив:

1 2 5 4 2 1 2

Тоді ваша структура матиме вигляд:
1 2 5 4  (цифри)
2 3 1 1  (кількість зустрічей)

Пошук ключа у структурі можна оптимізувати багатьма способами. І навіть це буде в рази швидше, ніж вкладені цикли. Уявіть, що елементів 10 000, то цикли ганятимуть 100 000 000 разів

Так, з масиву "к-сть зустрічей" знайти 3, легше ніж два вклад. цикли, Але яким алгоритмом можна дістати (цифри)
і (кількість зустрічей)

11

Re: Підрахувати кількість повторів у масиві

Можна без вкладених циклів.
На PHP

<?php

$arr=[1,2,3,2,4,1,2,9,5,3];
 
$arr2=[];

for($i=0; $i<count($arr); ++$i)

 $arr2[$arr[$i]] ? ++$arr2[$arr[$i]] : $arr2[$arr[$i]]=1;

print_r($arr2); //масив число=>к-ть повторень

12

Re: Підрахувати кількість повторів у масиві

Шановне панство
Ви кудись у захмарні матерії полетіли.

budda
Прокоментую ваш код.
Для кожного числа він знаходить, чи зустрічається воно ще десь у масиві. Причому, для чисел, що повторюються робить це декілька разів, і ніде не зберігає дані, скільки разів це число уже було знайдено. Це проблема, яку треба виправити.
Припустімо, що усі числа у вхідному масиві не менші за A і не більші за B. Тоді створимо додатковий масив:

counter: array[A..B] of Integer;

Значення з massiv будуть індексами у counter, а значеннями у counter буде кількість повторів певного числа у massiv.
Після цього дізнатися, скільки разів поточне число уже зустрічалося можна отак:

Memo2.Lines.Add(Inttostr(counter[massiv[i]]));

А зробити помітку, що це число знайдено ще раз можна отак:

counter[massiv[i]] := counter[massiv[i]] + 1;

13

Re: Підрахувати кількість повторів у масиві

Ось оцей counter - і є примітивною додатковою структурою. А Я ж хотів розширити на більш універсальний випадок - якщо потрібно рахувати літери, слова, чи щось інше, то звичайний масив уже не підійде.

14

Re: Підрахувати кількість повторів у масиві

Master_Sergius
З літерами можна отак:

counter: array[char] of Integer; //замість char може бути будь-який зліченний тип

Основна проблема цього підходу в тому, що масив займатиме дуже багато місця в оперативці, якщо варіантів вхідних даних більше мільйона. Тобто для великих діапазонів A..B і слів дійсно треба придумувати уже якусь складнішу структуру.

15

Re: Підрахувати кількість повторів у масиві

Master_Sergius діло каже, краще все зробити за один прохід масиву. Цикл в циклі це найпростіший алгоритм для даної задачі, але й найбільш ресурсоємний - функція квадратичної складності. Таку лабу викладач може й прийме, але в реальній програмі "ревьюери" коду сказали б - "шо за лажа, йди перероби".

Подякували: Q-bart1