Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Suma bitów danej liczby


Zad. 4. Napisz funkcję, która zwróci prawdę, w przypadku, gdy suma cyfr danej liczby, oraz suma cyfr tej liczby w notacji binarnej będzie taka sama, oraz:

a) wyświetli wszystkie takie liczby z przedziału <n, m>, gdzie n i m podajemy z klawiatury, które spełniają kryteria zadania.

Zrealizuj to zadanie za pomocą trzech funkcji:

  • funkcji zwracającej sumę cyfr w systemie dziesiętnym
  • funkcji zwracającej sumę cyfr w systemie binarnym
  • funkcji zwracającej prawdę lub fałsz, w zależności ok spełnienia kryteriów

Wejście

Liczba całkowita mieszcząca się w zmiennej typu long long.


Wyjście

Komunikat określający, czy dana liczba spełnia kryteria zadania, oraz sumy cyfr w odpowiednich systemach.

 

Rozwiązanie

Aby wyłuskać cyfry danej liczby w systemie dziesiętnym postępujemy zgodnie z zasadą:

$$cyfra = liczba\ mod\ 10$$

$$liczba = liczba\ div\ 10$$

Np. dla liczby 123 mamy:

$$cyfra = 123\ mod\ 10 = 3$$

$$123\ div\ 10 = 12$$

Podaną czynność wykonujemy do momentu, gdy liczba osiągnie wartość 0, gdzie

mod - reszta z dzielenia
div - dzielenie całkowite.

Dla systemu binarnego postępujemy analogicznie podstawiając zamiast 10 liczbę 2.

Sposób drugi dla systemu binarnego wykonuje się według następującej idei:

cyfra = liczba & 1;

liczba = liczba >>1;

Aby wyłuskać ostatnią cyfrę, wystarczy wykonać działanie (operacje bitowe):

 

  1001101
  1
& 0000001

 

Gdy ostatni bit jest równy 1, to działanie 1 & 1 = 1, natomiast gdy ma wartość 0, to mamy 0 & 1 = 0, w ten sposób uzyskujemy ostatni bit danej liczby.

Aby skrócić liczbę o jeden bit, należy przesunąć ją w prawą stronę o 1 za pomocą operatora ">>". Popatrzmy na przykład:

 

(1000111110)2 >> 1 = (100011111)2

 

Rozwiązanie

#include <iostream>
#include <cstdlib>

using namespace std;

int suma_dec(long long liczba)
{
	int s=0;

	while(liczba>0)
	{
		s+=liczba%10;
		liczba/=10;
	}
return s;
}

//pierwszy sposób
int suma_bin_1(long long liczba)
{
	int s=0;

	while(liczba>0)
	{
		s+=liczba%2;
		liczba/=2;
	}
return s;
}

//drugi sposób za pomocą operatorów bitowych
int suma_bin_2(long long liczba)
{
	int s=0;

	while(liczba>0)
	{
		s+=liczba&1;
		liczba>>=1;
	}

return s;
}

bool czy_rowne(int a,int b)
{
//jeśli a jest równe b to zwraca wartość true i wychodzi z funkcji
	if(a==b)return true; 

	return false;
}

int main()
{

	long long liczba;
	char opcja;

	do{	
		system("cls"); //czyszczenie ekranu

		cout<<"Podaj liczbę: ";
		cin>>liczba;
		cout<<endl;

		if(czy_rowne(suma_bin_2(liczba),suma_dec(liczba)))
			cout<<"Liczba "<<liczba<<" spełnia kryteria zadania";
		else
			cout<<"Liczba "<<liczba<<" nie spełnia kryteria zadania";

		cout<<endl<<endl;

		cout<<"Suma cyfr w systemie binarnym: "<<suma_bin_2(liczba)<<endl;
		cout<<"Suma cyfr w systemie dziesiętnym: "<<suma_dec(liczba)<<endl;

		cout<<endl;

		cout<<"Aby zakończyć wciśnij q, w przeciwnym razie dowolny znak ";

		cin>>opcja;

	}while(opcja!='q'); //po wciśnięciu q program kończy działanie

return 0;
}