P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 26 (1998/1999) Številka 4 Strani 204-208
Martin Juvan:
NENAVADNA FUNKCIJA Z RAČUNALNIKOM
Ključne besede: matematika, analiza, računalništvo, funkcije, naravna števila, rekurzija.
Elektronska verzija: http://www.presek.si/26/1376-Juvan.pdf
© 1999 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
NENAVADNA FUNKCIJA Z RAČUNALNIKOM
V prejšnji številki Preseka (Nenavadna funkcija, Presek 26 št. 3. str. 166 -169) smo spoznali nekatere zanimive lastnosti funkcije F, ki smo jo definirali rekurzivno z naslednjimi predpisi:
F(l) = 1 in F(2n) = F(n), F(2n + 1) = F(n) + F(ti + 1) za n > 1.
Tokrat si bomo ogledali nekaj računalniških programov, s katerimi si lahko pomagamo pri raziskovanju lastnosti te funkcije. S programi bomo tudi preverili odgovore na nekatera vprašanja, na katera smo s teoretičnim razmislekom odgovorili že v prejšnji številki Preseka.
Začnimo s programom v logu. s katerim za dano naravno število n izračunamo vrednost F(n):
TO F :n
IF :n < 2 [OUTPUT 1] ¡baza rekurzije
TEST (REMAINDER :n 2) = 0 ;Ali je argument sod?
IFT [OUTPUT F :n/2] ;Da.
IFF [OUTPUT CF (:n-l)/2) + (F <:n+l)/2)] ;Ne.
END
V gornjem programu računamo vrednost funkcije neposredno iz definicije. Pri taki neposredni uporabi rekurzivnih definicij moramo biti vedno previdni, saj se hitro primeri, da večkrat pokličemo funkcijo z istim argumentom. To pa pomeni odvečno delo in včasih je tega dodatnega dela toliko, da program postane praktično neuporaben. Ker je v našem primeru baza rekurzije le F(l) = X, je pri izračunu vrednosti F(n) funkcija F poklicana z argumentom n = 1 natanko F(ra)-krat. Že pri izračunu F(9) vrednost F(l) računamo npr. 4-krat. Ker pa funkcija F pri majhnih številih ne zavzame velikih vrednosti, je za majhna števila napisani program še vedno dovolj učinkovit.
Z gornjim programom lahko tudi sestavimo tabelo vrednosti funkcije F za števila od 1 do 16. Vrednosti zlagamo v seznam s, tega pa na koncu izpišemo:
MAKE "s [] KAKE "i 0
REPEAT 16 [MAKE "i :i+l MAKE "s LPUT F :i :sj
PRINT :s
Gornji ukazi tako izpišejo
1121323143525341
S programom lahko tudi ugotovimo, koliko je T7"(1999). Ukaz print F 1999
izpiše 49, toliko, kolikor smo liaračunali tudi v že omenjenem prispevku v prejšnji številki Preseka.
V nadaljevanja si bomo ogledali, kako lahko vrednosti funkcije F računamo še precej hitreje. Eden od možnih pristopov je, da vrednosti, ki jih izračunamo, sproti shranjujemo, npr. v tabelo. Poglejmo, kako na ta način s programom v programskem jeziku pascal poiščemo največjo vrednost, ki jo funkcija F zavzame na številih od 1 do 1999. program NenavadnaFunkcija;
{ Poišče največjo vrednost funkcije F na številih od 1 do meja. } const
meja = 1999; var
F: array [1.,meja] of integer: { tabeia vrednosti funkcije F } i: integer; max: integer; begin
{ Izračunamo vrednosti funkcije F od J do meja. }
F[l] := 1;
for i:=2 to meja do if odd(i) then
F[i] := F[i div 2] + F[i div 2 + 1] else
F[i] := F [i div 2j; { Med vrednostmi poiščemo največjo. } max :— F[l]; for i:—2 to meja do
if F[i]>max then max je= F[i]; { Izpišemo podatke o največji vrednosti. }
writelnfNajvecja vrednost funkcije od 1 do ',meja,' je \max,'.'); write('Ta vrednost je dosežena pri naslednjih številih:'); for i:=L to meja do
if F[i]=max then write(i:5); writeln; end.
Ko program poženemo, ta izpiše
Največja vrednost funkcije od 1 do 1999 je 144. Ta vrednost je dosežena pri naslednjih številih: 1365 1707
Seveda so odgovori enaki tistim, ki smo jih s kar precej dolgim in zapletenim razmislekom našli v prejšnji številki Preseka.
Računanje zaporednih vrednosti funkcije s sprotnim shranjevanjem vrednosti v tabelo je učinkovit postopek, kadar želimo izračunati vrednosti funkcije pri prvih nekaj številih. Da dobimo novo vrednost, moramo le preveriti parnost argumenta in morebiti sešteti dve že znani vrednosti, Slaba st ran postopka pa je, da potrebuje precej pomnilnika za tabelo vrednosti, kar omejuje njegovo uporabnost. Polovico tabele lahko prihranimo, če v njej hranimo le vrednosti funkcije pri lihih argumentih. Vrednost pri sodem argumentu potem dobimo tako, da argument delimo z 2, dokler je sod, ko pa postane lih, vrednost funkcije preberemo iz tabele. Na ta način nekoliko povečamo čas, ki ga potrebujemo za izračun naslednje vrednosti, hkrati pa razpolovimo količino potrebnega pomnilnika. Kodiranje programa, ki uporablja opisano spremembo, vam prepuščam za vajo.
Kako pa bi izračunali vrednost funkcije F pri velikih argumentih, recimo F(1 789 569 707) ali pa F(2 863 311 531)? S shranjevanjem vrednosti v tabelo si ne moremo pomagati, saj bi potrebovali res ogromno tabelo, pa tudi izračun manjših vrednosti bi nam vzel kar nekaj časa. Pa saj nas prejšnje vrednosti sploh ne zanimajo. Poskusimo lahko s programom v logu, ki smo ga napisali na začetku prispevka, a po nekaj minutah obupamo, saj ni videti, da bi se računanje kaj kmalu končalo. No, res je, da je logo programski jezik, ki se tolmači. Programi v jezikih, ki se prevajajo, taka sta npr. pascal in C, so običajno bistveno hitrejši. Tako lahko rekurzivno definicijo funkcije zapišemo kot program v pascalu ali C-ju. Poskusite, gotovo vam bo uspelo. Če vas skrbi predolgo L raj no računanje, lahko uporabite še kakšen dodatni "trik". V tabeli lahko pripravite vrednosti funkcije za "majhne" argumente, recimo do 10000, in te vnaprej izračunane vrednosti uporabite kot (razširjeno) bazo rekurzije. Poskusite lahko tudi s shranjevanjem vmesnih rezultatov. Vse vrednosti funkcije F, ki jih izračunate (tudi tiste z vmesnih korakov), skupaj s pripadajočim argumentom shranjujete v tabelo. Ko vas zanima vrednost F(n), najprej pogledate po tabeli, ah ste to vrednost morda že izračunali. Tako zagotovite, da za vsak argument, vrednost funkcije računate le enkrat (seveda pa se lahko zgodi, da vam čez čas po veliko opravljenih računih v tabeli zmanjka prostora).
Za konce prispevka pa si bomo ogledali tisto pravo metodo za računanje vrednosti funkcije F pri velikih argumentih. Postopek bo malce zvit, a preprost , zelo hiter in ne bo zahteval nobenega dodatnega prostora. Recimo, da bi radi izračunali vrednost F(n). Iskano vrednost bomo zapisali
kol celoštevilsko linearno kombinacijo dveli zaporednih vrednosti funkcije F:
F(n) = a • F(m) + b ■ F (m + 1).
Na začetku vzamemo kar m = n, a = 1 in b = 0. Nato število m razpolovimo in izračunamo nova koeficienta. Pri tem ločimo dve možnosti. Ce je število m sodo, m = Im!, potem velja F (m) — F (m') in F (m + 1) = = F(m') -I- F (m' + 1). Tako dobimo
JP(n) = a ■ F(m) + b ■ F(m + 1) = (a + b) - F (m') + b ■ F{m' + 1) ,
Ce pa je število m liho, m — 2m' -f- 1, potem imamo F ( m) --= F(m') + F(m' + 1) in F(m + 1} = F (m' + 1). Tedaj velja
F(n) = a ■ F(m) + b ■ F{m +1) = a • F{m') + {a + b) ■ F (m -f 1).
V obeh primerih lahko torej F (rt) zapišemo kot kombinacijo vrednosti Ffjn') in F(m' + 1), pri čemer nova koeficienta na zelo preprost način izračunamo iz prejšnjih dveh.
Zapišimo program v programskem jeziku C, ki za izračun vrednosti funkcije F uporablja zgoraj opisani postopek.
#include <stdio.h> /*
Hiter izračun vrednosti funkcije F.
Deluje hitro tudi za velike vrednosti argumenta,
*/
unsigned long F(unsigned long);
int main(void) f
unsigned long n; /* argument */ do {
printf("Vpisi vrednost argumenta (0 za konec): "); scanf C"y(lu", toi);
if (n != 0) printf("FC/.lu) = '/.lu\n\n", n, F(n)); } while (n != 0); return 0;
/* Nerekurzivno in brez tabele izračuna vrednost FCm). */
unsigned long F(unsigned long m)
{
unsigned long a s 1, b = 0;
/* Invarianta zanke: iskana vrednost = a*F(m)+b*F(m+1}. */ while Cm > 1) {
if (m % 2 — 0) a +« b; else b +*= a; m /= 2;
>
return a + b; /* F(l) = F(2) = 1 */
>
S programom izračunamo vrednosti
F(1 789 569 707) =2178309 in F(2 863311 531) = 3 524 578 .
Se na eno malenkost opozorimo. Programski jezik C pozna nepred-značena dolga cela števila (tip unsigned long). Na osebnih računalnikih spremenljivka takega tipa običajno zaseda 32 bitov, tako da je največja vrednost, ki jo lahko shranimo vanjo, enaka 232 — 1 = 4 294 967 295. Turbo pascal takega tipa ne pozna. (Predznačena) dolga cela števila (tip longtnt) sicer zavzamejo 32 bitov, a največja vrednost, ki jo lahko shranimo v spremenljivko tega tipa, je 231 — 1 = 2 147 483 647. Če bi gornji program napisali v (turbo) pascalu, tako z njim ne bi mogli izračunati vrednosti F(2 863 311 531), saj je argument funkcije prevelik in bi prišlo do prekoračitve. Morali bi sprogramirati še računanje s "pravimi" dolgimi števili ali pa prvo uporabo rekurzivnega pravila opraviti s svinčnikom in papirjem.
Martin Juvan