[C++] licznik wystąpień

Dla specjalistów Programowanie
#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ć : ) )

#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.

#3

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

#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.

#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.

#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

#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.

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:

#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 : )

#9

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

#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…

#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.