[C++] licznik wystąpień


(Atrox2) #1

Witam,

mam problem z programem, który by wczytywał dane z pliku oraz liczył ilość wystąpień par i trójek liczb w każdym wersie.

tzn.

w pliku dane.txt są takie linie:

23,34,78,95,22,45,68,64,20,46,78,45,32,

11,23,42,45,46,78,68,41,22,48,12,13,15,

itd...

i teraz program liczy wystąpienia takich samych par w tych wersach.

czyli para 23 i 34 wystąpiła tylko raz

23 i 46 wystapila 2 razy

22 i 46 wystapila takze 2 razy...

i trójkami

23,22 i 46 wystapilo 2 razy

23,34,95 tylko 1 raz.

Przy końcu wyświetlenie największej ilości powtórzeń

oraz zapisanie 20 najczęstszych wystąpień.

Próbowałem robić z tablicami trójwymiarowymi tyle ze przy dopisywaniu każdej kombinacji cyfry wyszło 100*100*100 = 1000000 czyli program chodziłby w ślimaczym tempie (wersów może być około 15 tys.)

Proszę o pomysł jak to można rozwiązać (jeżeli ktoś chętny to może z kodem opisać : ) )


(Zulowski) #2

Tak na szybko bez większego myślenia, tworzysz 1 tablicę 1 wymiarową od 0 do maksymalnej liczby

spotyka 23 - w komorke 23(lub 22, bo numerowane od 0...) dodaje +1, po przejściu masz zliczone wystąpienia każdej z liczb, gdzie 0, to nie było w ogóle takiej liczby, gdzie 1, to jedno wystąpienie... itd.


(Atrox2) #3

No tak ale jak sprawdzę czy się 3 powtórzyły razem ze sobą?


(Zulowski) #4

No miałbyś ilość wystąpień danej liczby w wierszu, np komórka nr 7 z wartością 3 oznacza, że w tym wierszu liczba 7 wystąpiła 3 razy.


(Tomek Matz) #5

@Zulowski

Nie rozumiem Twojego rozwiązania. Autor ma liczyć ilość wystąpień par i trójek liczb, a nie ich pojedyncze wystąpienia. Do tego celu potrzebna jest zagnieżdżona pętla i nie widzę tutaj sensu szukania maksymalnej liczby w danym wierszu.

@lifeframe89

Mogłeś jeszcze podać, czy wiesz jaka jest maksymalna liczba, która może się pojawić w pliku. Chyba, że może to być dowolna? I napisz która para w tych 2 przykładowych linijkach ma najwięcej wystąpień. Wydaje mi się, że 45,78 i jest to 5 wystąpień. Jeśli tak nie jest to napisz proszę dlaczego. Napisz też która trójka ma najwięcej wystąpień. Wydaje mi się, że maksymalna ilość to 5, a tą ilość osiągają 22,45,78 ; 23,45,78 ; 45,46,78 oraz 45,68,78.


(Atrox2) #6

@matzu

W każdym wersie może być dowolna, ale od 01 do 99.

A co do "I napisz która para w tych 2 przykładowych linijkach ma najwięcej wystąpień" w 2 wersach najwiecej wystapien może być...2, bo liczby się nie powtarzają, (wiem, źle wpisałem liczby tam) i chodzi o zliczanie wystąpień parami i trójkami.

Podam krócej żeby prościej było

01,02,03,04,05,06,07,08,

01,02,03,09,10,11,12,13,

pary które się powtórzyły 2 razy to: 01 i 02, 02 i 03.

trójka jest jedna : 01,02,03


(Tomek Matz) #7

OK rozumiem. To pary masz trzy w tym przykładzie ... jeszcze 01 i 03 (przynajmniej tak mi zwrócił program).

Na początek tworzysz sobie dwie wielowymiarowe tablice. Jedna 99x99 a druga 99x99x99 i inicjalizujesz je samymi zerami. Serce programu to będą cztery zagnieżdżone pętle. Pierwsza pętla będzie linijka po linijce odczytywać zawartość pliku, a w jej środku będą wykonywane operacje na tej linijce odczytanej z pliku:

  1. Dany wiersz rozbijasz na tablicę string-ów.

  2. Z danej tablicy stringów tworzysz tablicę int-ów i sortujesz tą tablicę tak, żeby zawierała elementy w kolejności od najmniejszego do największego.

3.

int count = sizeof(rowArrayInt)/sizeof(rowArrayInt[0]);


for (int i = 0; i < count; i++)

    for (int j = i + 1; j < count; j++)

    {

        result1[rowArrayInt[i] - 1][rowArrayInt[j] - 1] += 1;


        for (int k = j + 1; k < count; k++)

            result2[rowArrayInt[i] - 1][rowArrayInt[j] - 1][rowArrayInt[k] - 1] += 1;

    }

rowArrayInt to posortowana jednowymiarowa tablica int-ów wczytanych z danej linijki pliku.

result1 to tablica dwuwymiarowa 99x99, która będzie przechowywać pary liczb i ilość wystąpień tych par.

result2 to tablica trójwymiarowa 99x99x99, która będzie przechowywać trójki liczb i ilość wystąpień tych liczb.

Gdy główna pętla programu odpowiedzialna za odczytywanie pliku linijka po linijce zakończy działanie to w result1 i result2 będziesz miał wszystkie wyniki. Żeby teraz np. odczytać ile było wystąpień pary 22 i 23 robisz

int value = result[23][24]; (trzeba pamiętać o tym, że elementy w tablicy numerowane są od 0, dlatego 23 zamiast 22).

Generalnie jak już wczytasz cały plik to będziesz musiał zaimplementować sortowanie dla tablicy dwuwymiarowej i trójwymiarowej. Możesz zaimplementować najprostsze tj. sortowanie bąbelkowe.

I jeszcze jedno ... ten program daje Ci spore pole do popisu, bo do przechowywania ilości wystąpień możesz użyć tablic wielowymiarowych, ale możesz też stworzyć swoją klasę, która będzie miała pola number1, number2 i occurrenceCount. Teraz do przechowywania elementów tej klasy mógłbyś użyć jakiejś hashtablicy (nie wiem czy w C++ są takowe z miejsca dostępne, ja ten program napisałem sobie na szybko w innym języku). Które rozwiązanie okaże się wydajniejsze, to już będziesz musiał stwierdzić sam, testując :slight_smile:


(Atrox2) #8

@matzu

O Matko : O. Tylko wrócę do domu i spróbuje coś z tego zrozumieć xD.

Wielkie wielkie wielkie dzięki za chęci : ).

Czapki z głów z twoją wiedza : )


(Tomek Matz) #9

Bez przesady :slight_smile: BTW wstawiłem poprawkę w opisie, bo machnąłem babola. Teraz jest OK.


(Atrox2) #10

Przed godzina wziełem się do roboty nad tym, no i mam problem który mnie zaskoczył :open_mouth:

Otóż program się sypie po skompilowaniu bez błędów tego:

int tab1[99][99];

   int tab2[99][99][99];

for(int a=0;a<99;a++)

{

        for(int b=0;b<99;b++)

        {

                for(int c=0;c<99;c++)

                {

                        tab1[a][b]=0;

                        tab2[a][b][c]=0;

                }  

        }

}

Już tak to męczę i dalej nie mam pojęcia co jest źle...


(Tomek Matz) #11

Odpowiedź dlaczego tak się dzieje i jak to poprawić znajdziesz tutaj http://www.daniweb.com/software-development/cpp/threads/46297. Same pętle są OK, za wyjątkiem tego, że instrukcja tab1[a] =0; powinna zostać umieszczona w drugiej, a nie trzeciej pętli.