i
i
“Razpet-rekurzija” — 2010/5/28 — 10:49 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 14 (1986/1987)
Številka 4
Strani 226–231
Marko Razpet:
O UPORABI REKURZIVNIH FORMUL
Ključne besede: računalništvo, matematika.
Elektronska verzija: http://www.presek.si/14/849-Razpet.pdf
c© 1987 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
226
o UPORABI REKURZIVNIH FORMUL
Za začetek si poglejmo kratek programček, ki je napisan v programskem jeziku
BASIC za računalnik ZX SPECTRUM. Najb rž ga ne bo pretežko pr ilagoditi za
drug tip računalnika.
10 LET m=30: LET a=33
20 PLOT 0,75: DRAW 255,0
30 LET f=PI /m
40 FOR x=O TO 255
50 LET y=a *SIN(x*f)
60 PLOT x , y+75
70 NEXT x
Programček nariše na ekranu valovito pikčasto krivuljo, ki ji pravimo
sinusoida. Sprogramsko vrstico 20 dobimo os x , v vrstici 10 pomeni m število
točk na eni polovici vala, število a pa njegovo višino . Ta dva podatka lahko
sami spreminjamo, da dobimo sinusoide različnih oblik. Kdor hoče, pa naj
vrine še vrstico, ki bo dodala tudi os y.
Programu pravzaprav ni kaj očitati. Če pa večkrat ponovimo njegovo izva-
janje, nas kmalu začne motiti njegova počasnost . Nekako 20 sekund traja od
trenutka, ko ga sprožimo , do trenutka, ko nam računa ln ik javi, da je delo
končano. Če pa program malo bolje pogledamo, se njegovi počasnosti ni
treba več čudit i. Vrstice od 40 do 70 tvorijo zanko FOR-NEXT. V njej
uporabljamo funkcijo sinus (SIN), dvoje množenj in eno seštevanje , računalnik
mora to opraviti kar 256 -krat. Za izračun ene vrednosti funkcije sinus je treba
kar nekaj dela, to pa je glavni vzrok, da se program odvija , kakor pač se . Za
bralca, k i je že vešč dela s prevajalniki , pa tale naloga: prevedi naš programček
s prevajalnikom SOFTEK FP in izmeri hitrost izvajanja prevedenegaprograma.
Sicer pa dodajmo programu naslednje vrst ice:
80 PAUSE 100: CLS
90 PLOT 0,75 : DRAW 255,0
100 LET yO=O: LET yl=a*SINf
110 LET c=2*COSf
120 FOR x=O TO 255
130 PLOT x, yO+75
140 LET y2=c*yl-yO
150 LETyO=yl :LETyl=y2
160 NEXT x
Tako razširjen program še enkrat poženemo. Prvi del nariše sinusoido po-
časi , tako kot prej, kajt i za vsako točko mora opraviti dvoje množenj in izra-
čunati po eno vrednost funkcije sinus. Od programske vrstice 80 dalje dobimo
še enkrat isto sliko, toda precej hitreje kot prvič . V rstice od 120 do 160 tvori -
jo zopet zanko FOR-NEXT. V njej je le eno množenje in nekaj manj zahtevnih
operacij . Vse to se seveda ponovi 256-k rat. In v čem je skrivnost "uspeha", če
se malo pohvalimo?
y
x
Slika 1
Čim k rivulja ni sestavljena le iz daljic in krožnih lokov, moramo izračunati
dovolj mnogo različn ih točk in skoznje potegnemo kr ivuljo ali s krivuljnikom
ali po občutku .
Morda se je bralec v našem programu prvič srečal s funkcijo sinus. Nič za-
to! Ta funkcija spada med tako imenovane kotne ali, bolj učeno, t r igonometri-
čne funkcije. Veda, k i se ukvarja z njimi, se imenuje t rigonometrija, njeni za-
četki pa segajo noter v staro Babilonijo in Egipt. Ni zlomek, da bi mi v dobi
osvajanj a vesolja ne razumeli nekaterih preprostih stvar i iz poglavja okotn ih
funkc ijah . Treba je poudar it i, da kote v matemat iki in rač u na l n i štvu ob ičajno
merimo v rad ianih . Kotna enota rad ian je sred iščni kot, ki na poljubni k rožnici
pr ipada lo ku, kate rega dol žina je enaka dolžini polmera k rožnice. Dovolj si je
zapomniti , da je kot 1800 enak kotu 11 radianov. Po navadnem sklepnem ra-
č u n u je potem kot 10 enak kotu 11 / 180 radianov. Kotne funkcije SIN , COS
in TAN, k i jih pozna vaš SPECTRUM , zahtevajo kot v radian ih . V matematiki
imajo oznak e sin, cos in tq , V tem članku bomo imeli op ravka le 5 prvima
dvema .
Postavimo v ravnino pravokotni koord inatni sistem xy . Izberimo si enoto ,
nato nač rtamo krožnico s sredi ščem v iz hodišč u in zradijem 1. T a krožnica
bo pr ipravna za merjenje kotov . S rediščnemu kotu a pr ipada lok dolžine a.
Kote bomo meril i po loku krožnice od pozitivne polovi ce osi x . Kote, merjene
227
X = cosa, y = sina
T r ikotnik ONT na slik i 2 je pravoko-
ten in po Pitagorovem izreku dobimo
x 2 + y 2 = 1. V trigonometrij i pišemo
namesto (sin a) 2 ozi roma (cos a) 2 raje
sin 2a oz iroma cos/ c . T ako smo dobi-
li pr avzaprav osnovno zvezo
(1) sin2a + cos2a = 1
x
E(l,O)
Sl ika 2
y
sin cl!
v smeri, ki je nasprotna smer i giban ja kazalc ev na uri, bomo štel i za poz itivne,
če pa jih merimo v nasprotni smer i , pa negativne .
Prej om enjen i krožnici rečemo
kotomerne krožnica. Kot a določ a
na njnj to čko T s koord in at am a x in
y . Absc iso X im enujemo kosinus kota
a, ordi nato y pa sinu s ko ta a. To za-
pišemo takol e:
S slike 2 lahko razberemo tudi, da velj ata naslednj i fo rmul i
(2)
(3)
sin(-a) = - sina
cost -al = cosa
Funkcija cos je torej soda funkc ija , funkcija sin pa liha .
Hitro s slike 2 odčitamo tud i nekaj preprostih vrednosti: cosO = 1,
sin O= O, COS(7T12) = O, sin(7T12) = 1, ...t COS(27T) = 1, sin (2 7T) = O.
Funkcij i sinus in kosinus imamo na op isani nač in defin irani za vse kote
med - 2 7T in 27T. Lahko pa ju na smiselni način razširimo na vsa realna števila
z naslednj ima formulama
(4)
(5)
sin(a + 2k 7T) = sin a
cos(a + 2k7T) = cosa
ki veljata za poljubno realno število a in poljubno celo število k. Zarad i formul
(4) in (5) pravimo, da sta funkcij i sinus in kosinus periodični z osnovno perio-
do 27T .
Brez dokazov bomo navedli še formuli za sinus in kosinus vsote dveh re-
alnih števil. To sta tako imenovana adicijska izreka
(6)
(7)
228
sinln + ~) = sina cosf + cosa sin~
cost« + m= cosa cosf - sina sin~
Veljata za poljubni realni števili a in (3. Formuli (6) in (7) sta ključnega pomena
za hitrejše risanje sinusoid na računalniku. Če upoštevamo še formuli (2) in
(3), dobimo še
(8) sinlc - (3) = sina cosf - co>U .in(3
(9) costu - (3) = cosu cosf + sinu .in(3
Tudi ti dve formuli veljata za poljubni realni števili a in (3.
Povrn imo se na naše načrtovanje sinuso id. V najbolj splošnem primeru ima
ta krivulja enačbo Y =A .in(wx + <,O ). V njej nastopajo trije parametri: parame -
ter A se imenuje amplituda, w krožna frekvenca in <,O začetna faza. Za lepo
sliko jih je treba pazljivo izbrati.
Odločimo se, da bomo funkcijske vrednosti računali v točkah Xo = O,
XI = b, X2 = 2b, .. ., dokler bo pač krivulja še šla na papir oziroma na ekran.
Število b je pozitivno in primerno majhno, odvisno od tega, kakšno qostoto
točk bi radi imeli . Pripadajoče funkcijske vrednosti označimo Yk ' Torej
Yk = A .in(w xk + <,O) = A .in(kb ca + <,O)
kjer je k = O, 1, 2, oo • • Zaporedje Vo, YI, Y2, oo. pa ima zanimivo lastnost, ki
srno jo izkoristili v programu. Formuli (6) in (8) dasta tole zvezo med tremi za-
porednimi členi zaporedja Vo, YI, Y2, oo. :
(10) Yk+l+Yk_l=2Ykcos(bw) zak=1,2,3,oo.
To je poseben primer tročlene rekurzivne formule. Če poznamo Yo in YI , lah-
ko izračunamo Y2, iz YI in Y2 dobimo Y3 itd. Naj bo c = 2 cos(bw). Iz zveze
(10) izračunamo Yk+ 1 in dobimo
(11 )
Pri danih parametrih A, co, <,O in izbranem koraku b je Yo = A sin( <,O ) in YI =
=A sin(bw + <,O). Za vsak nadaljnjiYk napravimo le eno množenje in eno odšte-
vanje.
V posebnem primeru, ko je <,O = O, dobimo Yo = O in YI = A sin(bw) ter
Y« = A sin(kbw), kar smo uporabili v programu od vrstice 100 dalje. V tem
pr imeru dobimo sinusno krivuljo. Če pa je <,O = 1T/2, potem imamo Yo = A in
YI = A sin(bw + 1T12) = A cosl č co) ter Yk = A sin(kbw + 1T12) =A cos(kbw).
Ust rezni program bi načrtal kosinusno krivuljo .
Bralec naj poskusi napisati program, ki bo s pomočjo formule (11) narisal
hkrati sinusno in kosinusno krivuljo. Opazil bo, da je ena pravzaprav premik
druge v smeri osi x . Hkrati pa naj kontrolira, če velja formula (1). Morda bo
malo razočaran,a o tem malo kasneje.
229
Če je že treba tabeli rati funkciji sinus in kosinus z danim korakom li isto -
časno, delamo raje malo drugače. Izračunati mo ramo , sk ratka, števila
ck = cos(kli) in sk = sin(kli) za k = 0,1 ,2, .., Adicijski izrek (6) nam takoj da
(12) sk+ 1 = sin(kli + li) = sin(kli) cosč + cos(kli) sin č
adicijski izrek (7) pa
(13) ck+l = cos(kli +"li) = cos(kli) cos č - sin(kli) sinč
Če na kratko označimo C = CI = cosč in s = SI = sin li , potem lahko (12) in
(13) zapišemo bolj pregledno:
(14) sk+l=csk+sck
(15) ck+l = cCk - sSk za k = O, 1,2, ...
Ker poznamo Co = cosO = 1 in So = sinO = O, lahko korak za korakom izračuna­
mo Ct, St" C2, S2 ; . ..
Za začetek poskusimo načrtati na računaln iku elipso s pomočjo formul
(14) in (15). V pravokotnem koordinatnem sistemu xy naj ima elipsa enačbo
(x /a) 2 + (y l b )2 = 1. Če jo primerjamo s formulo (1) , se nam zdi , da bi postavi-
li x /a = cost in y /b = sint. S tem imamo
x=acost
(16)
y=bsint
V teh dveh enačbah nastopa parameter t, ki je realno število. S preprostim pre-
mislekom ugotovimo , da točka T s koordinatama x, y ravno enkrat obhodi
elipso, če parameter t preteče interval od O do 27r. Pravimo, da smo elipso para-
metrizirali s parametrom t . Z enačbama (16) je podana elipsa v parametr ičn i
obliki. Sedaj pa že lahko sestavimo program.
10 LET m=60: LET f=PI/m
20 LET c=COS f: LET s=SIN f
30 LET a=110: LET b=70
40 LET cO=1: LET sO=O
50 FOR t=O TO 2*m
60 PLOT 128+a *c0,75+b*sO
70 LET c1=c *cO-s *sO
80 LET s1 =c*sO+s *cO
90 LET cO=c1: LET sO=s1
100 NEXT t
Program se sicer ne izvede tako hitro kot ukaz CIRCLE pri vašem računalniku;
upoštevati je treba, da je to le BASIC.
230