i
i
“1478-Ramsak-Priblizek” — 2010/8/25 — 8:20 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 29 (2001/2002)
Številka 3
Strani 171–173
Žiga Ramšak in Janez Brank:√
(6+
√
15) JE NAJBOLJŠI PRIBLIŽEK ZA π
Ključne besede: matematika, iracionalna števila, približki, računalni-
štvo, sintaksna drevesa.
Elektronska verzija:
http://www.presek.si/29/1478-Ramsak-Brank.pdf
c© 2001 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.
I Računalništvo
)6 + jI5 JE NAJBOLJŠI PRIBLIŽEK ZA Jr
Če je približek zr-ja lahko izražen le z nar avnimi št evili, največ dvema
kvadratnima korenoma, sešte vanjem in množenj em, je vseh možnih kan-
didatov (izrazov) za najboljš i približek končno mnog o, pravzaprav celo
zelo malo. P rvopodpisani sem domneval, da so možne samo naslednj e
št ir i oblike izrazov z naštet imi om ejitvami:
a + v'b, O ::; a ::; 4, O ::; b ::; 10 (1)
a + )b + ve, O::; a < 4, O::; b< 10, O::; c::; 100 (2)
a + v'b + ve, O< a ::; 4, O< b, C < 10 (3)
a + (b+ ve)(d + ve) , O::; a,b,d < 4, O::; c, e < 10 (4)
Možnost (1) je sicer že za je t a v (2) , v (3) in v (4), če so nekater i
koeficienti enaki O, vend ar jo vseeno ob ravnavamo pose bej. Mn oženj e
dveh korenov bi dalo spet en sam koren: J(iVb = ve,C = ab (neko drugo
naravno števi lo). Podobno pa velja t udi za mn oženje naravnega števila in
koren a iz nar avnega števila (kvadrat šte vila damo pod kor en in dob imo
izraz z enako vrednostjo) .
Moj bivši sošo lec in kolega na Fakult eti za računalnistvo in informa-
t iko Janez Brank je mojo domnevo pot rdil z dokazom , ki ga pr ilagam na
koncu.
Vseh naštetih možnosti je, kljub temu, da se jih večina od 1T razli-
kuje za več kot 1, še vedno tako malo, da sem jih nekaj preveril kar s
kalkulatorjem, ostale pa s programom v C-ju na osebnem računalniku.
Na jboljši pribli žek obl ike (1) je ViO, ki je od 1T (po absolut ni vr edno-
sti) oddaljen za manj kot 0.2l.
Za ob liko (4) so najboljši pribli žki prav tako le ViO in nj egove izp e-
ljanke, npr. V2v'5.
Ob lika (2) da najboljši prib ližek sploh in sicer V6 + v'I5, ki je od 1T
oddaljen za manj kot 0.00054.
Oblika (3) pri sp eva naj zanimivejši približek , ki sploh ni slab: V2+V3
je od 1T oddaljen za manj kot 0.005.
Glede na to , da sva , eden absolvent računalništva, drugi pa od nedav-
nega po diplomski št udent, in da sva prev eri la kar vse mo žnosti, kar najbrž
ni bil smisel naloge, men iva, da najina reš itev ne more biti nagraj ena ,
četudi sva našla najboljši prib ližek. Naloga se nama je zde la zanimiva ,
zato sva se t udi lot ila reševanja.
172 Računalništvo I
D okaz , da so oblike izrazov (1) , (2) , (3) in (4) res ed ine, ki
ustrezajo zahtevam naloge:
Mislimo si sint aksna drevesa, v kater ih se lahko pojavljajo operatorji
+, . (oba binarna) in V (unarn i) , v listih drevesa pa naravna števila .
1. Najprej opazimo, da lahko poljubno dr evo, v katerem se pojavlj ata
od operatorj ev le + in ., poenost avimo kar v navad no naravno število.
2. Recimo zdaj , da se omejimo na dr evesa z enim sa mim V-vozliščem .
Ker je V un arni operator , ima to vozlišče eno samo poddrevo. V njem
lahko od opera to rjev nastopata le + in " tako da lahko (v skladu s točko
1) brez izgube za splošnost vzamemo , da je to poddrevo kar en sam list ,
v katerem je neko naravno število. Mislimo si zdaj pot od vrha drevesa
do tistega edinega V-vozlišča. Poddr evesa, ki izhajaj o iz t e poti na levi
in na desni , so ravno tako brez operatorjev V in jih lah ko poenostavim o
v naravna števila . Če upoštevam o še komutativnost + in " lah ko drevo
preoblikujemo tako , da gre ti st a veja do V-vozlišča ves čas na desno.
Tako dobimo izraz al o (a2 o (a3 o . . . o (an o V1J)...)) . Vsak o predst avlj a
ali + ali ·. Zdaj pa upošt eva jmo, da lahko izrazu oblike a + V1J nekaj
pr išt ejemo ali pa ga z nečim (poz it ivnim) pomnožimo, pa bo ostal enake
oblike. Izraz V1J je take oblike (za a vzamemo število O) , ko pa mu zunanji
ope ratorji še kaj pri štejejo ali ga s čim pomnožijo, ostane enake oblike.
Torej: dr evo z enim samim V-vozliščem nujno pr edstavlja izraz oblike
a + v1J.
3. Zdaj pa si oglejmo drevesa z dvema V-vozliščema. Tu ločimo dve
možnosti : ali je eno od V-vozlišč potomec drugega ali pa ne.
3.1. Recimo , daje eno od V-vozlišč (recimo mu B) potomec drugega
(recimo mu A) . Poddrevo pod A-jem v skladu s točko 2 pr edst avlja neki
izraz oblike b+ y'c . Skupaj z A-jem imam o torej izraz Jb + y'c . Na veji,
ki pelje od kore na do A-ja, spet po enostavimo vsa stranska poddrevesa
v nar avna števila in dobljeno izroj eno drevo pr euredimo tako, da se veja
do A-ja ves čas pr emika na desno. Razmislek, kot pr i točki 2, nam zdaj
pove, da lah ko izrazu oblike a + Vd, za d = Jb + y'c, kaj pr ištejemo ali
pa ga s čim pomnožimo, pa ostane enake oblike. Torej drevo, v katerem
imamo dva gnezdena kvadratna korena, gotovo pr edstavlja izraz oblike
a + J b + y'c.
3.2. Rec imo, da nobeno od V-vozlišč ni potomec drugega. Naj bosta
A in B naši V-vozlišči , C pa njun najnižji skupni prednik. Brez izgube
za splošnos t predpostavimo, da je A v levem poddrevesu C-ja, B pa v
desnem (v C-ju seved a mora biti binarni operator, saj smo oba korena že
porabili, A in B pa tudi ne moreta biti v istem C-jevem poddr evesu , sa j
m o  rerkll, mj bo C njun m@&ji h p n i  pmb&). Leva Gjm &drew, 
jetomjdrevna:enimmnhJ- wdiiEem in =to po t o M  2 pmdshvga 
krw oblilac! a + &. Ram hku pea demo €2-jm poddrew predstavua 
-j, ob& c + &. fh je opmtm v Gju +, pmbtavlja psd* s 
korenom~b6~& blikee+&+fimndm~ll;ketnowt,s~ante~g b in c. 
pa je v Gju operator *, predstsivlja p o d h  sh e n o m  C hraz oblilce (a+ 
+fi)(e+Jq. Preprd indukt;iMi raanhlek POW, dase s p- in 
mnd4i, ki se dopjajo na poti od lmrerma do C, v prvem primeru ohrmja 
obba+&+~qvdrugemprim~~1paoblikaa+(b+&(d+~. 
S ~ d a b i l i s m a ~ & ~ ~ o ~ ~ ~ ~ , ~ t k a ~ ~ a