Matura 2012 (maj). Zadanie 2. Diamenty

W sejfie jubilera znajduje się n diamentów wycenionych odpowiednio na d₁, …, d_n złotych, przy czym żadne dwa diamenty nie są w tej samej cenie. Jubiler nie ujawnia cen diamentów, co oznacza, że tylko on zna ceny d₁, …, d_n.
Dla zainteresowanych klientów jubiler wykonuje operację porównania cen diamentów: dla wskazanych numerów i oraz j podaje, czy diament o numerze i ma wyższą cenę, niż diament o numerze j.
Przyjmijmy następujący sposób oznaczania wyniku operacji porównania cen:
większe( i , j ) = prawda, gdy d₁ > d
większe( i , j ) = fałsz, gdy d₁ < d

1. Poniżej prezentujemy pewien algorytm korzystający z operacji porównania cen:

 Krok 1. j ← 0
 Krok 2. i ← 1
 Krok 3. dopóki i < n
   jeżeli większe(i, i i + 1) to j ← j + 1
   i ← i + 1
 Krok 4. wypisz j

Uzupełnij poniższą tabelę, podając wyniki działania powyższego algorytmu po jego wykonaniu dla wskazanych danych.

Komentarz:
Musimy podać wartość zmiennej j. Zmienna j jest zwiększona o jeden pod warunkiem, że funkcja większe(i,j) zwróci prawdą (true). Prawda jest wtedy, kiedy element i tablicy jest większy od elementów i+1, czyli element sprawdzany jest większe od elementu następnego.

Algorytm

#include <iostream>
#define N 4
using namespace std;
int d[N] = {1,2,3,4};
bool wieksze(int i, int j) {
  if (d[i]>d[j]) return true;
  else return false;
}
int main()
{
  int j=0;
  int i=0;
  while (i<N-1) {
    if (wieksze(i,i+1)) j++;
    i++;
  }
  cout << j << endl;
  return 0;
}

2. Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku programowania), który dla podanego ciągu cen diamentów znajduje numer diamentu o najwyższej cenie. W algorytmie zastosuj operację większe porównania cen dwóch diamentów.

Specyfikacja:

Dane:

n – liczba naturalna większa od zera oznaczająca liczbę diamentów
d₁, …, d_n – ceny diamentów o kolejnych numerach 1, 2, …, n; ceny dwóch różnych diamentów są różne

Wynik:

i – numer diamentu o najwyższej cenie

Algorytm:

#include <iostream>
#define N 4
using namespace std;
int d[N] = {2,5,1,2};
bool wieksze(int i, int maks) {
  if (d[i]>d[maks]) return true;
  else return false;
}
int main()
{
  int maks=0;
  int i=0;
  while (i<N-1) {
  if (wieksze(i,maks)) maks = i;
  i++;
 }
  cout << maks << endl;
  return 0;
}

Matura 2009 (maj). Zadanie 2. Ceny w systemach dziesiętnym i dwójkowym

W Dwójkolandii tradycyjnie ceny w sklepach są podawane w systemie dwójkowym. Ze względu na rosnący ruch turystów z innych krajów, gdzie wciąż obowiązuje system dziesiętny, rząd Dwójkolandii postanowił, że handlowcy mają obowiązek umieszczania cen w obu systemach.

1. Pomóż właścicielowi baru szybkiej obsługi uzupełnić obowiązujący cennik:

Wyjaśnienie:

1. Rozdzielamy liczbę na część całkowitą i część ułamokową.
2. Najpierw zajmiemy się częścią całkowitą, na przykładzie ceny:
   kakao
   111₍₂₎ = 1 * 2⁰ + 1 * 2¹ + 1 * 2² =  1 + 2 + 4 = 7₍₁₀₎
   kawa espresso:
   110₍₂₎ = 0 * 2⁰ + 1 * 2¹ + 1 * 2² = 0 + 2 + 4 = 6₍₁₀₎
   

Zamiana części całkowitej odbywa się za pomocą algorytmu:

Zamiana ceny w systemie binarnym na cenę w systemie dziesiętnym.
System dwójkowy jest najprostszym systemem pozycyjnym, w którym podstawa p = 2. System posiada dwie cyfry 0 i 1, zatem można je kodować bezpośrednio jednym bitem informacji. Wartość dziesiętna liczby zapisanej w naturalnym kodzie binarnym dana jest wzorem:
b_n-1b_n-2…b₂b₁b₀ = b_n-12^n-1 + b_n-22^n-2 + … + b₂2² + b₁2¹ + b₀2⁰
gdzie :
b – bit, cyfra dwójkowa 0 lub 1
n – liczba bitów w zapisie liczby
101011₍₂₎ = 2⁵ + 2³ + 2¹ + 2⁰ = 32 + 8 + 2 + 1 = 43₍₁₀₎

Zamiana ceny w systemie dziesiętnym na cenę w systemie binarnym.
W jednym kroku algorytmu wykonujemy czynności wyznaczenie reszty (%) z dzielenia przez dwa przekształcanej liczby oraz wykonujemy dzielenie całkowite przez dwa. Tę czynność wykonujemy tak długo, aż liczba dziesiętna będzie większa od 0 (zera).

3. Kolejnym krokiem jest zamiana części ułamkowej, na przykładzie ceny:

kakao
0,11(2) = 1 * 2^-1 + 1 * 2^-2 = 1/2 + 1/4 = 0,5 + 0,25 = 0,75₍₁₀₎

Zamiana ceny w systemie dziesiętnym na cenę w systemie binarnym w części ułamkowej.
Wykonujemy w taki sam sposób części całkowitej, z zapisem po przecinku.

Zamiana ceny w systemie binarnym na cenę w systemie dziesiętnym w części ułamkowej.
Obliczamy wartość części ułamkowej w następujący sposób:
0,111011(2) = 1 * 2^-1 + 1 * 2^-2 + 0 * 2^-3 + 1 * 2^-4 + 1 * 2^-5 + 1 * 2^-6 =  1/2 + 1/4 + 1/8 + 1/32 + 1/64 = 32/64 + 16/64 + 8/64 + 2/64 + 1/64 = 59/64
lub
0,111011(2) = 1 * 2^-1 + 1 * 2^-2 + 0 * 2^-3 + 1 * 2^-4 + 1 * 2^-5 + 1 * 2^-6 = 0,5 + 0,25 + 0,125 + 0,03125 + 0,015325 = 0,921875
Liczymy od pierwszej liczby po przecinku, mnożymy 1 lub 0 z 2 podniesioną do potęgi minusowej o odpowiedniej wartości, w zależności od pozycji danej liczby. pozycję liczymy od przecinka zaczynając od -1, -2, itd.

Liczbę należy zaokrąglić do dwóch miejsc po przecinku.

4. Ostatnim krokiem jest połączenie dwóch części w całość (części całkowitej i ułamkowej).

2. Zaproponuj handlowcom metodę przeliczania cen z systemu dwójkowego na dziesiętny i zapisz ją w postaci algorytmu w wybranej przez siebie notacji (lista kroków, schemat blokowy lub język programowania, który wybrałeś/aś na egzamin). Uwzględnij, że ceny są podawane z dokładnością do dwóch miejsc po przecinku. 

Specyfikacja:

Dane: s – napis złożony z ciągu zer i jedynek, przecinka oraz dwóch cyfr po przecinku (każda cyfra to 0 lub 1). Napis przed przecinkiem nie jest pusty.

Wynik: w – liczba oznaczająca wartość w systemie dziesiętnym liczby podanej w systemie dwójkowym w postaci napisu s.

#include <iostream>
#include <conio.h>
#include <math.h>
#include <iomanip>

using namespace std;

int main()
{
 string cenaB, cenaB2="", cenaB3="";
 int cenaD=0;
 cout << "Podaj cene w systemie binarnym: ";
 cin >> cenaB;
 // pobieranie czesci calosci
 int a=0;
 while (cenaB[a] != ','){
 cenaB2 += cenaB[a];
 a++;
 }
 // pobieranie częsci ulamku
 a++; // przesuniecie o przecinek
 for (a;a<cenaB.length();a++) cenaB3 += cenaB[a];

// zamiana na dziesietna liczbe
 int podstawa = 2;
 int tmp = 1;
 int x;
 for (int i=cenaB2.length()-1; i>=0; i--) {
 x = cenaB2[i]-48;
 cenaD += x*tmp;
 tmp *= podstawa;
 }

// zamiana ulamku
 double wynik=0, s=1;
 for (int z=0; z<cenaB3.length(); z++){
 if (cenaB3[z]=='1') {
 wynik = wynik + pow(2,-s);
 }
 s++;
 }

// wyswietlenie wyniku
 cout << "Cena w systemie dziesietnym: ";
 cout << fixed;
 cout << setprecision(2);
 cout << wynik+cenaD << endl;
 return 0;
}