[C++] Tablice

Dla specjalistów Programowanie
#21

Jeśli liczby są naturalne a ciągi mogą być długie, lepiej IMO zastosować zliczanie z sortowaniem. Dodając element do listy/wektora/czegoś, dodajesz tak by ciąg był rosnący. Każdy węzeł trzyma liczbę danych wartości. Przykładowo dodając do wektora/listy 1,2,5,5,3, budujesz kolejno coś takiego:

1(1)

1(1), 2(1)

1(1), 2(1), 5 (1)

1(1), 2(1), 5 (2)

1(1), 2(1), 3(1), 5 (2)

Dla 1,6,2,8,4,5,3,5:

1(1),

1(1), 6(1)

1(1), 2(1), 6(1)

1(1), 2(1), 6(1), 8(1)

1(1), 2(1), 4(1), 6(1), 8(1)

1(1), 2(1), 4(1), 5(1), 6(1), 8(1)

1(1), 2(1), 3(1), 4(1), 5(1), 6(1), 8(1)

1(1), 2(1), 3(1), 4(1), 5(2), 6(1), 8(1)

Następnie porównujesz listy kolejno i przy pierwszym “braku”, wiesz że nie jest podzbiorem.

Generalnie rozwiązanie każdego problemu - szczególnie takiego abstrakcyjnego - jest silnie zależne od typu i probabilistycznego rozkładu danych, na których będziesz operował. Bo o ile na olimpiadach często musisz działać w miarę wydajnie zawsze, w rzeczywistych zastosowaniach w większości przypadków masz pewien wzorzec tego, co przetwarzasz (wiesz jakie są najbardziej prawdopodobne wartości). I pod ten wzorzec tworzysz/optymalizujesz algorytm i struktury danych.

#22

Z tego co wiem to całości nie porównasz. Musiałbyś je przeszukiwać po elementach, ale możliwe że się mylę :wink:

#23

Co do pomysłu alexa tez o tym myślałem. Teraz tak jeśli bym usuwał z kopi to jak? v.erase(iterator pos) o to chodzi? i czy zostanie po usunięciu “dziura” czy pozostałe dane się przesuną i jak sie odwolac do iterator pos

#24

Po erase() nie będzie dziury, więc kasując trzeba “iść od tyłu” aby nie komplikować.

#25

Mam pentle i teraz niewiem jak w erase wywolac odpowiedni index vectora

#26

google nie gryzie

#27

Moze ktos mi wskazac blad

for(i=0;i
        {

            kopia.push_back(m);

            c=0;

            for(j=0;j
            {

                kopia[j]=a[j];

            }

            j=0;


            while(j
            {

                if(kopia[j]==b[i][j]) j++;

                else kopia.erase(kopia.begin()+j);

                if(kopia.size()
                j=b[i].size();


            }


            for(j=0;j
            {

                if(kopia[j]!=b[i][j])

                {

                    c=1;

                    j=kopia.size();

                }

            }

            if(c==1) wynik.push_back("NIE");

            else wynik.push_back("TAK");

            kopia.clear();

        }[/code]

Niewiem co jest zle z ta petla while. Ma wykleslac liczby z kopi, ktore sa rozne od liczb z b[i] o tym samym indeksie

#28

kopia.push_back(m); // dodajesz do kopia element m, może miałeś na myśli resize()

kopia[j]=a[j]; // prawdopodobnie wychodzisz poza zakres

Może najpierw opisz co próbujesz zrobić.

Usuwasz z kopii elementy których niema w kolejnym elemencie b[i] czyli wg mnie badasz nie “czy b jest podzbiorem a” tylko czy z b[i] da się utworzyć a wstawiając niektóre elementy.

Dla takiego badania wystarczy:

=a.size(),bs=b.size();int i=0;ibs;++i)   {    int p=0,s=b[i].size();    for(int k=0;(kps);++k)  if (a[k]==b[i][p]) ++p;    wynik.push_back(ps?"NIE":"TAK");   } Czyli ten kod robi dokładnie to co próbujesz zrobić w ... tym co podałeś.
#29

Cos tu jest zle, ale postaram sie pokombinowac

#30

Tak

//zamiast b[i][p] było B[i][k] [/code]