Zadanie 2: Liczby binarne, bloki i programy (2.1-2.3, 2.5)
Algorytm liczący bloki zapisu binarnego oraz trzy programy na oryginalnym pliku bin.txt.
Rozwiązujesz bez konta, a odpowiedzi sprawdza ten sam silnik co na platformie. Postęp i powtórki zapisują się dopiero po darmowej rejestracji.
Ułóż algorytm liczący bloki w zapisie binarnym
Blokiem w zapisie binarnym liczby nazywamy każdy niepusty, maksymalny (nie da się go rozszerzyć ani w lewo, ani w prawo) ciąg kolejnych takich samych cyfr. Przykładowo 111110000110111 składa się z pięciu bloków: 11111, 0000, 11, 0, 111, a 1111111111111111 z jednego.
Ułóż kroki algorytmu, który dla danej dodatniej liczby całkowitej n wyznaczy b, czyli liczbę bloków w jej zapisie binarnym. Wolno używać tylko instrukcji sterujących, przypisań, porównań oraz mod i div; funkcje wbudowane do zamiany systemów są zabronione. Pomysł: kolejne cyfry binarne od najmniej znaczącej to kolejne reszty z dzielenia przez 2, więc wystarczy porównywać każdą cyfrę z poprzednią.
Przeciągnij wiersze albo użyj strzałek, aby ustawić poprawną kolejność.
- 1n ← n div 2
- 2jeżeli cyfra ≠ poprzednia, to:
- 3b ← 1
- 4cyfra ← n mod 2
- 5poprzednia ← cyfra
- 6dopóki n > 0 wykonuj:
- 7b ← b + 1
- 8poprzednia ← n mod 2
- 9n ← n div 2