Strona główna » Kursy » Zadania » Kolokwium 2B 2014/15
 

Kolokwium 2B 2014/15

https://mattomatti.com/lab1415K2B

Cel

Rozwiązanie

Zadanie IIB1

Rozważmy przypadek kiedy macierz zaczyna się liczbą nieparzystą. Wtedy na pozycjach, których jedna współrzędne x i y są równocześnie parzyste lub nieparzyste oznacza, że liczba powinna być nieparzysta. W przeciwnym wypadku rozpatrywana liczba na x, y powinna być parzysta. W ten sposób dochodzimy do wniosku, że pierwszy przypadek będzie spełniony, gdy reszta z dzielenia x przez 2 + reszta z dzielenia y przez 2 wyniesie 0 lub 2, w drugim przypadku 1. Jeśli wynik podzielimy przez dwa uzyskamy 0 dla pierwszego przypadku, a 1 dla drugiego. Teraz ten wynik możemy potraktować jako prawidłowy wynik reszty z dzielenia liczby na x, y przez 2.

Do rozpatrzenia pozostaje drugi przypadek, gdy pierwsza jest liczba parzysta. Na początku sprawdźmy parzystość pierwszej liczby. To ona zadecyduje jakiego typu mamy macierz. Wynik reszty dzielenia liczby na pozycji 1, 1 dodamy do obliczania: reszta z dzielenia x przez 2 + reszta z dzielenia y. Funkcja parznieparz() realizująca ten proces myślenia:

  1. bool parznieparz(int** macierz, int m, int n){
  2.   int ws = (macierz[0][0]%2==0 ? 1 : 0);
  4.   for(int i = 0; i < m; i++){
  5.     for(int j = 0; j < n; j++){
  6.       if(macierz[i][j]%2 == (i%2 + j%2 + ws)%2)
  7.         return false;
  8.     }
  9.   }
  10.   return true;
  11. }

Zadanie IIB2

Napiszemy funkcję najczesciej(), która zliczy ile razy występuje każda litera. Następnie sprawdzi, która litera najczęściej występowała dana litera i ją zwróci.

  1. char najczesciej(char* napis){
  2.   const int dl = 'z' - 'a' + 1;
  3.   int i = 0;
  5.   int* l = new int['z' - 'a' + 1];
  6.   for(i = 0; i < dl; i++)
  7.     l[i] = 0;
  9.   i = 0;
  10.   while(napis[i])
  11.     l[napis[i++] - 'a']++;
  13.   int pozycja = 0;
  14.   for(i = 0; i < dl; i++)
  15.     if(l[i] != 0 && l[pozycja] < l[i])
  16.       pozycja = i;
  18.   delete[] l;
  19.   return 'a' + pozycja;
  20. }

(2.) Na początek deklarujemy zmienną dl, która określa nam ile różnych elementów możemy mieć, czyli wszystkie od a do z dodajemy jeden, bo od 1 do 2 jest nie 2 - 1, a (2 - 1) + 1 elementów. (3.) Zmienna i posłuży nam do różnych celów w różnych częściach kodu. (5.) Inicjalizujemy listę, która posłuży nam do zliczania każdej litery i (6., 7.) ustawiamy wartość każdego elementu na 0. Następnie (9.) resetujemy wskaźnik i na 0 i (10.) przeglądamy cały napis. (11.) Zmieniamy wartość kubełka napis[i++] - 'a', ponieważ kubełek litery a ma indeks=0. Po zliczeniu wystąpień każdego znaku (12.) deklarujemy zmienną pozycja, która będzie wskazywała, który kubełek ma najwięcej elementów. Potem (13.) sprawdzamy dla każdego kubełka czy nie jest pusty i czy ma więcej elementów niż dotąd kubełek znaleziony. Jeśli tak (14.) to go zapamiętujemy. Na sam koniec (16.) usuwamy listę zliczającą czyli nasze kubełki i zwracamy literę pamiętając, że indeks 0 ma a, 1 - b, 2 - c itd.

Zadanie IIB3

Funkcja Loteryjka() najlepiej rozbić na kilka prostszych funkcji do napisania. Na początek zadeklarujmy zmienną stałą, globalną ILOSC:

  1. const int ILOSC = 5;

Dzięki temu za każdym razem, gdy będziemy sprawdzać listę kuponu zamiast pisać 5 to wpiszemy zmienną. Jest to dobry nawyk, bo dzięki temu mamy pewność, ze wszędzie mamy tę sama wartość, a jeśli pomylimy się z wartością zmiennej to wystarczy zmienić to tylko w jednym miejscu zamiast szukać w kodzie, gdzie jeszcze trzeba zmienić.

Pierwsza funkcja, którą dopiszemy będzie sprawdzać czy na podanej liście nie znajduje się dana liczba.

  1. bool naLiscie(int* lista, int dl, int a){
  2.   for(dl--;dl>=0;dl--)
  3.     if(lista[dl]==a)
  4.       return true;
  5.   return false;
  6. }

Nie deklarujemy tu dodatkowej zmiennej, która sprawdza kolejne wartości na liście. Zmniejszamy podaną długość listy. Dzięki temu przeglądamy każdy element idąc od tyłu. Możemy to zrobić wiedząc, że lista ma minimalną długość 0 i nigdzie dalej nie wykorzystujemy podanej zmiennej.

Następna funkcja jest bardziej związana z tematem zadania. Napiszemy funkcję, która wylosuje nam 5 liczb z zakresu od 1 do 100.

  1. int* losujLiczby(){
  2.   int* lista = new int [ILOSC];
  3.   int liczba = 0;
  5.   for(int i = 0; i < ILOSC; i++){
  6.     do{
  7.       liczba = rand()%100 + 1;
  8.     } while(naLiscie(lista, i, liczba));
  9.     lista[i] = liczba;
  10.   }
  11.   return lista;
  12. }

(2.) Deklarujemy listę na której umieścimy wylosowane liczby. (3.) Zmienna liczba posłuży nam do zapamiętania wylosowanej liczby. (4.) Rozpoczynamy losowanie 5 liczb. (5.) Posłużymy się pętlą, aby wylosować liczbę. (7.) Losujemy liczbę, jeśli (8.) jest na liście to wracamy do (7.) co będzie wywoływać losowanie nowej liczby aż uzyskamy taką, której nie ma na liście. Na koniec iteracji z (4.) dopisujemy liczbę na i-te miejsce. (10.) Na sam koniec zwracamy listę wylosowanych liczb.

Mają dwie dodatkowe funkcje przechodzimy do pisania głównej:

  1. int* Loteryjka(int* liczby, int k){
  2.   int* wynik = new int[k];
  3.   for(int i = 0; i < k; i++){
  4.     int* lista = losujLiczby();
  5.     wynik[i] = 0;
  6.     for(int j = 0; j < ILOSC; j++)
  7.       wynik[i] += naLiscie(lista, ILOSC, liczby[j]);
  8.     wynik[i] *= 100;
  9.     delete[] lista;
  10.   }
  11.   return wynik;
  12. }

(2.) wynik to nasza tablica, którą mamy zwrócić na sam koniec. W niej będziemy przechowywać ile za i-tym razem zostało trafionych liczb. (3.) Rozpoczynamy iterację dla każdego z k losowań. Na początek (4.) losujemy nowe liczby. (5.) Ustawiamy ilość trafionych liczb na zero, a (6. - 7.) potem sprawdzamy dla każdej liczby typowanej czy jest na liście wylosowanych. Korzystamy z tego, że wartość prawda to 1. Każda zgarnięta liczba to wygrane 100zł, dlatego (8.) mnożymy ilość trafionych liczb razy sto. Na koniec iteracji (9.) usuwamy wylosowaną listę liczb i (10.) kończymy iteracje. (11.) Na sam koniec zwracamy lsitę wyników.

Zadanie IIB4

Struktura rok powinna wyglądać tak: (oczywiście nazwy zmiennych są dowolne)

  1. struct Rok{
  2.   int m;
  3.   int* d;
  4. };

Kolejna funkcja stworzRok():

  1. Rok* stworzRok(int m, int d){
  2.   Rok* rok = new Rok;
  3.   rok->m = m;
  4.   int* lista = new int[m];
  5.   for(int i = 0; i < m; i++)
  6.     lista[i] = d;
  7.   rok->d=lista;
  8.   return rok;
  9. }

Należy pamiętać o ->, ponieważ rok jest wskaźnikiem.

Ostatnia funkcja nie powinna być problematyczna, ale należy pamiętać, że najpierw musimy sprawdzić poprawność miesiąca i dopiero sprawność poprawność dni, ponieważ odwrotnie możemy odwołać się do elementu tablicy dni, który nie istnieje. Co więcej miesiące i dni numerujemy od 1, więc jeśli sprawdzimy, że dany miesiąc istnieje to ile dni odczytamy na tablicy o indeksie, którego wartość to podany miesiąc zmniejszony o 1.

  1. bool czyPoprawna(Rok* rok, int m, int d){
  2.   return (m>= 1 && m<=rok->m && d >= 1 && d <= rok->d[m-1]);
  3. }

Testy

Polecam zamienić podane funkcje na swoje własne i sprawdzić na przygotowanych testach poprawność swoich rozwiązań:

  1. void wypiszRok(Rok* rok){
  2.   cout << rok->m << "m, {";
  3.   for(int i = 0; i < rok->m; i++){
  4.     cout << rok->d[i];
  5.     if(i+1 != rok->m)
  6.       cout << ", ";
  7.   }
  8.   cout << "}";
  9. }
  11. void wypiszListe(int* lista, int dl){
  12.   for(int i = 0; i < dl; i++){
  13.     cout << lista[i];
  14.     if(i+1 != dl)
  15.       cout << ", ";
  16.   }
  17. }
  19. int main () {
  20.   setlocale(LC_ALL, "");
  21.   srand(0);
  23.   cout << "Zadanie IIB1.";
  24.   int m = 3; int n = 4;
  25.   int** macierz = new int*[m];
  26.   for(int i = 0; i < m; i++)
  27.     macierz[i] = new int[n];
  29.   macierz[0][0]=1;macierz[0][1]=2;macierz[0][2]=1;macierz[0][3]=2;
  30.   macierz[1][0]=2;macierz[1][1]=1;macierz[1][2]=2;macierz[1][3]=1;
  31.   macierz[2][0]=1;macierz[2][1]=2;macierz[2][2]=1;macierz[2][3]=2;
  33.   cout << "\nwyjście: "<< (parznieparz(macierz, m, n) ? "TAK" : "NIE");
  35.   for(int i = 0; i < m; i++)
  36.     delete[] macierz[i];
  37.   delete[] macierz;
  39.   cout << "\n\nZadanie IIB2.";
  41.   char* napis1 = new char[8];
  42.   napis1[0]='a';napis1[1]='b';napis1[2]='a';napis1[3]='a';napis1[4]='c';napis1[5]='a';napis1[6]='b';napis1[7]='\0';
  43.   cout << "\n\nwejście: " << napis1 << "\nwyjście: "<< najczesciej(napis1);
  45.   napis1[0]='b';napis1[1]='a';napis1[2]='b';napis1[3]='a';napis1[4]='b';napis1[5]='a';napis1[6]='b';napis1[7]='\0';
  46.   cout << "\n\nwejście: " << napis1 << "\nwyjście: "<< najczesciej(napis1);
  48.   delete[] napis1;
  50.   cout << "\n\nZadanie IIB3.";
  51.   int k = 4;
  52.   int* lista_liczb = new int [ILOSC];
  53.   lista_liczb[0]=1;lista_liczb[1]=6;lista_liczb[2]=9;lista_liczb[3]=43;lista_liczb[4]=29;
  54.   cout << "\n\nwejście: ";
  55.   wypiszListe(lista_liczb,ILOSC);
  56.   cout << "\nwyjście: ";
  57.   wypiszListe(Loteryjka(lista_liczb,k),k);
  59.   cout << "\n\nZadanie IIB4.";
  60.   Rok* rok = stworzRok(12,30);
  61.   m = 12;
  62.   int d = 12;
  63.   cout << "\n\nwejście: (kalendarz) ";
  64.   wypiszRok(rok);
  65.   cout << "\n (miesiąc/dzień) " << m << "." << d;
  66.   cout << "\nwyjście: "<< (czyPoprawna(rok, m, d) ? "TAK" : "NIE");
  67.  
  68.   delete[] rok->d;
  69.   rok = stworzRok(12,5);
  70.   m=14; d=1;
  71.   cout << "\n\nwejście: (dzień) ";
  72.   wypiszRok(rok);
  73.   cout << "\n (godzina) " << m << "." << d;
  74.   cout << "\nwyjście: "<< (czyPoprawna(rok, m, d) ? "TAK" : "NIE");
  76.   m=1; d=6;
  77.   cout << "\n\nwejście: (dzień) ";
  78.   wypiszRok(rok);
  79.   cout << "\n (godzina) " << m << "." << d;
  80.   cout << "\nwyjście: "<< (czyPoprawna(rok, m, d) ? "TAK" : "NIE");
  82.   delete[] rok->d;
  83.   delete rok;
  85.   cout << "\n\n";
  86.   system("pause");
  87.   return 0;
  88. }