Usuwanie z ciagu powtarzajacych sie podciagow.

Odpowiedz Nowy wątek
2008-11-15 12:29
0

Jaki algorytm (lub jak on dziala) mozna uzyc by dla danego wczytanego ciagu liczb usuwal on powtarzajace sie podciagi np. dla ciagu 12341234 =>1234, a dla 1122232345=>12345.. Z gory dzieki:)

[edit:] chodzi o podciagi nastepujace bezposrednio po sobie :) nie wystarczy przeskanowac ciagu w poszukiwaniu elementow ktore pojawiaja sie pierwszy raz.. np 123234546 to chce otrzymac 1234546.. z gory dzieki.. jeszcze raz

Pozostało 580 znaków

2008-11-16 23:30
mgr.Dobrowolski
0

na mojego nosa jest to zle postawione zadanie,
mam wrazenie, ze mozna dac rozne odpowiedzi, a kazda bedzie w pewien sposob poprawna.
moze sie myle, przemysle to jeszcze.

z wyrazami dr.Czepialski

P.S.(rysik mojego palma nie ma alta)

ale ciekawe, ciekawe...

//q: btw. ciekaw jestem jak to zadanie okresla reakcje na 3333333.. na ozycji zero mamy podciag 333333..., na pozycji jeden mamy podciag 33333..., usuwajac duplikat i pozostawiajac oryginal dostajemy ciag 333333... :)

Pozostało 580 znaków

2008-11-19 20:14
0

Hm.. z tego co dobrze przeczytałem, to zadanie definiuje zachowanie dla ciągu np. 3333333. Należy go uprościć do ciągu(znaku,cyfry) 3 ;>

Algorytm opisujący podejście to rozwiązania tego problemu powinien działać mniej więcej tak :
przechodzimy od pozycji numer 2(względnie od indeksu tablicy 1) przez każdy znak ciagu; dla każdego znaku na pozycji i (i w zakresie 2..N) przechodzimy ciąg od 1 do (i-1) w poszukiwaniu takiego znaku jaki na pozycji i; gdy napotkamy takie wystąpienie(np. na pozycji j < i), rozpoczynamy porównywanie znaków od j+1 ze znakami od i+1; jeśli z takim porównywaniem dojdziemy do pozycji j = i-1, to znaczy że ciąg j..i-1 jest taki sam jak ciag i..i+(i-1-j) i dodatkowo, te ciągi występują po sobie.

Ale zagmatwałem :D Pewnie da się ten algorytm zoptymalizować z użyciem algorytmów wyszukiwania podciągu w ciągu. Przyjmując jednak taki opis, wydaje mi się, że zadanie jest jednoznaczne ?

Pozostało 580 znaków

2008-11-20 20:50
0

nie rozumiem tego.

np 123234546 to chce otrzymac 1234546..

O to ci chodzi że pierwsze liczby 123 ( z 123234546) z się nie powtarzają, czyli wliczamy na początek ciągu. Potem skanujemy kolejne liczby 234. A że 23 jest już w tej samej kolejności w ciągu (123) to nie zapisujemy, za to 4 idzie.
Kolejne to 546. 5 się nie powtarza więc idzie do ciągu, 46 też nie ma takiej kolejności i też idzie do ciągu. O to chodzi ? Czy po prostu "cyferówka" :)

Pozostało 580 znaków

2008-11-20 21:03
0

@Grymek napisał

nie rozumiem tego.
np 123234546 to chce otrzymac 1234546..

A ja nie rozumiem czego nie rozumiesz. W ciągu 123234546 powtarza się podciąg 23, więc jeden egzemplarz wyrzucamy i zostaje 1234546.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2008-11-21 01:10
0

Tutaj zamieszczam dosc proste rozwiazanie tego problemu wg mojego zrozumienia zadania :

char * eraseRepetitions(char T[], int n) {
    if( T == 0 || n < 1 ) return NULL;
        if( n == 1 ) return T;
    int a=0, j=0, k=0, l=0;
    char *A = new char[n+1];
    memset(A,'\0',n+1);
    A[0] = T[0];
    for(int i=1, a=1; i<n ;) { // petla przechodzi po kazdym znaku ciagu
        for(j=0; j<i; j++) { // petla szuka wczesniejszego wystapienia znaku T[i]
            k=j;
            l=i;
            while( (l<n) && (k<i) && (T[k] == T[l++]) ) k++; // petla sprawdza identycznosc ciagow
            if( k == i ) { // jesli identycznosc doszla do znaku i-1( i po inkrementacji)
                i += k-j;  // to znaczy, ze znaleziono wystepujace po sobie iden. ciagi
                break;    // przeskakujemy do przodu o dlugosc powtorzonego ciągu i przerywamy szukanie
            }
        }
        if( k-j > 0 ) continue; // jesli znaleziono identyczne ciagi, to nie przepisujemy bezmyslnie
        A[a++] = T[i++];
    }
    char *B = new char[strlen(A)+1];
    strncpy(B, A, strlen(A)+1);
    delete [] A;
    return B;
}

Pisane z palca, nie gwarantuje 100% poprawności :P

Pozostało 580 znaków

2008-11-21 15:47
0

Ja rozumiem pytanie tak. Dany jest ciąg a, wykonaj na nim:

dopóki uda się znaleźć odcinek b tego ciągu taki, że a = cbbd usuń odcinek b

Aby zagadnienie było dobrze postawione, trzeba wykazać, że kolejność skreśleń nie ma wpływu na ostateczny ciąg. Jeśli a=1111221122, to możemy rozpocząć od 1111221122, od 1111221122,...,od 1111221122. Niezależnie jak zaczniemy i jaki powtarzający się odcinek znajdziemy potem zakończymy na ciągu 12. We wszystkich zbadanych przeze mnie przypadkach końcowy ciąg nie zależał od kolejności skreśleń, ale dowodu nie znalazłem.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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