Moduł liczby
[źródło]
#
# / x, dla x >=0
# abs(x) = |
# \ -x, dla x < 0
#
read 0
jgtz noabs # r0 > 0
# r0 < 0
store 1 # r1 := r0
load =0 # r0 := 0
sub 1 # r0 := 0-r1
noabs:
write 0
halt
Funkcja sign
[źródło]
#
# / +1, dla x>0
# sign(x) = | 0, dla x=0
# \ -1, dla x<0
#
read 0
jzero zero
jgtz plus
#minus:
write =-1
halt
plus:
write =1
halt
zero:
write =0
halt
Reszta z dzielenia
[źródło]
# a mod b = a - (a div b)*b
read 1 # a
read 0 # b
jzero error # b=0
# b != 0
store 2 # r2 = b
load 1 # r0 = a
div 2 # r0 = a div b
mult 2 # r0 = (a div b)*b
store 2 #
load 1 #
sub 2 # r0 := a - (...)
write 0
error:
halt
Największy wspólny dzielnik
[źródło]
#
# function gcd(a,b)
# {
# while (true)
# {
# c = a-b
# if (c > 0) a=c
# else b=-c
#
# if (c==0)
# break;
# }
# return a;
# }
#
# proponowane wyrażenie watch
# c=0 a=1 b=2
read 1 # r1 = a
read 2 # r2 = b
while:
load 1 #
sub 2 # r0 = c = a-b
jgtz then
jump else
then:
store 1 # a = c
jump endif
else:
store 2
load =0
sub 2
store 2 # b = -c
endif:
jzero break # c ?= 0
jump while
break:
write 1 # return a
Obliczenie silni
[źródło]
#
# function factorial(n)
# {
# var res = 1;
# while (n)
# {
# res = res*n;
# n = n-1;
# }
# return res;
# }
#
# proponowane wyrażenie watch
# n=1 res=2
read 1 # r1 = n
load =0 #
sub 1 #
jgtz negative # n < 0?
load =1 # r2 = res = 1
store 2 #
load 1
while:
jzero endwhile
mult 2
store 2 # res = res * n
load 1
sub =1
store 1 # n = n-1
jump while
endwhile:
write 2 # return
negative:
halt
Obliczenie n do potęgi n-tej
[źródło]
#
# function npown(n)
# {
# var res = n;
# var k = n-1;
# while (k)
# {
# res = res*n;
# k = k-1;
# }
# return res;
# }
#
# proponowane wyrażenie watch
# n=1 k=3 res=2
read 0
store 1 # r1 = n
store 2 # r2 = res = n
sub =1
store 3 # r3 = k = n-1
load =0 #
sub 1 #
jgtz negative #
jzero zero # n <= 0?
load 3
while:
jzero endwhile
load 2
mult 1
store 2 # res = res * n
load 3
sub =1
store 3 # k = k-1
jump while
endwhile:
write 2 # return
zero:
negative:
halt
Obliczanie pierwiastka kwadratowego
[źródło]
# algorytm:
#
# c - pierwiastkowana liczba > 0
#
# tworzymy dwa ciągi a i b
#
# a0 = dowolna liczba - może być c
# b0 = c/a0
#
# a1 = (a0+b0)/2
# b1 = c/a1
# ...
# an = (an-1 + bn-1)/2
# bn = c/an
#
#
# b < c^(1/2) < a
# można wykazać, że ciągi a,b sa zbieżne do c^(1/2)
#
# proponowane wyrażenie watch
# c=4 an=2 bn=3
read 4 # r4 = c
load 4
jzero write2 # sqrt(0) = 0
jgtz ok
jump error # c < 0 - błąd!
ok:
store 2 # r2 = a
# r3 = b
loop:
load 2 #
add 3 #
div =2 #
store 2 # an=r2 = (an-1+bn-1)/2
load 4 #
div 2 #
store 3 # bn=r3 = c/an
# jeśli b>=a (b>a lub b=a)
sub 2 # r0 = a-b
jzero write1
jgtz write1
jump loop
write1:
write 2 # wypisz an (an=floor(sqrt(c)))
write 3 # wypisz bn (bn=round(sqrt(c)))
halt
write2: write =0
error: halt
Obliczanie wartości wyrażeń zapisanych w ONP
[źródło]
# Kodowanie symboli specjalnych jest następujące:
# zero = 0, 0
# koniec łańcucha = 0, 1
# + = 0, 2
# - = 0, 3
# * = 0, 4
# / = 0, 5
#
# np.
# notacja infiksowa: (((8+9)*5)-8/2)*(1+2) = 243
# ONP: 8 9 + 5 * 8 2, / - 1 2 + * eol
# po zakodowaniu: 8 9 0 2 5 0 4 8 2 0 5 0 3 1 2 0 2 0 4 0 1
#
# proponowane wyrażenie watch:
# x=3 y=5 arg_a=2 arg_b=3 top=4 stack=10:15
load =10 # r4 - wskaźnik stosu (top[stack])
store 4 # stos zaczyna się od rejestru 10-tego
next:
read 3 # wczytaj x (r3)
load 3
jzero escape # znak specjalny
jump pushnum # liczba
escape:
read 0 # wczytaj y
jzero pushnum # x,y = 0,0 -> wartość zero
sub =1 # (y-1) == 0 -> x,y = 0,1 -> koniec łańcucha
jzero eol #
store 5 # r5 = y
# ściągamy ze stosu dwie liczby
load 4
sub =10 # "usuń" offset
sub =1 # gdy ilość el. na stosie wynosi zero to r0=-1
# gdy jest jeden el. to r0=0
jgtz pop2
jump error # stos zawiera 0 albo 1 element - błąd!
pop2:
load 4 # załaduj wskaźnik stosu
sub =1 #
load *0 #
store 2 # r2 = wierzchołek stosu
load 4 #
sub =2 #
store 4 #
load *0 #
store 3 # r3 = "podwierzchołek" stosu
# klasyfikujemy y
load 5
sub =1 # (y-2) == 0 -> x,y = 0,2 -> plus
jzero plus
sub =1 # (y-3) == 0 -> x,y = 0,3 -> minus
jzero minus
sub =1 # (y-4) == 0 -> x,y = 0,4 -> mnożenie
jzero mult
sub =1 # (y-5) == 0 -> x,y = 0,5 -> dzielenie
jzero div
jump error # niewłaściwy kod!
plus:
load 2
add 3
jump pushnum
minus:
load 3
sub 2
jump pushnum
mult:
load 3
mult 2
jump pushnum
div:
load 3
div 2
pushnum:
store *4 # stack[sp++] = r0
load 4 # sp++
add =1 #
store 4 #
jump next #
eol: write 10 # zapisz top[stack]
error: halt
Sortowanie przez wybieranie
[źródło]
# function selection_sort(n)
# {
# if (n == 0)
# return;
#
# k = n; // odczytywanie tablicy
# idx = 10;
# while (k--)
# tab[idx++] = read;
#
# m = n; // sortowanie
# i = 10;
# while (true)
# {
# j = i+1;
# idx = i;
# max = tab[i]
# k = n-j
# while (k)
# {
# tmp = tab[j]
# if (tmp > max)
# {
# max = tmp;
# idx = j
# }
# j++;
# k--;
# }
# tmp = tab[i];
# tab[i] = tab[idx]
# tab[idx] = tmp;
#
# i++;
# if (--m == 0) break
# }
# }
#
# proponowane wyrażenie watch (dla części sortującej):
# m=1 i=2 j=3 k=6 idx=4 max=5 tmp=7 tab=10:20
#
# przykładowe dane:
# 5, 1, 12, 13, 8, 4
### odczytywanie tablicy ###
read 9 # r9 = n
load 9
jzero end
load =10 # tab zaczyna sie od rej. 10-tego
store 8 # r8 = idx
load 9 #
store 7 # r7 = k
readtab:
read *8
load 8 #
add =1 #
store 8 # idx++
load 7
sub =1
store 7
jgtz readtab
### sortowanie ###
load 9
store 1 # r1 = m=n
load =10
store 2 # r2 = i=10
while1:
load 2 #
add =1 #
store 3 # r3 = j=i+1
load 2 #
store 4 # r4 = idx=i
load *4 #
store 5 # r5 = max=tab[i]
load 9
sub 3
add =10
store 6 # r6 = k=n-j
while2:
load 6 #
jzero endwhile2 # k==0?
load *3 #
store 7 # tmp = tab[j]
sub 5 # tmp-max > 0
jgtz then
jump endif
then:
load 7 #
store 5 # max = tmp
load 3 #
store 4 # idx = j
endif:
load 3 #
add =1 #
store 3 # j++
load 6 #
sub =1 #
store 6 # k--
jump while2
endwhile2:
load *2 #
store 7 # r7 = tmp = tab[i]
load *4 # r0 = tab[idx]
store *2 # tab[i] = tab[idx]
load 7 #
store *4 # tab[idx] = tmp
load 2 #
add =1 #
store 2 # i++
load 1 #
sub =1 #
store 1 # m--
jzero end # m==0?
jump while1
end:
halt
Odwracanie tablicy
[źródło]
#
# function reverse(n)
# {
# k=n
# i=10;
# while (k)
# {
# tab[i] = read;
# i++;
# k--;
# }
#
# k=n div 2
# i=10 // indeks pierwszego
# j=10+n-1 // indeks ostatniego elementu
# while (k--)
# {
# tmp = tab[i]
# tab[i] = tab[j]
# tab[j] = tmp
#
# i++;
# j--;
# }
#
# proponowane wyrażenie watch:
# n=9 k=8 i=1 j=2 tmp=3 tab=10:20
#
# przykładowe dane
# 5 1 2 3 4 5
### wczytywanie ###
read 9 # r9 = n
load 9
jzero end
load =10 #
store 1 # r1 = i
load 9 #
store 8 # r2 = k
readtab:
read *1 # tab[i] = read
load 1 #
add =1 #
store 1 # i++
load 8 #
sub =1 #
store 8 # k--
jgtz readtab
### odwracanie ###
load =10 #
store 1 # r1 = i=10
load =9 #
add 9 # r2 = j=10+n-1
store 2
load 9 #
div =2 #
store 8 # r8 = k=n div 2
rev:
load 8 #
jzero end #
sub =1 #
store 8 # if (k--) goto end
load *1 #
store 3 # tmp = tab[i]
load *2 #
store *1 # tab[i] = tab[j]
load 3 #
store *2 # tab[j] = tmp
load 1 #
add =1 #
store 1 # i++
load 2 #
sub =1 #
store 2 # j--
jump rev
end:
halt