Programowanie i algorytmy

Jesteś tutaj: Start Rozwiązania zadań maturalnych Zad. 4 2015 NF

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

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'&amp;&amp;
  liczba[liczba.size()-2]=='0'&amp;&amp;
  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;
}