Kolokwium 2A 2014/15

Cel

• Kolokwium Treść

Rozwiązanie

Zadanie IIA1

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

1. const int ILOSC = 6;

Dzięki temu za każdym razem, gdy będziemy sprawdzać listę kuponu zamiast pisać 6 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 6 liczb.

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()%49 + 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 6 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* DuzyLotek(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.     delete[] lista;
9.   }
10.   return wynik;
11. }

(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. Na koniec iteracji (8.) usuwamy wylosowaną listę liczb i (9.) kończymy iteracje. (10.) Na sam koniec zwracamy listę wyników.

Zadanie IIA2

Można tu szukać różnych rozwiązaniach. Jednak im prościej tym lepiej:

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

(2.) Zmienna mn będzie przechowywać informację czy jaki mamy typ macierzy, ponieważ z jednego typu uzyskujemy drugi mnożąc całą macierz przez -1. W ten sposób ograniczamy sprawdzenie tylko do pierwszego przypadku jeśli każdą sprawdzaną liczbę macierzy pomnożymy przez mn. (3., 4.) Sprawdzamy każdą liczbę macierzy i (5.) sprawdzamy czy ma odpowiednią wartość. Jeśli nie to (7.) zwracamy fałsz. (10.) Prawdę zwrócimy tylko, gdy nie zwrócimy fałszu czyli wszystkie liczby spełnią założenia.

Żeby sprawdzić, dlaczego kod działa warto sobie rozpatrzeć kolejne iteracje na poniższym przykładzie:

Zadanie IIA3

Struktura powinna wyglądać tak:

1. struct Dzien{
2.   int h;
3.   int* m;
4. };

Kolejna funkcja stworzDzien():

2. Dzien* stworzDzien(int h, int m){
3.   Dzien* dzien = new Dzien;
4.   dzien->h = h;
5.   int* lista = new int[h];
6.   for(int i = 0; i < h; i++)
7.     lista[i] = m;
8.   dzien->m=lista;
9.   return dzien;
10. }

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

Ostatnia funkcja nie powinna być problematyczna, ale należy pamiętać, że najpierw musimy sprawdzić poprawność godziny i dopiero sprawność poprawność minut, ponieważ odwrotnie możemy odwołać się do elementu tablicy minut, który nie istnieje.

1. bool czyPoprawny(Dzien* dzien, int h, int m){
2.   return (h<dzien->h && m<dzien->m[h]);
3. }

Zadanie IIA4

W moim rozwiązaniu wykorzystuje metodę kubełkową, ponieważ jest mało przypadków i łatwo opisać krok po kroku co się dzieje.

1. char rzadko(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żymy 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 najmniej elementów. Potem (13.) sprawdzamy dla każdego kubełka czy nie jest pusty i czy ma mniej 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.

Testy

Na samo koniec zamieszczam funkcję main() z przygotowanymi testami. Dzięki temu łatwiej będzie sprawdzić swoje rozwiązanie modyfikując odpowiednie funkcje i wyświetlając rezultat.

1. void wypiszDzien(Dzien* dzien){
2.   cout << dzien->h << "h, {";
3.   for(int i = 0; i < dzien->h; i++){
4.     cout << dzien->m[i];
5.     if(i+1 != dzien->h)
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 IIA1.";
24.   int k = 4;
25.   int* lista_liczb = new int [ILOSC];
26.   lista_liczb[0]=27;lista_liczb[1]=37;lista_liczb[2]=9;lista_liczb[3]=49;lista_liczb[4]=43;lista_liczb[5]=7;
27.   cout << "\n\nwejście: ";
28.   wypiszListe(lista_liczb,ILOSC);
29.   cout << "\nwyjście: ";
30.   wypiszListe(DuzyLotek(lista_liczb,k),k);
32.   cout << "\n\nZadanie IIA2.";
33.   int m = 3; int n = 4;
34.   int** macierz = new int*[m];
35.   for(int i = 0; i < m; i++)
36.     macierz[i] = new int[n];
38.   macierz[0][0]=1;macierz[0][1]=-1;macierz[0][2]=1;macierz[0][3]=-1;
39.   macierz[1][0]=-1;macierz[1][1]=1;macierz[1][2]=-1;macierz[1][3]=1;
40.   macierz[2][0]=1;macierz[2][1]=-1;macierz[2][2]=1;macierz[2][3]=-1;
42.   cout << "\nwyjście: "<< (plusminus(macierz, m, n) ? "TAK" : "NIE");
44.   for(int i = 0; i < m; i++)
45.     delete[] macierz[i];
46.   delete[] macierz;
48.   cout << "\n\nZadanie IIA3.";
49.   Dzien* dzien = stworzDzien(12,30);
50.   int h = 12;
51.   m = 12;
52.   cout << "\n\nwejście: (dzień) ";
53.   wypiszDzien(dzien);
54.   cout << "\n (godzina) " << h << ":" << m;
55.   cout << "\nwyjście: "<< (czyPoprawny(dzien, h, m) ? "TAK" : "NIE");
56.  
57.   delete[] dzien->m;
58.   dzien = stworzDzien(14,20);
59.   h=14; m=0;
60.   cout << "\n\nwejście: (dzień) ";
61.   wypiszDzien(dzien);
62.   cout << "\n (godzina) " << h << ":" << m;
63.   cout << "\nwyjście: "<< (czyPoprawny(dzien, h, m) ? "TAK" : "NIE");
65.   h=0; m=21;
66.   cout << "\n\nwejście: (dzień) ";
67.   wypiszDzien(dzien);
68.   cout << "\n (godzina) " << h << ":" << m;
69.   cout << "\nwyjście: "<< (czyPoprawny(dzien, h, m) ? "TAK" : "NIE");
71.   delete[] dzien->m;
72.   delete dzien;
74.   cout << "\n\nZadanie IIA4.";
76.   char* napis1 = new char[8];
77.   napis1[0]='A';napis1[1]='B';napis1[2]='A';napis1[3]='A';napis1[4]='C';napis1[5]='A';napis1[6]='B';napis1[7]='\0';
78.   cout << "\n\nwejście: " << napis1 << "\nwyjście: "<< rzadko(napis1);
80.   napis1[0]='A';napis1[1]='B';napis1[2]='B';napis1[3]='B';napis1[4]='A';napis1[5]='A';napis1[6]='B';napis1[7]='\0';
81.   cout << "\n\nwejście: " << napis1 << "\nwyjście: "<< rzadko(napis1);
83.   delete[] napis1;
84.   cout << "\n\n";
85.   system("pause");
86.   return 0;
87. }

• Kod źródłowy Rozwiązanie