Zadanie 2. Ułamki dwójkowe

W systemach pozycyjnych – o podstawie innej niż 10 – można zapisywać nie tylko liczby całkowite, ale również rzeczywiste z pewną dokładnością. Np. w systemie dwójkowym cyfry po przecinku odpowiadają kolejnym potęgom $\frac{1}{2}$ (jednej drugiej). Cyfra 1 na pierwszym miejscu po przecinku odpowiada $\frac{1}{2}$, na drugim miejscu oznacza $\frac{1}{4}$, na trzecim reprezentuje $\frac{1}{8}$ i tak dalej. Np. (0,101)Indeks dolny 2₂ = $\frac{1}{2}$ + $\frac{1}{8}$ = $\frac{5}{8}$ = 0,625Indeks dolny 10₁₀ . Podobnie jak w systemie dziesiętnym nie każda liczba daje się zapisać w ten sposób dokładnie, np. liczba $\frac{1}{3}$ nie ma skończonego rozwinięcia w systemie dwójkowym (ani też w dziesiętnym). Można jednak dla każdej liczby rzeczywistej dość łatwo wyznaczyć zadaną liczbę początkowych cyfr po przecinku.

Następujący algorytm przyjmuje na wejściu liczbę rzeczywistą x, należącą do przedziału $⟨0,1)$ oraz dodatnią liczbę całkowitą k i wypisuje k pierwszych cyfr liczby x w zapisie dwójkowym:

Specyfikacja problemu:

Dane:

• x – liczba rzeczywista, 0 ≤ x < 1

• k – liczba całkowita dodatnia

Wynik:

• y – zapis dwójkowy liczby x do k-tego miejsca po przecinku

funkcja binarny(x, k)
	wypisz "0,"
	y ← x
	dla i = 1, 2, ..., k wykonuj:
(*)		jeżeli y ≥ 1/2:
			wypisz "1"
		w przeciwnym razie:
			wypisz "0"
		y ← y * 2
		jeżeli y ≥ 1:
			y ← y – 1

Rozwiązanie