Matura z informatyki 2015 – Liczby binarne (C++)

Czas czytania: 2 minut

Dzisiaj pobawimy się dużymi liczbami binarnymi. Słyszałeś o czymś takim, prawda? Z zadaniem, które dzisiaj rozwiążemy maturzyści musieli się zmierzyć w roku 2015. Zadanie „Liczby binarne” wymaga od zdającego znajomości kilku sztuczek, które są nieodzowne do stworzenia prawidłowego rozwiązania punktowanego maksymalnie. (Jeśli chcesz zajrzeć do rozwiązań innych zadań, zapraszam do spisu treści).

Wyspani, najedzeni i gotowi do zwiększonego wysiłku umysłowego? No to zaczynamy 🙂

Zadanie 4 – Liczby binarne

W pliku liczby.txt znajduje się 1000 liczb naturalnych zapisanych binarnie. Każda liczba zapisana jest w osobnym wierszu. Pierwsze pięć wierszy zawiera następujące liczby:

11010100111
11110111111011101
1010100111010100
1101111111111111111111010100101010101001
1010110011001101010011110101010101010111

Każda liczba binarna zawiera co najwyżej 250 cyfr binarnych, co oznacza, że w wielu językach programowania wartości niektórych z tych liczb nie da się zapamiętać w pojedynczej zmiennej typu całkowitoliczbowego, np.: w języku C++ w zmiennej typu int.

Napisz program który da odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wynik4.txt, a każdą odpowiedź poprzedź numerem oznaczającym odpowiednie zadanie.

Kod uniwersalny dla wszystkich podpunktów

Twórcy tego zadania wprowadzili kilka komplikacji i pułapek. Tak jak zostało powiedziane w treści zadania, niektóre liczby po konwersji nie zmieszczą się w typie całkowitoliczbowym. Ba – nie zmieszczą się nawet w long long int. Co możemy zrobić? Jak rozwiązać ten problem?

Dobrym pomysłem wydaje się przechowywanie każdej z liczb w formie ciągu znaków. I tak właśnie zrobimy 🙂

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

vector<string> readFile(const string filename) {
vector<string> readen;
ifstream file;
file.open(filename);
if(!file.is_open()) {
cout<<"Nie udało się otworzyć pliku "+filename<<endl;
return readen;
}
while(file.peek()!=EOF) {
string line;
getline(file,line);
readen.push_back(line);
}
return readen;
}

Jeśli chcesz poznać dokładniejsze omówienie tej funkcji, zapraszam do lektury rozwiązania zadania Wega z roku 2018, gdzie funkcja wczytująca plik była identyczna.

Zadanie 4.1 (0-3)

Podaj, ile liczb z pliku liczby.txt ma w swoim zapisie binarnym więcej zer niż jedynek.

Przykład: Dla zestawu liczb: 
101011010011001100111
10001001
1000000
101010011100
100010
wynikiem jest liczba 3 (3 podkreślone liczby mają w swoim zapisie więcej zer niż jedynek).

Rozwiązanie:

26
27
28
29
30
31
32
33
34
35
36
37
38

int countNumbersWithZeroes(vector<string> numbers) {
int correctNumbers = 0;
for(unsigned int i = 0;i<numbers.size();i++) {
int zero = 0;
int ones = 0;
for(unsigned int j = 0;j<numbers[i].size();j++) {
if(numbers[i][j] == '0') zero++;
else if(numbers[i][j] == '1') ones++;
}
if(zero>ones) correctNumbers++;
}
return correctNumbers;
}

Powyższa funkcja stanowi rozwiązanie zadania. Co ona robi?

Jako argument przyjmujemy vector przechowujący wszystkie pobrane liczby. Zmienna correctNumbers będzie przechowywała wynik obliczeń. W dalszej części znajdują się dwie pętle for.

Pętla zewnętrzna pozwala nam przeanalizować każdą z 1000 liczb. Dla każdego z ciągów binarnych liczymy ilość zer i ilość jedynek. Na samym końcu porównujemy te wartości. Jeśli zer jest więcej – zwiększamy ilość „prawidłowych liczb” o 1.

I … to tyle. Jest to najprostsze i najprzyjemniejsze zadanie z tego zestawu.

Zadanie 4.1. - kompletne rozwiązanie

Zadanie 4.2 (0-3)

Podaj, ile liczb w pliku liczby.txt jest podzielnych przez 2 oraz ile liczb jest podzielnych przez 8.

Przykład: Dla zestawu liczb:
101011010011001100000 (*), (**) 
10001001 
100100 (*)
101010010101011011000 (*), (**)
100011

trzy liczby są podzielne przez 2 (*) i dwie liczby są podzielne przez 8 (**)

Rozwiązanie

W tym zadaniu najważniejszy jest pomysł. Musimy się zastanowić, co to znaczy że liczba jest podzielna przez 2? Co decyduje o tym, że dana liczba binarna jest podzielna przez takie a nie inne liczby? Jakie cechy charakterystyczne możemy zauważyć?

Pomysł na rozwiązanie

Najpierw zobaczmy, jak to wygląda w systemie dziesiętnym, którego używamy na co dzień. Pamiętasz z pewnością regułki z podstawówki, które kułeś na pamięć, odnoszące się do podzielności liczb. Np.: Liczba jest podzielna przez 2 kiedy na jej końcu znajduje się 0,2,4,6 albo 8 (czyli cyfra parzysta). Liczba jest podzielna przez 4 gdy dwie ostatnie cyfry tworzą liczbę podzielną przez 4, itd. Jak to się ma do systemu binarnego?

Jak wiemy, kolejne cyfry liczby binarnej to kolejne potęgi dwójki. Zapiszmy sobie przykładową liczbę binarną.

$11101110=1*2^7+1*2^6+1*2^5+1*2^3+1*2^2+1*2^1$

Nie przeliczając powyższej liczby na system dziesiętny, spróbujmy odgadnąć zasady podzielności. Zauważ, że zapis liczby dziesiętnej w systemie binarnym to suma kolejnych potęg dwójki. Warto spostrzec: skoro 2^3=8, to każda kolejna potęga dwójki będzie podzielna przez 8. 16 jest podzielne przez 8, 32 także itd. Tak samo jest z dwójką. Czwórka i wszystkie większe od niej potęgi dwójki są automatycznie podzielne przez 2.

Powstaje pytanie, czy suma liczb podzielnych przez 8 dalej będzie podzielna przez 8? Sprawdźmy. Przeprowadzimy prosty dowód.

$\text{Oznaczmy przez x dowolna liczbe. Dodajemy do siebie 3 liczby podzielne przez 8}$

$8x+8x+8x=24x$

$\text{24 jest podzielne przez 8, co konczy dowod}$

Jeśli natomiast do liczby podzielnej przez 8 dodamy liczbę niepodzielną przez 8, to w efekcie otrzymamy liczbę niepodzielną przez 8 (na to dowód możesz sobie przeprowadzić we własnym zakresie).

Posiadamy już doświadczenie, które pozwala odpowiedzieć na pytanie: jakie warunki musi spełniać liczba podzielna przez 8? Otóż, którykolwiek z bitów o wadze większej niż bit określający ósemkę musi być równy 1. Z drugiej strony wszystkie bity o wadze mniejszej muszą być równe 0.

Powolnym, dostojnym krokiem zbliżamy się do prawidłowego rozwiązania postawionego przed nami problemu. Ogromny wysiłek umysłowy który poczyniliśmy przeprowadzając powyższe rozumowanie opłacał się. Prawie opracowaliśmy gotowy algorytm. Spróbujmy napisać trochę kodu. Będzie on bardzo prosty, o wiele prostszy niż matematyka, z którą przeprowadziliśmy zwycięską bitwę kilka chwil wcześniej.

28
29
30
31
32
33
34

int countDivisibleBy2(vector<string> numbers) {
int counter = 0;
for(string number : numbers) {
if(number.size()>2 && number[number.size()-1] == '0') counter++;
}
return counter;
}

Powyższy kod jest wręcz banalny. Przechodzimy całą tablicę liczb. Dla każdej sprawdzamy, czy ostatnia cyfra jest równa 0. Jeśli tak, to liczba jest podzielna przez 2.

35
36
37
38
39
40
41
42
43
44

int countDivisibleBy8(vector<string> numbers) {
int counter = 0;
for(string number : numbers) {
if(number.size()>4 &&
number[number.size()-1]=='0' &&
number[number.size()-2]=='0' &&
number[number.size()-3]=='0') counter++;
}
return counter;
}

Jak wygląda sytuacja w przypadku sprawdzania podzielności przez 8? Zauważamy, że konstrukcja jest podobna. Aczkolwiek if dosyć mocno spuchł. Tak jak rozważaliśmy, musimy sprawdzić czy trzy ostatnie cyfry (odpowiadające wagom 1,2,4) są równe 0. Jeśli tak, to liczba musi być podzielna przez 8.

Zadanie wykonane 🙂

Zadanie 4.2. - kompletne rozwiązanie

Zadanie 4.3. (0-6)

Znajdź najmniejszą i największą liczbę w pliku liczby.txt. Jako odpowiedź podaj numery wierszy, w których się one znajdują.

Przykład: Dla zestawu liczb:
101011010011001100111
10001001011101010
1001000
101010011100
1000110

Najmniejsza liczba to 1000110
Największa liczba to: 101011010011001100111
Prawidłowa odpowiedź dla powyższego przykładu to: 5, 1.

Rozwiązanie:

Zadanie wydaje się dosyć skomplikowane. Mogłaby to potwierdzać duża ilość przydzielanych punktów. Ale w istocie jest dosyć proste – tym bardziej, że większą część roboty odwalą za nas wbudowane w bibliotekę standardową języka C++ mechanizmy.

Jak możemy porównywać liczby zapisane w stringach? Otóż, string posiada przeciążone operatory < i >. Jeden ciąg znaków jest mniejszy od drugiego, jeśli w kolejności „alfabetycznej” znajduje się on wcześniej. „Alfabetycznie” ciąg 111 będzie wcześniej niż 100. Czy rzeczywiście wystarczy prosta pętla, która porównuje ciągi znaków tak jak liczby? Niekoniecznie.

Zwróćmy uwagę, że liczby mogą być różnej długości. Dodatkowo, niektóre z nich mogą być na początku dopełnione kilkoma zerami, np.: 00011101. Jeśli wykonamy porównanie np.: z liczbą 11 okaże się że 11 jest większa! A to nie jest przecież prawda. Jak możemy pokonać tę trudność? Wystarczy zastosować dopełnienie zerami 🙂

28
29
30
31
32
33
34
35

string fillWithZero(string data,int length) {
string newstring = data;
while(length>0) {
newstring.insert(0,"0");
length--;
}
return newstring;
}

Zasada działania powyższej funkcji jest niezwykle prosta. Jako argument przekazujemy liczbę do dopełnienia oraz ostateczną długość. Następnie w pętli while dodajemy zera na początku dopóty, dopóki nie wyzerujemy zmiennej length. Z pomocą tej funkcji możemy napisać algorytm wyszukiwania minimum.

36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

int findMin(vector<string> data) {
string minimum = data[0];
int pos = 0;
for(int i = 1;i<data.size();i++) {
if(minimum.size()<data[i].size()) {
minimum = fillWithZero(minimum,data[i].size()-minimum.size());
}
else if(minimum.size()>data[i].size()) {
data[i] = fillWithZero(data[i],minimum.size()-data[i].size());
}
if(data[i]<minimum) {
minimum = data[i];
pos = i;
}
}
pos+=1;
return pos;
}

Funkcja wygląda bardzo podobnie do zwykłego wyszukiwania minimum w tablicy. Podobny algorytm zastosowaliśmy w rozwiązaniu zadania Piksele. Jedyną różnicą jest wywoływanie umieszczonej na poprzednim listingu funkcji dopełnienia zerami. Posiadamy zmienną minimum typu string, w której przechowujemy aktualne minimum. Przechodzimy tablicę element po elemencie. Dopełniamy zerami ciąg o mniejszej długości i porównujemy. Jeśli aktualnie analizowany element jest mniejszy, to aktualizujemy zmienną minimum. Zapisujemy także pozycję elementu.

Możesz się zastanowić, dlaczego na samym końcu, tuż przed zwróceniem wyniku zwiększamy zawartość pos o 1? Kryje się tutaj bardzo prosty kruczek, przez który możemy stracić 6 punktów za prawidłowo rozwiązane zadanie 😉 Otóż, w przykładzie znajdującym się w treści zadania pierwsza linijka tekstu to pozycja pierwsza, a dla naszej funkcji pierwsza linijka to linijka zerowa 🙂 Musimy skorygować ten drobny niuans dodając jedynkę do naszego rezultatu.

Kompletne rozwiązanie - Zadanie 4.3

Gratuluję

Że udało ci się dotrzeć do końca 🙂 Mam nadzieję, że nauczyłeś się czegoś pożytecznego 🙂 Jeśli chcesz zobaczyć analizę innych zadań z ubiegłych matur z informatyki, zapraszam do kompendium rozwiązań maturalnych 🙂

Gdybym przypadkiem popełnił jakiś błąd który zauważyłeś, poinformuj o tym w komentarzu. Jeśli masz inne uwagi, także będę wdzięczny za opinię 🙂

Do zobaczenia 🙂

Niestety, nie mamy jeszcze podobnych artykułów do tego, który właśnie przeczytałeś :( Zajrzyj w przyszłości, a na pewno coś się znajdzie :)

Zadanie 4 – Liczby binarne

Kod uniwersalny dla wszystkich podpunktów

Zadanie 4.1 (0-3)

Rozwiązanie:

Zadanie 4.2 (0-3)

Rozwiązanie

Pomysł na rozwiązanie

Zadanie 4.3. (0-6)

Rozwiązanie:

Gratuluję

Dodaj komentarz Anuluj pisanie odpowiedzi