Usuwanie z ciagu powtarzajacych sie podciagow.

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

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

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 ?

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

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.

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

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.

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