Misja pierwsza: Bitwa podwórkowa - PY_I_R_W13B_M04 Misja matura - ćwiczenia w konstruowaniu pętli

RyDYsHWfoddNT

Zadanie: Bitwa podwórkowa

Bartek i Tomek bawią się w bitwę podwórkową z dziećmi z pobliskiego osiedla. Ich kolega Maciek pilnuje trzepaka kilka bloków dalej. Chłopcy chcą przekazać mu wiadomość o nadchodzącym ataku na jego posterunek. Sami nie mogą jednak opuścić swojego posterunku.

Bartkowi udało się zwerbować do drużyny młodszego brata, Kacpra, w roli posłańca. Chłopcy boją się jednak, że Kacper zostanie złapany wraz z wiadomością. Żeby temu zaradzić, Tomek wymyślił algorytm, dzięki któremu przeciwnik nie będzie umiał odczytać wymienianych wiadomości.

Przedstawiony algorytm przekształca wiadomość s o długości n za pomocą odpowiednich przestawień. Po wykonaniu algorytmu przekształcona wiadomość znajdzie się w zmiennej s:

Algorytm:

s[0..n-1]  #wiadomość do przekształcenia
dla i = n - 1, n - 2, ..., 0 wykonuj:
	jeżeli i mod 2 = 0:
		a ← s[i]
		s[i] ← s[i div 2]
		s[i div 2] ← a
	w przeciwnym wypadku:
		a ← s[i]
		s[i] ← s[i mod 2]
		s[i mod 2] ← a

Operator mod oznacza resztę z dzielenia, natomiast div – dzielenie całkowitoliczbowe.

Podaj wynik działania przedstawionego algorytmu Tomka dla słów ATAK oraz TRZEPAK.

Specyfikacja problemu:

Dane:

n – długość łańcucha s; liczba naturalna
s[0..n‑1] – łańcuch znaków o długości $n$ zawierający wiadomość do przekształcenia

Wynik:

s[0..n‑1] – łańcuch znaków o długości $n$ zawierający przekształconą wiadomość

Praca domowa

Zapisz algorytm w postaci programu w języku C++, Java lub Python.

Rozwiązanie

Przeanalizujmy działanie algorytmu.

Zacznijmy od słowa ATAK. Wypiszmy etapy przekształceń z zastosowaniem przedstawionego algorytmu:

n ← 4
s[0..n-1] ← 'ATAK'

i ← 3 
	a ← s[3] = 'K'
	s[3] ← s[1] = 'T'
	s[1] ← a 
	# s = 'AKAT'

i ← 2 
	a ← s[2] = 'A'
	s[2] ← s[1] = 'K'
	s[1] ← a 
	# s = 'AAKT'

i ← 1 
	a ← s[1] = 'A'
	s[1] ← s[1] = 'A'
	s[1] ← a 
	# s = 'AAKT'

i ← 0
	a ← s[0] = 'A'
	s[0] ← s[0] = 'A'
	s[0] ← a 
	# s = 'AAKT'

Analogicznie analizujemy kolejne iteracje pętli dla słowa TRZEPAK:

Linia 1. n ← 7. Linia 2. s otwórz nawias kwadratowy 0 kropka kropka n minus 1 zamknij nawias kwadratowy ← apostrof TRZEPAK apostrof. Linia 4. i ← 6. Linia 5. a ← s otwórz nawias kwadratowy 6 zamknij nawias kwadratowy znak równości apostrof K apostrof. Linia 6. s otwórz nawias kwadratowy 6 zamknij nawias kwadratowy ← s otwórz nawias kwadratowy 3 zamknij nawias kwadratowy znak równości apostrof E apostrof. Linia 7. s otwórz nawias kwadratowy 3 zamknij nawias kwadratowy ← a. Linia 8. kratka s znak równości apostrof TRZKPAE apostrof. Linia 10. i ← 5. Linia 11. a ← s otwórz nawias kwadratowy 5 zamknij nawias kwadratowy znak równości apostrof A apostrof. Linia 12. s otwórz nawias kwadratowy 5 zamknij nawias kwadratowy ← s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości apostrof R apostrof. Linia 13. s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy ← a. Linia 14. kratka s znak równości apostrof TAZKPRE apostrof. Linia 16. i ← 4. Linia 17. a ← s otwórz nawias kwadratowy 4 zamknij nawias kwadratowy znak równości apostrof P apostrof. Linia 18. s otwórz nawias kwadratowy 4 zamknij nawias kwadratowy ← s otwórz nawias kwadratowy 2 zamknij nawias kwadratowy znak równości apostrof 1 apostrof. Linia 19. s otwórz nawias kwadratowy 2 zamknij nawias kwadratowy ← a. Linia 20. kratka s znak równości apostrof TAPKZRE apostrof. Linia 22. i ← 3. Linia 23. a ← s otwórz nawias kwadratowy 3 zamknij nawias kwadratowy znak równości apostrof K apostrof. Linia 24. s otwórz nawias kwadratowy 3 zamknij nawias kwadratowy ← s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości apostrof A apostrof. Linia 25. s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy ← a. Linia 26. kratka s znak równości apostrof TKPAZRE apostrof. Linia 28. i ← 2. Linia 29. a ← s otwórz nawias kwadratowy 2 zamknij nawias kwadratowy znak równości apostrof P apostrof. Linia 30. s otwórz nawias kwadratowy 2 zamknij nawias kwadratowy ← s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości apostrof P apostrof. Linia 31. s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy ← a. Linia 32. kratka s znak równości apostrof TPKAZRE apostrof. Linia 34. i ← 1. Linia 35. a ← s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości apostrof P apostrof. Linia 36. s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy ← s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości apostrof P apostrof. Linia 37. s otwórz nawias kwadratowy 1 zamknij nawias kwadratowy ← a. Linia 38. kratka s znak równości apostrof TPKAZRE apostrof. Linia 40. i ← 0. Linia 41. a ← s otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości apostrof T apostrof. Linia 42. s otwórz nawias kwadratowy 0 zamknij nawias kwadratowy ← s otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości apostrof T apostrof. Linia 43. s otwórz nawias kwadratowy 0 zamknij nawias kwadratowy ← a. Linia 44. kratka s znak równości apostrof TPKAZRE apostrof.

n ← 7
s[0..n-1] ← 'TRZEPAK'

i ← 6 
	a ← s[6] = 'K'
	s[6] ← s[3] = 'E'
	s[3] ← a 
	# s = 'TRZKPAE'

i ← 5 
	a ← s[5] = 'A'
	s[5] ← s[1] = 'R'
	s[1] ← a 
	# s = 'TAZKPRE'

i ← 4 
	a ← s[4] = 'P'
	s[4] ← s[2] = '1'
	s[2] ← a 
	# s = 'TAPKZRE'

i ← 3 
	a ← s[3] = 'K'
	s[3] ← s[1] = 'A'
	s[1] ← a 
	# s = 'TKPAZRE'

i ← 2 
	a ← s[2] = 'P'
	s[2] ← s[1] = 'P'
	s[1] ← a 
	# s = 'TPKAZRE'

i ← 1 
	a ← s[1] = 'P'
	s[1] ← s[1] = 'P'
	s[1] ← a 
	# s = 'TPKAZRE'

i ← 0 
	a ← s[0] = 'T'
	s[0] ← s[0] = 'T'
	s[0] ← a 
	# s = 'TPKAZRE'

Wynik: AAKT i TPKAZRE

Słownik

dekrementacja

zmniejszenie wartości zmiennej o jeden

inkrementacja

zwiększenie wartości zmiennej o jeden

iteracja

technika programowania polegająca na powtarzaniu tej samej operacji w pętli określoną liczbę razy lub aż do spełnienia określonego warunku; termin ten używany jest także w węższym znaczeniu - nazywa się nim operacje wykonywane wewnątrz takiej pętli

nieskończona pętla

pętla, która nigdy nie zostanie zakończona, ponieważ warunek wyjścia z pętli nigdy nie zostaje spełniony

zagnieżdżone pętle

wywołanie pętli wewnątrz innej pętli

Najczęstsze błędy

Misja druga: Poczta Bajtocka

Zadanie: Bitwa podwórkowa

Rozwiązanie

Słownik