Najczęściej występujący element - metoda dziel i zwyciężaj

0

Witam. Mój problem wygląda następująco.
Muszę napisać program wyszukujący najczęściej występujący element w zbiorze (jeżeli jest ich kilka to wypisać którykolwiek z powtarzających się). Ma być to metoda dziel i zwyciężaj. Co ta metoda znaczy w teorii - wiem, jednak jeszcze nie "zaprzyjaźniłem" się z funkcjami rekurencyjnymi na tyle żeby ten problem rozwiązać. Nie mam pomysłu jak to ugryźć, a termin się zbliża błyskawicznie. Język programowania to C.
Piszę tutaj w poszukiwaniu znacznej podpowiedzi i pomocy. Dziękuję i niech Bóg wam w dzieciach wynagrodzi.

//Edit: Oczywiscie w google szukalem, lecz nie znalazlem nic co by mi tak naprawde pomoglo.

Znaczną podpowiedź miałem na myśli algorytm postępowania, nie napisany kod. W tym właśnie kłopot. Chyba się nie zrozumieliśmy. Znaczną - bo nie wiem jak mam to zrobić - nie znam algorytmu rekurencyjnego. Nie napisałem nic co miałoby ręce i nogi, jedynie funkcje wypełniającą i wyświetlającą tablice żeby sobie to zwizualizować. Nie chce "szykować pieniędzy" bo to mija się z celem studiowania informatyki. Jestem tutaj aby podnieść swoje umiejętności i jestem zdeterminowany aby to robić. Jest to zadanie dodatkowe i nic mi się nie stanie jeśli go nie zrobię, aczkolwiek chcę...
Teoretycznie pisałem bardziej skomplikowane (od tego :P) algorytmy (poszukiwanie idola, obliczanie wyrażeń w ONP), ale jak już pisałem, z rekurencja jeszcze nie zdążyłem się zaprzyjaźnić :).

0

A są jakieś dodatkowe założenia do tego zadania? Na przykład na to jak liczna jest ta dominanta? Bo jeśli nie ma, to ja nie widzę tutaj żadnego prostego algorytmu dziel i zwyciężaj.
No chyba że uznamy za sensowne rozwiązanie posortowanie ciągu wejściowego a potem puszczenie czegoś podobnego do magicznych 5 ;]
W ogóle na pewno musi to być tą metodą? Bo proste zliczanie w O(n) byłoby szybsze i łatwiejsze.

0

Dokładne polecenie:

Napisz funkcję szukającą elementu w tablicy, który występuje najwięcej razy. Użyj strategii dziel i zwyciężaj. W przypadku, gdy jest kilka dobrych elementów funkcja powinna zwracać którykolwiek z nich.

Jedyne założenie to to że liczby są całkowite. Też móżdżyłem rozwiązanie, a raczej próbowałem, ale nic mi do głowy nie przyszło. Chyba że poprzez "dziel i zwyciężaj" mój ćwiczeniowiec miał na myśli po prostu podzielenie tablicy na pół (bez użycia rekurencji?) i przeszukanie połówek... Mogę założyć ew. że tablica ma stałą długość, ale czy to coś ułatwi... ?

dodanie znacznika <quote> - Furious Programming

0

Ale podział tablicy na pół guzik ci da, bo może tak być że dwie interesujace cię liczby będą w różnych połówkach ;] W efekcie w każdej połówce masz tylko jedno wystąpienie każdej liczby i dopiero sumowanie wystąpień w calej tablicy ujawnia że masz jedną podwójną liczbę.
edit: drugie podejscie :D

  1. Sortujemy liczby
  2. Łączymy w 3. Jeśli w 3 sie coś powtarza to przerzucamy do nowej kolekcji to co sie powtórzyło (dominantę trójki) która będzie bazą dla levelu drugiego.
  3. Jeśli nic w 3 się nie powtarza to usuwamy z tej trójki środkową liczbę, bo ona na pewno nie ma pary.
    Postępujemy tak aż w tablicy nie zostanie nam nic (tzn po przeleceniu calej tablicy lecimy od nowa łącząc w 3) a ostatnie dwie liczby odrzucamy.
    Następnie odpalamy dokładnie ten sam algorytm dla tych elementów które wpadly do naszej kolekcji level 2.

Powtarzamy cały proces aż kolekcja level 2 zostanie pusta po którymś obiegu (wtedy rozwiązaniem są dwie pozostałe liczby w level 1) albo będzie w niej jedne element który jest rozwiązaniem.

0

Rano spróbuje to naskrobać, teraz jest już dosyć późno. Dzięki za pomoc, podejmę wyzwanie i zaprogramuje to :p. Pytanie tylko - jak usunąć z tej trójki jedną liczbę w tablicy :D ? Może co rozumiesz przez "usunac" ?

0

No już bez żartów z takimi pytaniami. A niech to będzie lista a nie tablica ;] Albo przepisuj do nowej tablicy. Co za rożnica? To przecież szczegół.

1 użytkowników online, w tym zalogowanych: 0, gości: 1