Strona główna » Kursy » Zadania » Napisy zestaw 6A/2014
 

Napisy zestaw 6A/2014

https://mattomatti.com/a20

Zadanie

Oryginalna treść zadania

Rozwiązanie

Omówienie podpunktu 1 - podziel()

Przed omówieniem podpunktu warto przypomnieć sobie, że napis to lista liczb, które na końcu ma znak specjalny \0. Przyjrzyjmy się argumentom funkcji. Otrzymujemy napis s i znak c. Mamy zwrócić nowy dynamicznie alokowany napis. Czyli nie wolno nam modyfikować napisu wejściowego pod żadnym pozorem. Przed przejściem dalej ustalmy nagłówek funkcji:

  1. char* podziel(char* s, char c){
  2.   int pozycja = 0, i = 0;
  3.   while(s[i]!='\0'){
  4.     if(s[i]==c)
  5.       pozycja = i;
  6.     i++;
  7.   }

(2.) Przyjmijmy, że znak c występuje na pozycji 0. Przechowajmy to w zmiennej pozycja. (3.) Następnie sprawdźmy znak po znaku napisu. (4.) Jeśli natrafimy na sprawdzanej pozycji znak c to (5.) zapisujemy w zmiennej pozycja nową pozycje. Na koniec każdej iteracji (6.) należy zwiększyć indeks aktualnie sprawdzanego znaku. (3.) Kiedy natrafimy na znak końca linii to przechodzimy dalej.

W tym momencie zmienna pozycja + 1 przechowuje długość napisu, który mamy przepisać. Warto zastanowić się nad przypadkiem kiedy znaku nie znajdziemy w napisie. Wtedy pozycja będzie równa 0.

  1.   char* s2 = new char[pozycja+1];
  2.   for(int i = 0; i < pozycja; i++)
  3.     s2[i]=s[i];
  4.   s2[pozycja]='\0';
  5.   return s2;
  6. }

Kolejna część rozwiązania polega na (8.) deklaracji nowej listy i (9. - 10.) przepisanie części napisu. Warto pamiętać, że długość tekstu do przepisania wynosi pozycja + 1, ponieważ (11.) ostatni znak musi być znakiem \0. Na koniec należy (12.) zwrócić nowy napis.

Do przetestowania funkcji podziel() można wpisać następujący kod:

  1.   char* s = new char[5];
  2.   s[0]='0';s[1]='1';s[2]='2';s[3]='1';s[4]='\0';
  3.   char* w = podziel(s,'1');
  4.   cout << s << endl << w << endl;

Oczywiście wynikiem działania funkcji powinno być 0121.

Omówienie podpunktu 2 - czyUnikalne()

Odwólując się do wskazówki w zadaniu wykorzystamy funkcje strcmp(), która porównuje dwa napisy. Zgodnie z jej deklaracją

  1. int strcmp(const char *s1, const char *s2)

podajemy jej dwa napisy, które mamy zagwarantowane, że nie zostaną zmienione. Funkcje znajdziemy w bibliotece string.h. Funkcja zwraca liczbę mniejszą od zera, gdy napis1 < napis2, 0 gdy napis1 jest taki sam jak napis2 oraz liczbę większą od zera gdy napis1 > napis2.

Pisanie kodu najlepiej rozpocząć od napisania nagłówka. Funkcja ma na podstawie podanej listy napisów i jej rozmiaru zwrócić wartość logiczną:

  1. bool czyUnikalne(char** t, int n){

Kontynuując analizę zadania wiemy, że wyrazy są posortowane niemalejąco względem porządku leksykograficznego. Najważniejszą informacją z tego jest, że dwa takie same wyrazy mogą wystąpić tylko obok siebie. Żeby sprawdzić czy t napisów jest unikalnych wykonamy tylko t-1 porównań. Zadanie to realizuje poniższy kod:

  1.   for(int i = 1; i < n; i++)
  2.     if(strcmp(t[i-1], t[i]) == 0)
  3.       return false;
  4.   return true;
  5. }

Do przetestowania funkcji podziel() można wpisać następujący kod:

  1.   int n = 4;
  2.   char* t_0 = new char[4];
  3.   t_0[0]='a';t_0[1]='l';t_0[2]='a';t_0[3]='\0';
  4.   char* t_1 = new char[6];
  5.   t_1[0]='a';t_1[1]='l';t_1[2]='a';t_1[3]='a';t_1[4]='a';t_1[5]='\0';
  6.   char* t_2 = new char[5];
  7.   t_2[0]='b';t_2[1]='a';t_2[2]='l';t_2[3]='a';t_2[4]='\0';
  8.   char* t_3 = new char[6];
  9.   t_3[0]='z';t_3[1]='e';t_3[2]='b';t_3[3]='r';t_3[4]='a';t_3[5]='\0';
  10.   char** t = new char* [4];
  11.   t[0]=t_0;t[1]=t_1;t[2]=t_2;t[3]=t_3;
  13.   cout << (czyUnikalne(t,n) ? "TAK" : "NIE");

Omówienie podpunktu 3 - Testy

Testy podane do każdego wcześniejszego podpunktu wystarczy wpisać do funkcji main().