Notatki do wykładu
Wstęp do programowania
4
1 Kilka pętli
Przykład 4a
Dany jest ciąg liczb dodatnich, zakończony liczbą zero. Sprawdzić, które z tych liczb są
liczbami pierwszymi.
Przypomnienie
Liczba naturalna (tzn. całkowita nieujemna) jest pierwsza, jeśli jej jedynymi dzielnikami
są liczby 1 oraz ona sama: m " P RIME �! "d " Z+d|m �! (d = 1 (" d = m), gdzie
P RIME oznacza zbiór liczb pierwszych. Obliczyć należy zatem funkcję charakterystyczną
zbioru P RIME :
1 jeśli m " P RIME,
chP RIME(m) =
0 w przeciwnym przypadku.
Przyjmijmy, że liczba jeden nie jest liczbą pierwszą.
Główna idea
Oczywiście, liczba 1 dzieli każdą liczbę; sprawdzić należy zatem, czy istnieje dzielnik d danej
liczby m taki, że d > 1 oraz d = m. Postąpimy według następującej idei:

rozpoczynając od wartości 1 zmiennej d będziemy w kolejnych krokach zwiększać wartość d
o 1, aż uzyskamy sytuację taką, że d|m (zawszy ten warunek zostanie osiągnięty, gdyż, w końcu
m|m). Jeśli okaże się, że pewna liczba d mniejsza od m dzieli m, to m nie jest pierwsza.
Schemat blokowy przedstawia Rysunek 1.
1
Początek
Czytaj m
T
m=0?
N
T
m<2?
N
d�!1
N
d�!d+1
d � m?
T
T N
d=m?
Drukuj 1 Drukuj 0
Koniec
Rysunek 1: Schemat do przykładu 4b.
Oto mapa pamięci dla przykłąadu 4a. Zobacz kompletny program RAM.
Mapa pamięci
0
1 m
2 d
3
. .
. .
. .
2
2 Adresowanie pośrednie
Ostateczna postać argumentu:
ńł
e etykieta wskazuje na następny rozkaz do wykonania,
�ł
�ł
�ł
i wtedy wartość argumentu v(a) = v(i) = r(i),
a =
= i wtedy wartość argumentu v(a) = v(= i) = i,
�ł
�ł
ółĆi wtedy wartość argumentu v(a) = v(Ći) = r(r(i)).
Innymi słowy, wartością argumentu postaciĆi jest zawartość rejestru rj, którego adres, j,
znajduje się w rejestrze ri. Przykładowo, w przypadku:
Mapa pamięci
0
1
2 7
3
. .
. .
. .
7 45
. .
. .
. .
po wykonaniu rozkazu:
LOAD Ć3
zawartość akumulatora będzie równa 45, albowiem v(Ć3) = r(r(3)) = r(7) = 45.
Przykład 4b
Dane jest słowo złożone z jedynek i dwójek, zakończone zerem. Wydrukować dane słowo
wspak.
Przypomnienie
Słowem nazywamy ciąg liczb, przeważnie małych, które umownie nazywamy cyframi.
Główna idea
Umieścimy kolejne cyfry danego słowa: c1, c2, . . . w kolejnych rejestrach pamięci: r10, r11, . . . .
Następnie wydrukujemy je, rozpoczynając od ostatniej przeczytanej cyfry. Zatem zmierzamy
uzyskać następującą sytuację:
Mapa pamięci
0
1
. .
. .
. .
10 c1
11 c2
. .
. .
. .
?? c?
Znaki zapytania postawiliśmy, gdyż nie wiemy, z ilu cyfr składa się dane słowo.
3
Jeśli przez j oznaczymy adres rejestru, do którego czytana jest kolejna cyfra danego słowa,
to czytanie całego słowa przebiegnie następująco:
1. j �! 10,
2. czytaj kolejną cyfrę c,
3. jeśli c = 0, to przejdz
do drukowania,
4. rj �! c,
5. j �! j + 1.
Zwróćmy uwagę, że po przeczytaniu całego słowa zmienna j ma wartość ??+1, zatem pier-
wsza drukowana cyfra znajdować się będzie w rejestrze rj-1.
Schemat blokowy przedstawia Rysunek 2.
Oto mapa pamięci dla przykładu 4b. Zobacz kompletny program RAM.
Mapa pamięci
0 c
1
2 j
. .
. .
. .
10 c1
11 c2
. .
. .
. .
?? c?
4
Początek
j �! 10
Czytaj c
c = 0?
r(j) �! c
j �! j+1
T
j = 10?
N
j �! j-1
Drukuj r(j)
T
Koniec
Rysunek 2: Schemat do przykładu 4b.
5