[Algorytmy] Najczęściej pojawiający się element
-
- Użytkownik
- Posty: 46
- Rejestracja: 23 lut 2016, o 20:45
- Płeć: Kobieta
- Lokalizacja: Gdańsk
- Podziękował: 4 razy
[Algorytmy] Najczęściej pojawiający się element
Dzień Dobry
Mam do zrobienia program, który działa na tablicy typu int z wartościami od -100 do 100 (losowymi), zaś ilość elementów mogę dowolnie wybierać. Jedna z funkcji, którą muszę napisać, ma za zadanie wyświetlić element najczęściej występujący oraz podać jej ilość. Tylko nie wiem jak mam się za to zabrać. Była bym wdzięczna za jakieś podpowiedzi.
Pozdrwiam
Mam do zrobienia program, który działa na tablicy typu int z wartościami od -100 do 100 (losowymi), zaś ilość elementów mogę dowolnie wybierać. Jedna z funkcji, którą muszę napisać, ma za zadanie wyświetlić element najczęściej występujący oraz podać jej ilość. Tylko nie wiem jak mam się za to zabrać. Była bym wdzięczna za jakieś podpowiedzi.
Pozdrwiam
Ostatnio zmieniony 30 maja 2016, o 15:01 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 22173
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3748 razy
[Algorytmy] Najczęściej pojawiający się element
WYobraż sobie, że nie masz napisać funkcji, tylko ktoś Ci wysypał kupke owoców (jabłka, gruszki, pomarańcze i mandarynki) i kazał policzyć, których jest najwęcej. Jak się za to zabierzesz?
-
- Użytkownik
- Posty: 318
- Rejestracja: 14 maja 2016, o 16:25
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 90 razy
[Algorytmy] Najczęściej pojawiający się element
Na początku mam 0 jabłek, 0 gruszek, 0 pomarańczy i 0 mandarynek (0,0,0,0).
Wyciągnąłem jabłko, zwiększam liczbę jabłek o 1 (1,0,0,0).
Wyciągnąłem mandarynkę, więc zwiększam liczbę mandarynek: (1,0,0,1).
Ooo, kolejna mandarynka, więc (1,0,0,2).
Na końcu: (5,4,9,7), a więc najwięcej mam pomarańczy (dziewięć).
To jest algorytm, który można zastosować w sytuacji, gdy liczba rodzajów elementów nie jest zbyt duża i jest a priori znana (tutaj mamy taką sytuację: od -100 do 100).
Wyciągnąłem jabłko, zwiększam liczbę jabłek o 1 (1,0,0,0).
Wyciągnąłem mandarynkę, więc zwiększam liczbę mandarynek: (1,0,0,1).
Ooo, kolejna mandarynka, więc (1,0,0,2).
Na końcu: (5,4,9,7), a więc najwięcej mam pomarańczy (dziewięć).
To jest algorytm, który można zastosować w sytuacji, gdy liczba rodzajów elementów nie jest zbyt duża i jest a priori znana (tutaj mamy taką sytuację: od -100 do 100).
-
- Użytkownik
- Posty: 22173
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3748 razy
[Algorytmy] Najczęściej pojawiający się element
M Maciejewski pisze:Na początku mam 0 jabłek, 0 gruszek, 0 pomarańczy i 0 mandarynek (0,0,0,0).
Wyciągnąłem jabłko, zwiększam liczbę jabłek o 1 (1,0,0,0).
Wyciągnąłem mandarynkę, więc zwiększam liczbę mandarynek: (1,0,0,1).
Ooo, kolejna mandarynka, więc (1,0,0,2).
Na końcu: (5,4,9,7), a więc najwięcej mam pomarańczy (dziewięć).
To jest algorytm, który można zastosować w sytuacji, gdy liczba rodzajów elementów nie jest zbyt duża i jest a priori znana (tutaj mamy taką sytuację: od -100 do 100).
Brawo, ale to było zadanie dla autorki posta.
-
- Użytkownik
- Posty: 1931
- Rejestracja: 29 maja 2009, o 11:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 145 razy
- Pomógł: 320 razy
[Algorytmy] Najczęściej pojawiający się element
Najwygodniej (ale niekoniecznie najszybciej) byłoby taką tablicę posortować (np. wbudowaną funkcją quicksqort - wiele języków ma ją w standardzie), i następnie zliczać wystąpienia i porównać. Proste w implementacji oraz dam głowę, że szybsze niż podejście M Maciejewski - gdyż w takim przypadku trzeba policzyć ile mamy unikalnych liczb, a następnie stworzyć tablicę o wielkości równej ich ilości.-- 30 maja 2016, o 18:21 --a tu gotowy i działający kod:
Kod: Zaznacz cały
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int myComp(const void *, const void *);
int main()
{
srand(time(NULL));
int i, tab_size;
printf("Ile elementow ma byc w tablicy: ");
scanf("%d", &tab_size);
int tab[tab_size];
for(i = 0; i < tab_size; ++i)
tab[i] = rand() % 200 - 100;
qsort(tab, tab_size, sizeof(int), myComp);
for(i = 0; i < tab_size; ++i)
printf("%d ", tab[i]);
int counter_cur = 0, counter_prev = 0;
int prev_num, cur_num;
int max_num = tab[0], amount_max = 0;
prev_num = tab[0];
for(i = 0; i < tab_size - 1; ++i)
{
if(tab[i] != tab[i + 1])
{
cur_num = tab[i + 1];
if(counter_cur > counter_prev)
{
max_num = tab[i];
amount_max = counter_cur;
}
counter_prev = counter_cur;
counter_cur = 0;
}
else
++counter_cur;
}
printf("
Najwiecej razy (%d) wystapila liczba: %d
", amount_max + 1, max_num);
return 0;
}
int myComp (const void *a, const void *b)
{
int _a = *(int*)a;
int _b = *(int*)b;
if(_a < _b) return -1;
else if(_a == _b) return 0;
else return 1;
}
-
- Użytkownik
- Posty: 318
- Rejestracja: 14 maja 2016, o 16:25
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 90 razy
[Algorytmy] Najczęściej pojawiający się element
Chyba za dużo podpowiedziałem, przepraszam.a4karo pisze:Brawo, ale to było zadanie dla autorki posta.
Jak napisałem, algorytm, który zaproponowałem jest efektywny wtedy, gdy liczba rodzajów elementów \(\displaystyle{ k}\) jest nieduża, wyraźnie mniejsza niż liczba elementów \(\displaystyle{ n}\) w tablicy (i te elementy są znane a priori, jak np. tutaj: liczby całkowite z przedziału [-100,100]). W tym przypadku jest z pewnością szybszy niż sortowanie o złożoności \(\displaystyle{ n\cdot \log n}\), ponieważ wystarczy raz przelecieć tablicę długości \(\displaystyle{ n}\), a potem raz przelecieć tablicę długości \(\displaystyle{ k}\). Jest to podobne do algorytmu sortowania przez zliczanie.kalwi pisze: Proste w implementacji oraz dam głowę, że szybsze niż podejście M Maciejewski - gdyż w takim przypadku trzeba policzyć ile mamy unikalnych liczb, a następnie stworzyć tablicę o wielkości równej ich ilości.
Tak więc ktoś traci głowę .
Jeśli jednak możliwych wartości jest bardzo dużo, są to np. wartości rzeczywiste, to ten algorytm z pewnością się nie sprawdzi.
-
- Użytkownik
- Posty: 22173
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3748 razy
[Algorytmy] Najczęściej pojawiający się element
kalwi napisał ładny program, ale nie do tego zadania. A priori nie musimy z góry wiedzieć ile mamy elementów na wyjściu. Jedyne co wiemy, to że są to liczby całkowite z zakresu podanego.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Najczęściej pojawiający się element
Podpowiem, że da się to rozwiązać w oczekiwanym czasie liniowym od długości tablicy, niezależnie od zakresu czy rodzaju elementów.
-
- Użytkownik
- Posty: 22173
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3748 razy
[Algorytmy] Najczęściej pojawiający się element
Koledzy, trochę opamiętania.
Koleżanka ma problem z napisaniem prostego algorytmu, a wy tu dyskutujecie o sortowaniu i optymalizacji.
Nie ten poziom... Jeszcze nie.
Koleżanka ma problem z napisaniem prostego algorytmu, a wy tu dyskutujecie o sortowaniu i optymalizacji.
Nie ten poziom... Jeszcze nie.
-
- Użytkownik
- Posty: 1931
- Rejestracja: 29 maja 2009, o 11:58
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 145 razy
- Pomógł: 320 razy
[Algorytmy] Najczęściej pojawiający się element
To jeśli chcemy mieć rozwiązanie naiwne:
- masz tablicę
- tworzysz tablicę
- robisz pętle od
Następnie wyszukanie najczęściej powtarzającego się numeru:
Złożoność czasowa: \(\displaystyle{ O(2n)}\) = \(\displaystyle{ O(n)}\) - jak mniemam właśnie ten algorytm miał na myśli Afish
- masz tablicę
tab
o rozmiarze n
z liczbami z zakresu od <-k;k>
- tworzysz tablicę
array[2k+1]
(+1, ponieważ jeszcze jest zero po środku), inicjalizujesz zerami (tutaj wygodnie byłoby użyć calloca)- robisz pętle od
i=0
do i<n
i następnie co iterację zwiększasz ilość wystąpień danej liczby: ++array[tab[i]+k]
Następnie wyszukanie najczęściej powtarzającego się numeru:
Kod: Zaznacz cały
int counter = array[0]
int max = -k;
for(i = 0; i < 2k + 1; ++i)
if(array[i] > counter)
{
counter = array[i];
max = i-k;
}
Ostatnio zmieniony 2 cze 2016, o 10:19 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 318
- Rejestracja: 14 maja 2016, o 16:25
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 90 razy
[Algorytmy] Najczęściej pojawiający się element
Kalwi, to jest dokładnie algorytm, który podałem.
No właśnie wg mnie złożoność czasowa to \(\displaystyle{ O(n)+O(k)}\), więc jeśli \(\displaystyle{ k}\) jest duże (np maxlongint), to jest bieda. Ten algorytm jest super, gdy \(\displaystyle{ k}\) nie jest wielkie (stałe lub ograniczone przez \(\displaystyle{ n}\) i wtedy mamy faktycznie złożoność liniową. Afish pisze jednak:kalwi pisze: Złożoność czasowa: O(2n) = O(n) - jak mniemam właśnie ten algorytm miał na myśli Afish
Jeśli chodzi o algorytm o złożoności liniowej, wyszukujący najczęściej pojawiający się element, ale bez żadnych ograniczeń, to ja znam jedynie wyszukujący element, który pojawia się więcej niż \(\displaystyle{ \frac{n}{2}}\) razy:Afish pisze: niezależnie od zakresu czy rodzaju elementów.
Kod: Zaznacz cały
kandydat=Tablica[0];
moc=1;
for k=1 to n:
{
jeśli Tablica[k]==kandydat, to moc++
w przeciwnym wypadku moc--
jeśli moc==0, to kandydat=Tablica[k]
}
return kandydat //wynik poprawny, jeśli faktycznie jest taki element, który pojawia się więcej, niż n/2 razy. W przeciwnym wypadku algorytm nie musi zwrócić najczęściej pojawiającego się elementu.
Ostatnio zmieniony 2 cze 2016, o 10:20 przez Afish, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Najczęściej pojawiający się element
Jak już M Maciejewski podał, złożoność to \(\displaystyle{ O(n)+O(k)}\). Wyzerowanie tablicy wymaga przeiterowania po \(\displaystyle{ k}\) elementach.kalwi pisze:Złożoność czasowa: \(\displaystyle{ O(2n)}\) = \(\displaystyle{ O(n)}\)
Nie, nie o ten algorytm mi chodzi. Algorytm wspomniany przeze mnie wykorzystuje hashmapę do przechowywania liczników, stąd jego niska oczekiwana złożoność.kalwi pisze:jak mniemam właśnie ten algorytm miał na myśli Afish
-
- Użytkownik
- Posty: 318
- Rejestracja: 14 maja 2016, o 16:25
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 90 razy
[Algorytmy] Najczęściej pojawiający się element
Aaaacha. To ma sens.Afish pisze:Algorytm wspomniany przeze mnie wykorzystuje hashmapę do przechowywania liczników, stąd jego niska oczekiwana złożoność.