Powtórzenie wiadomości o pętli while

Pętla whilepętla whilePętla while jest specjalną instrukcją programistyczną służącą do powtarzania określonych czynności. To alternatywne rozwiązanie dla pętli forpętla forpętli for, która działa bardzo podobnie. Stosuje się ją zazwyczaj w sytuacjach, gdy kluczową kwestią jest liczba wykonanych powtórzeń. Z kolei pętli while używa się wówczas, gdy liczba wykonywanych powtórzeń nie jest znana, natomiast ważne jest spełnienie określonego warunku.

Przykładowe zastosowania pętli while:

1. operacje matematyczne na danej liczbie wykonywane do momentu osiągnięcia określonej wartości,

2. wypisanie n liczb parzystych większych od 0,

3. odliczanie pozostałego czasu trwania sesjisesjasesji.

Implementacja pierwszego przykładu w pseudokodzie:

liczba ← 0

dopóki liczba < 5 wykonuj:
	liczba ← liczba + 1

Implementacja drugiego przykładu w pseudokodzie:

n ← 5
licznik ← 0
i ← 1

dopóki licznik < n wykonuj:
	jeżeli i mod 2 = 0:
    	wypisz i
    	licznik ← licznik + 1
    i ← i + 1

Implementacja trzeciego przykładu w pseudokodzie:

ile_sekund ← 60

dopóki ile_sekund > 0 wykonuj:
	wypisz ("Pozostało " + ile_sekund + " sekund trwania sesji")
	czekaj jedną sekundę
    ile_sekund ← ile_sekund - 1

Zadanie 1. Silniowy system pozycyjny

Pojęcie silnisilniasilni dla liczb naturalnych większych od zera definiuje się następująco:

Silniowy system pozycyjny to pozycyjny sposób zapisu liczb naturalnych, w którym mnożniki dla kolejnych pozycji definiowane są przez silnie kolejnych liczb naturalnych, czyli:

W systemie silniowym współczynnik $x_i$, który odpowiada mnożnikowi $i!$, spełnia zależność $0 ≤ x_i ≤ i$. Zapis każdej liczby w silniowym systemie pozycyjnym jest jednoznaczny, tzn. każdą liczbę naturalną można zapisać tylko w jeden i dokładnie jeden sposób. W omawianym zadaniu będziemy mieć do czynienia wyłącznie z takimi liczbami, dla których współczynniki $x_i$ spełniają zależność $0 ≤ x_i ≤ 9$.

Poniżej przedstawiono algorytm z lukami, który zamienia zapis liczb z systemu dziesiętnego na system silniowy. Uzupełnij luki w tym algorytmie.

silnia ← 1
k ← 1
dopóki (silnia < x), wykonuj:
	k ← k + 1
	silnia ← silnia * k
jeżeli ..........................................
	silnia ← silnia div k
	k ← k – 1
s ←" "
dopóki (k > 0), wykonuj:
	cyfra ← ............................................
	s ← s ◦ tekst(cyfra)
	x ← ..................................................
	silnia ← ...........................................
	k ← k – 1

Uwaga:

• tekst(x) – funkcja zamieniającą liczbę x na jej zapis tekstowy

• " " – pusty napis

• u ◦ v – sklejenie dwóch napisów: u oraz v

Specyfikacja problemu:

Dane:

• x – liczba całkowita dodatnia zapisana w systemie dziesiętnym

Wynik:

• s – napis reprezentujący liczbę x zapisaną w systemie silniowym

Rozwiązanie

Przeanalizujmy algorytm krok po kroku. Pierwsza z luk do uzupełnienia pojawia się tuż po obliczeniu silni, której docelowa wartość ma być nie mniejsza niż x:

silnia ← 1
k ← 1
dopóki (silnia < x), wykonuj:
	k ← k + 1
	silnia ← silnia * k
jeżeli ..........................................
	silnia ← silnia div k
	k ← k – 1

Instrukcja umieszczona w bloku jeżeli powoduje zmniejszenie wartości zmiennych silnia oraz k. W celu otrzymania pierwszego współczynnika z silniowego systemu pozycyjnego odszukujemy jak największą wartość silni, jednak nie większą niż konwertowana liczba. W związku z tym jedynym możliwym warunkiem dla bloku jest silnia > x:

silnia ← 1
k ← 1
dopóki (silnia < x), wykonuj:
	k ← k + 1
	silnia ← silnia * k
jeżeli silnia > x:
	silnia ← silnia div k
	k ← k – 1

Kolejne luki w algorytmie pojawiają się po zadeklarowaniu pustego łańcucha znaków i  bezpośrednio dotyczą konwersji do silniowego systemu pozycyjnego:

silnia ← 1
k ← 1
dopóki (silnia < x), wykonuj:
	k ← k + 1
	silnia ← silnia * k
jeżeli silnia > x:
	silnia ← silnia div k
	k ← k – 1
s ←" "
dopóki (k > 0), wykonuj:
	cyfra ← ............................................
	s ← s ◦ tekst(cyfra)
	x ← ..................................................
	silnia ← ...........................................
	k ← k – 1

Luka w linii 11. dotyczy obliczania kolejnej cyfry w silniowym systemie pozycyjnym. Zgodnie z definicją będzie to wynik dzielenia całkowitego przez odpowiednią silnię będącą współczynnikiem przy danej cyfrze, która jest zapisana w zmiennej silnia:

silnia ← 1
k ← 1
dopóki (silnia < x), wykonuj:
	k ← k + 1
	silnia ← silnia * k
jeżeli silnia > x:
	silnia ← silnia div k
	k ← k – 1
s ←" "
dopóki (k > 0), wykonuj:
	cyfra ← x div silnia
	s ← s ◦ tekst(cyfra)
	x ← ..................................................
	silnia ← ...........................................
	k ← k – 1

Następnym krokiem będzie pomniejszenie wartości zmiennej x w celu wyznaczenia cyfr na kolejnych pozycjach. Zmniejszamy ją zatem o zapisaną już część w postaci silniowej, czyli iloczyn zmiennych cyfra oraz silnia (której wartość odpowiada współczynnikowi przy cyfrze):

silnia ← 1
k ← 1
dopóki (silnia < x), wykonuj:
	k ← k + 1
	silnia ← silnia * k
jeżeli silnia > x:
	silnia ← silnia div k
	k ← k – 1
s ←" "
dopóki (k > 0), wykonuj:
	cyfra ← x div silnia
	s ← s ◦ tekst(cyfra)
	x ← x - cyfra * silnia
	silnia ← ...........................................
	k ← k – 1

Ostatnia luka stanowi pomniejszanie silni w celu otrzymania kolejnego współczynnika pozycyjnego – podobny krok wykonujemy w linii 7. W związku z tym na zmiennej silnia wykonujemy dzielenie całkowite przez zmienną k:

silnia ← 1
k ← 1
dopóki (silnia < x), wykonuj:
	k ← k + 1
	silnia ← silnia * k
jeżeli silnia > x:
	silnia ← silnia div k
	k ← k – 1
s ←" "
dopóki (k > 0), wykonuj:
	cyfra ← x div silnia
	s ← s ◦ tekst(cyfra)
	x ← x - cyfra * silnia
	silnia ← silnia div k
	k ← k – 1

Schemat oceniania

• 3 pkt – za poprawne uzupełnienie wszystkich luk,

• 2 pkt – za poprawne uzupełnienie 3 luk,

• 1 pkt – za poprawne uzupełnienie 2 luk,

• 0 pkt – za poprawne uzupełnienie 1 lub 0 luk, lub za brak odpowiedzi.

Słownik