C++
FRAKTAL

Programowanie i algorytmy

Matura 2015 - nowa formuła, zadanie 4

powrót

Rozwiązanie zadania 4 - matura 2015 - nowa formuła

Treść zadania:

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.

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

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

//funkcja sprawdza, czy liczba ma wiecej zer
bool czy_wiecej(string liczba)
{
	int licz = 0;
	for(int i = 0; i < liczba.size(); i++)
		if(liczba[i]=='0') ++licz;
		else	--licz;
	
	//jesli wiecej jest 0
	if(licz > 0) return true;
	
	return false;
}

int main()
{
	ifstream in("liczby.txt");
	
	if(in.is_open())
	{
		string liczba; //wczytana liczba
		int ile = 0; 
		
		for(int i=0; i<1000; i++)
		{
			in>>liczba;
			if(czy_wiecej(liczba)) ++ile;	
		}
		
		cout<<"Takich liczb jest: "<<ile<<endl;
		cin.get();
		in.close();
	}
	else
		cout<<"Problem z otwarciem pliku \"liczby.txt\"";
	
		
	return 0;
}
 

 

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

Liczba w zapisie binarnym dzieli się przez dwa, jeśli na końcu stoi co najmniej jedno 0, natomiast przez osiem gdy tych zer jest co najmniej trzy.

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

bool czy_przez_dwa(string liczba)
{
	//sprawdzenie, czy ostatni znak jest 0
	if(liczba[liczba.size()-1]=='0') 
		return true;
	return false;
}

bool czy_przez_osiem(string liczba)
{
	//sprawdzenie, czy trzy ostatnie znaki to 0
	if(liczba[liczba.size()-1]=='0'&&
	liczba[liczba.size()-2]=='0'&&
	liczba[liczba.size()-3]=='0') 
		return true;
	//gwarantuje sie, ze sa co najmniej trzy znaki
	return false;
}
int main()
{
	ifstream in("liczby.txt");
	
	if(in.is_open())
	{
		string liczba; //wczytana liczba
		int przez_dwa = 0, przez_osiem = 0; 
		
		for(int i=0; i<1000; i++)
		{
			in>>liczba;
			if(czy_przez_dwa(liczba)) ++przez_dwa;
			if(czy_przez_osiem(liczba)) ++przez_osiem;	
		}
		
		cout<<"Liczb podzielnych przez 2 jest: "<<przez_dwa<<endl;
		cout<<"Liczb podzielnych przez 8 jest: "<<przez_osiem<<endl;
		cin.get();
		in.close();
	}
	else
		cout<<"Problem z otwarciem pliku \"liczby.txt\"";
	
		
	return 0;
}
 

 

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

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int main()
{
	ifstream in("liczby.txt");
	
	if(in.is_open())
	{
		//liczba - wczytana liczba z pliku
		//pomMin - przechowuje najmniejsza liczbe
		//pomMax - przechowuje najwieksza liczbe
		string liczba, pomMin, pomMax;
		
		//i - zlicza wiersze, nrMin - wiersz z najmniejsza liczba
		//nrMax - wiersz z najwieksza liczba
		int nrMin = 1, nrMax = 1;
		
		in>>liczba; //wczytanie pierwszej liczby
		
		pomMin = pomMax = liczba;
		
		for(int i=2; i<1001; i++)
		{
			in>>liczba;
			//szukanie maksymalnej --------------------------------------
			//jesli wczytana liczba ma wiecej znaków
			//oznacza to, ze jest wieksza
			if(liczba.size() > pomMax.size())
			{
				pomMax = liczba; //zapamietaj ja
				nrMax = i; //zapamietaj wiersz
			} 
			else
				//jesli maja po tyle samo znaków
				//to trzeba sprawdzic, która jest wieksza
				//operator > porównuje leksykograficznie
				if(liczba.size()==pomMax.size())
					if(liczba > pomMax)
					{
						//zapamietujemy ja
						pomMax = liczba;
						//oraz jej pozycje
						nrMax = i;
					}
			//szukanie minimalnej --------------------------------------
			//jesli wczytana liczba ma mniej znaków
			//oznacza to, ze jest mniejsza
			//operator < porównuje leksykograficznie
			if(liczba.size() < pomMin.size())
			{
				pomMin = liczba; //zapamietaj ja
				nrMin = i; //zapamietaj wiersz
			} 
			else
				//jesli maja po tyle samo znaków
				//to trzeba sprawdzic, która jest mniejsza
				if(liczba.size()==pomMin.size())
					if(liczba < pomMin)
					{
						//zapamietujemy ja
						pomMin = liczba;
						//oraz jej pozycje
						nrMin = i; 
					}	
		}
		
		cout<<"Najmniejsza znajduje sie we wierszu: "<<nrMin<<endl;
		cout<<"Najwieksza znajduje sie we wierszu: "<<nrMax<<endl;
		cin.get();
		in.close();
	}
	else
		cout<<"Problem z otwarciem pliku \"liczby.txt\"";
	
		
	return 0;
}