Zadanie 1. Zera binarne

Paweł pracuje jako dyplomata w ambasadzie Bajtocji. W związku z rosnącym napięciem między Bajtocją a Terabajtami Górnymi został poproszony przez swój rząd o przekazanie Terabajtczykom wiadomości zapisanej w pliku depesza.txt.

W pliku depesza.txt znajduje się 100 liczb naturalnych, zapisanych w systemie dziesiętnym, o długości od 3 do 10 cyfr, każda w osobnej linii.

R15DSt8m5pddd

Przycisk do pobrania pliku TXT z treścią zadania.

Plik TXT o rozmiarze 734.00 B w języku polskim

Niestety języki obu krajów istotnie się różną – Bajtocja używa systemu dziesiętnego, natomiast Terabajty systemu binarnego. W dodatku wyrazy zawierające tyle samo lub więcej jedynek niż zer są uznawane w Terabajtach powszechnie za obraźliwe i lekceważące.

Napisz program, który przetłumaczy dane z pliku depesza.txt do systemu binarnego, pomijając te, które mogłyby zostać odebrane jako obraźliwe, a wynik zapisze do pliku konwersja.txt.

Do oceny oddajesz:

  • plik konwersja.txt (plik tekstowy zawierający liczby z pliku depesza.txt, które spełniają warunki zadania, zapisane w systemie binarnym, każda liczba w osobnej linii),

  • plik(i) z komputerową realizacją zadania (kodem programu).

Przedstaw rozwiązanie zadania w postaci programu w języku C++, Java lub Python.

Rozwiązanie

Na egzaminie maturalnym z informatyki każdy uczeń ma możliwość wybrania jednego z dostępnych języków programowania. Z tego powodu nie będziemy dokonywać implementacji rozwiązania zadania w konkretnym języku. Zamiast tego przedstawimy je za pomocą pseudokodu.

Na początku wczytujemy dane z pliku do tablicy. Będzie ona przechowywała liczby naturalne. Każdą liczbę zapisaną w systemie dziesiętnym przekonwertujemy do systemu binarnego. Tworzymy pętlę dla przechodzącą po wszystkich liczbach z pliku:

Linia 1. liczby otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów depesza kropka txt cudzysłów. Linia 3. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek.

Najpierw przeprowadzamy konwersję liczby naturalnej do systemu dwójkowego. Podczas konwersji zliczamy zera w postaci binarnej danej liczby. Po wykonaniu algorytmu sprawdzimy, czy w systemie dwójkowym w danej liczbie występuje więcej zer niż jedynek. Jeżeli się tak stanie, zapiszemy ją do pliku wynikowego. Do przechowywania wartości liczby zer użyjemy zmiennej licznik_zer.

Linia 1. liczby otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów depesza kropka txt cudzysłów. Linia 3. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 4. licznik podkreślnik zer ← 0.

Przystępujemy do konwersji liczby dziesiętnej na zapis w systemie binarnym. Deklarujemy zmienną postac_bin przechowującą liczbę dwójkową jako łańcuch znaków. Dopóki liczba w systemie dziesiętnym jest większa od 0, dopisujemy jej resztę z dzielenia przez 2 na początek zmiennej postac_bin, a następnie dzielimy całkowitoliczbowo przez 2. Aby skorzystać z konkatenacji napisów, użyjemy funkcji napis(), konwertującej liczbę całkowitą do łańcucha znaków. Jej implementacja jest dostępna w każdym języku programowania używanym na maturze.

Ważne!

Do wczytania danych z pliku nie potrzebujemy koniecznie tablicy. Można je również wczytywać po jednym wierszu i od razu dokonywać konwersji na system binarny.

Linia 1. liczby otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów depesza kropka txt cudzysłów. Linia 3. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 4. licznik podkreślnik zer ← 0. Linia 5. postac podkreślnik bin ← cudzysłów cudzysłów. Linia 6. dopóki liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 przecinek wykonuj dwukropek. Linia 7. reszta ← liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy mod 2. Linia 8. postac podkreślnik bin ← napis otwórz nawias okrągły reszta zamknij nawias okrągły plus postac podkreślnik bin. Linia 9. liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy ← liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy div 2.

Operatory div oraz mod oznaczają odpowiednio dzielenie całkowitoliczbowe oraz resztę z dzielenia.

Podczas konwersji możemy zliczać występujące w postaci binarnej zera. Zapiszmy odpowiednią instrukcję jeżeli:

Linia 1. liczby otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów depesza kropka txt cudzysłów. Linia 3. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 4. licznik podkreślnik zer ← 0. Linia 5. postac podkreślnik bin ← cudzysłów cudzysłów. Linia 6. dopóki liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 przecinek wykonuj dwukropek. Linia 7. reszta ← liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy mod 2. Linia 8. postac podkreślnik bin ← napis otwórz nawias okrągły reszta zamknij nawias okrągły plus postac podkreślnik bin. Linia 9. liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy ← liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy div 2. Linia 10. jeżeli reszta znak równości 0 dwukropek. Linia 11. licznik podkreślnik zer ← licznik podkreślnik zer plus 1.

Po zakończeniu konwersji do systemu binarnegosystem binarnysystemu binarnego sprawdzamy warunek, czy liczba zer jest większa od liczby jedynek. Korzystamy przy tym z funkcji dlugosc, zwracającej długość łańcucha znaków, której implementacja również jest dostępna w każdym języku programowania używanym na maturze.

Linia 1. liczby otwórz nawias kwadratowy 0 kropka kropka 99 zamknij nawias kwadratowy ← wczytaj dane z pliku cudzysłów depesza kropka txt cudzysłów. Linia 3. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek. Linia 4. licznik podkreślnik zer ← 0. Linia 5. postac podkreślnik bin ← cudzysłów cudzysłów. Linia 6. dopóki liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 przecinek wykonuj dwukropek. Linia 7. reszta ← liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy mod 2. Linia 8. postac podkreślnik bin ← napis otwórz nawias okrągły reszta zamknij nawias okrągły plus postac podkreślnik bin. Linia 9. liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy ← liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy div 2. Linia 10. jeżeli reszta znak równości 0 dwukropek. Linia 11. licznik podkreślnik zer ← licznik podkreślnik zer plus 1. Linia 12. jeżeli licznik podkreślnik zer zamknij nawias ostrokątny dlugosc otwórz nawias okrągły postac podkreślnik bin zamknij nawias okrągły minus licznik podkreślnik zer dwukropek. Linia 13. dopisz postac podkreślnik bin na koniec pliku cudzysłów konwersja kropka txt cudzysłów.

W ten sposób odpowiednio przetłumaczyliśmy wiadomość na system binarny.

Ważne!

W pseudokodzie wykorzystaliśmy funkcję napis. Ma one swoje odpowiedniki w językach programowania.

Odpowiedniki funkcji napis:

  • C++: to_string()

  • Java: Integer.toString()

  • Python: str()

Odpowiedź do zadania

konwersja.txt

R1Edlqz9cOTJ1

Przycisk do pobrania pliku TXT z wynikiem zadania.

Plik TXT o rozmiarze 883.00 B w języku polskim

Słownik

system binarny
system binarny

pozycyjny system liczbowy, którego podstawą jest liczba 2, a do zapisu liczb potrzebne są tylko dwie cyfry: 0 i 1; używany w matematyce, informatyce i elektronice, gdzie minimalizacja liczby stanów do dwóch pozwala na prostą implementację sprzętową (stany: wyłączony i włączony)