Notatki do wykładu

Wstęp do programowania

(3)

1

Maszyny RAM – pętle, liczniki, większe dane.

1.1

Pętle, liczniki.

Przykład 3a.
Napisać program RAM, który oblicza f (n) = 2

n

.

Przypomnijmy, że

2

n

=

 1

jeśli n = 0

n · 2

n−1

jeśli n > 0

Ogólna idea działania programu.

1. Czyta n.

2. Sprawdza, czy n ≥ (jesśli nie, to co?).

3. Czynności początkowe:

• licznik l (wskazujący, które mnożenie należy wykonać) przyjmuje wartość początkową

1,

• początkowa wartość funkcji f jest 1.

4. Jeśli l > n, to KONIEC.
5. Oblicza kolejny “częściowy wynik” f = 2 · f oraz zwiększa l o 1.
6. Przechodzi go 4.

Szczegóły algorytmu przedstawione zostały na schemacie blokowym (rysunek 1). Kompletny

program podano poniżej.

Oto mapa pamięci dla przykładu 3a. Zobacz kompletny program RAM.

Mapa pamięci

0
1

n

2

l

3

f

..

.

..

.

1

Początek

Czytaj n

n<0?

l←1

f←1

N

l>n?

Koniec

T

N

f←2*f

l←l+1

f

←n

Drukuj f

T

Rysunek 1: Schemat blokowy do przykładu 3a.

Przyklad3a:

#f=2^n

read

1

#czytaj n

load

1

#Acc ‹- n

mult

=-1

#Acc ‹- -n

jgtz

ujemna #n<0

load

=1

store 2

#l ‹- 1

store 3

#f ‹- 1

nmn:

load

2

#Acc ‹- l

sub

1

#Acc ‹- l-n

jgtz

druk

#l>n

load

3

#l<=n

mult

=2

2

store 3

#f ‹- 2*f

load

2

add

=1

store 2

#l ‹- l+1

jump

nmn

ujemna:

load

1

store 3

#f ‹- n

druk:

write 3

1.2

Rozpoznawanie słów.

Słowem nazywamy dowolny ciag liczb, przeważnie niewielkich (< 10.) Można sie umówić, że
liczby te nazywamy cyframi.

Przykład 3b.
Na taśmie wejściowej znajduje się słowo złożóne z jedynek i dwójek. Na końcu jest zero. Napisać
program, który rozpoznaje słowa zawierąjace taką samą liczbę jedynek i dwójek.

Uwaga. Rozpoznaje, znaczy oblicza funkcję charakterystyczną zbioru E złożonego ze słów w
zawierających taką samą liczbę jedynek i dwójek:

ch

E

(w) =

 1 jeśli w zawiera taką samą liczbę jedynek i dwójek,

0 w przeciwnym wypadku

Ogólna idea działania programu.
Zmienna d posłuży do obliczenia różnicy liczby wystąpień dwójek i jedynek w danym słowie
(ciągu liczb niedużych). Będziemy czytać kolejne cyfry. Jeśli napotkamy 1, to zmniejszymy d
o jeden; jeśli napotkamy 2, to zwiększymy d o jeden.

Szczegóły algorytmu przedstawione zostały na schemacie blokowym (rysunek 2). Kompletny

program podano poniżej.

Oto mapa pamięci dla przykładu 3b. Zobacz kompletny program RAM.

Mapa pamięci

0
1

d

2

..

.

..

.

3

Początek

Czytaj n

n<0?

l←1

f←1

N

l>n?

Koniec

T

N

f←2*f

l←l+1

f

←n

Drukuj f

T

Rysunek 2: Schemat blokowy do przykładu 3b.

Przyklad3b:

#Tyle samo jedynek i dwojek

load

=0

store 1

#d ‹- 0

kolcyfra:

read

0

#Acc ‹- WE (kolejna cyfra)

jzero druk

#przeczytano 0

sub

=1

jzero jeden

#przeczytano 1

load

1

#przeczytano 2

add

=1

store 1

#d ‹- d+1

jump

kolcyfra

jeden:

load

1

#przeczytano 1

sub

=1

4

store 1

#d ‹- d-1

jump

kolcyfra

druk:

load

1

jzero tak

#wynik = 1

write =0

#WY ‹- 0

halt

tak:

write =1

#WY ‹- 1

5