Kolokwium 1 2014/15

Treści zadań

• Kolokwium grupa A
• Kolokwium grupa B

Rozwiązanie

Zadanie IA1

Przedstawione zadanie można podzielić na dwa etapy: szukanie k-tej liczby pierwszej oraz wywołanie pozostałych funkcji, aby uzyskać wynik.

Etap I - szukanie k-tej liczby pierwszej

Zadeklarujmy zmienną i, która będzie przechowywać ostatnia znalezioną liczbę pierwszą. Przypiszmy do zmiennej i liczbę 2, która jest liczbą pierwszą. Wyszukiwania liczby pierwszej przeprowadzimy w pętli while. Warunkiem jest, aby k > 1. To zagwarantuje nam, że dla k = 1 k-ta liczba pierwsza została znaleziona. W pętli wywołamy kolejną pętle, tym razem do while, która będzie tak długo zwiększać i, aż i będzie liczbą pierwszą. Po jej zakończeniu zmniejszymy k o 1, ponieważ znaleźliśmy kolejną liczbę pierwszą.

Etap II - wypisanie wyniku

Należy pobrać wartość fun(i), a następnie sprawdzić czy wynik tej funkcji jest liczbą pierwszą.

1. bool g(int k) {
2.   int i = 2;
3.   while (k > 1) {
4.     do {
5.       i++;
6.     } while (!czyPierwsza(i));
7.     k--;
8.   }
9.   return czyPierwsza(fun(i));
10. }

Zadanie IB2

Rozwiązanie opiera się na podobnym schemacie co IA1, ale warto je omówić. Przede wszystkim teraz za każdym razem jak znajdziemy liczbę pierwszą to musimy przechowywać w zmiennej czy wartość fun dla tej liczby pierwszej jest dodatnia. W tym celu należy zadeklarować zmienną np. licznik przed wywołaniem pierwszej pętli.

1. int g(int k) {
2.   int licznik = 0, i = 1;
3.   do {
4.     do {
5.       i++;
6.     } while (!czyPierwsza(i));
7.     if (fun(i) > 0)
8.       licznik++;
9.     k--;
10.   } while (k > 0);
11.   return licznik;
12. }

Tym razem zmienna i przyjmuje wartość 1 id razu rozpoczynamy pętle do while, a następnie drugą dzięki temu gwarantujemy, że pierwsza znaleziona to 2. Tu właśnie należy dopatrywać się dlaczego i na początku musi wynieść 1. Pętla do while gwarantuje, że nawet jeśli i jest liczbą pierwszą to szukamy następnej liczby pierwszej. Następnie sprawdzamy czy wartość fun(i) jest dodatnia. Na koniec zmniejszamy ilość szukanych liczb pierwszych o 1 i sprawdzamy czy k > 0 czyli czy mamy szukać następną liczbę pierwszą. Na sam koniec zwracamy wartość licznika.

Dla ciekawskich: linijki 7. i 8. możemy zapisać jako:

1. licznik += (fun(i) > 0);

Zadanie IA2 i IB3

Schemat do wyliczania punktów jest dla obu zadań identyczny tj. musimy pętlą for przejść przez całą tablicę. Porównania zliczyć do zmiennej licznik o początkowej wartości 0 i zwrócić wynik. Jedyną trudnością w tym zadaniu jest odczytanie wartości karty na i-tym polu któregoś z gracza, dlatego też wartość pobranej karty przekażemy do dodatkowej funkcji, która zwróci odpowiednią wartość. Główna funkcja (dla obu zadań) wygląda tak:

1. int wojna(int* g1, int* g2) {
2.   int suma = 0;
3.   for (int i = 0; i < 26; i++) {
4.     if (wartosc(g1[i]) > wartosc(g2[i])) {
5.       suma++;
6.     }
7.     else if (wartosc(g1[i]) < wartosc(g2[i])) {
8.       suma--;
9.     }
10.   }
11.   return suma;
12. }

Różnice następują w wyliczaniu co to za karta, dlatego też w zadaniu IA2 zapisujemy funkcję wartość jako:

1. int wartosc(int n) {
2.   return n / 4;
3. }

Warto zauważyć, że cztery kolejne karty mają tą samą wartość, więc dzieląc ich indeks przez 4 i zaokrąglając w dół i dodając 2 otrzymujemy ich wartość. W C++ zaokrąglanie w dół uzyskujemy przez dzielenie wartości całkowitych, a dodawanie 2 nie ma sensu przy porównaniu.

Natomiast dla grupy B wartości dla 2 mamy dla k = {0, 13, 26, 39} jeśli by się temu przyjrzeć to wartość karty to reszta z dzielenia indeksu przez 13:

1. int wartosc(int n) {
2.   return n % 13;
3. }

Zadanie IA3 i IB4

Załóżmy, że numerowanie dni tygodnia lub miesięcy nie zaczynamy od 1, ale od 0 wtedy np. poniedziałek 0, wtorek 1 ... niedziela 6, a w przypadku miesięcy styczeń 0, luty 1 ... grudzień 11. W ten sposób o wiele łatwiej wyliczyć nam przesunięcie o k, ponieważ będziemy się przesuwać w określonym przedziale czyli (a+k)%n, gdzie a to początkowy miesiąc / dzień tygodnia, a n = 12 / n = 7. Oczywiście należy pamiętać, że na początku musimy skonwertować dzień tygodnia do naszego systemu tj. odjąć jeden, a po wyliczeniu to jeden dodać.

1. int* dodajMiesiace(int *x, int n, int *y, int k) {
2.   int* tab = new int[n];
3.   for (int i = 0; i < n; i++)
4.     tab[i] = ((x[i] - 1 + y[i%k]) % 12) + 1;
5.   return tab;
6. }

A dla zadania IB4 (zmieniamy tylko nazwę i 12 na 7 ...):

1. int* dodajDniTygodnia(int *x, int n, int *y, int k) {
2.   int* tab = new int[n];
3.   for (int i = 0; i < n; i++)
4.     tab[i] = ((x[i] - 1 + y[i%k]) % 7) + 1;
5.   return tab;
6. }

Zadanie IA4 i IB1

Pomocna w tym zadaniu okazuje się funkcja modulo czyli reszta z dzielenia. Przede wszystkim zadeklarujmy nową tablicę o wielkości n, a następnie wywołajmy pętle for dla każdego elementu. k-ty wyraz ma się znaleźć na 0 indeksie. Jeśli dodamy po obu stronach jakąś liczbą a to wyraz k+a, będzie na a miejscu. Łatwo jednak zauważyć, że k+a wykroczy poza zakres tablicy. W celu uniknięcia tego użyjemy modulo, ponieważ reszta dzielenia k+a przez n nigdy nie wyjdzie poza zakres tablicy, a kiedy będziemy chcieli pobrać n-ty wyraz to pobierzemy pierwszy (tj. indeksie 0).

1. int* przesunL(int *x, int n, int k) {
2.   int* tab = new int[n];
3.   for (int i = 0; i < n; i++)
4.     tab[i] = x[(k + i) % n];
5.   return tab;
6. }

Dla zadania IB1 sytuacja jest bardzo podobna z tą różnicą, że pod k podstawiamy n - k.

1. int* przesunL(int *x, int n, int k) {
2.   int* tab = new int[n];
3.   for (int i = 0; i < n; i++)
4.     tab[i] = x[(n - k + i) % n];
5.   return tab;
6. }

Dla ciekawskich to warto zauważyć, że mając już np. przesunL to, aby uzyskać przesunP to wystarczy wywołać przesunL ze zmienionym parametrem k na n - k tj.:

1. int* przesunP(int *x, int n, int k) {
2.   return przesunL(x, n, n - k);
3. }