журнал «Информатика и образование» - Информатика и образование 2012 №05

word;
s: string;
begin
m1:=0; n1:=1;
m2:=1; n2:=0;
s:='';
repeat
p:=a*(n1+n2);
q:=b*(m1+m2);
if pq then
begin
m1:=m1+m2;
n1:=n1+n2;
s:=s+'R';
end;
until p=q;
ToSB:=s;
end;

Çàäà÷à 2.
Ýòà çàäà÷à — îáðàòíàÿ ê ïðåäûäóùåé.
Íàïèøèòå ïðîöåäóðó, êîòîðàÿ ïî ïðåäñòàâëåíèþ
íåêîòîðîãî ïîëîæèòåëüíîãî ðàöèîíàëüíîãî ÷èñëà â
ñèñòåìå ñ÷èñëåíèÿ Øòåðíà—Áðîêî íàõîäèò ñàìî
a
.
÷èñëî
b

Контактная информация
Окулов Станислав Михайлович, доктор пед. наук, канд. тех. наук, профессор кафедры прикладной математики и информатики,
декан факультета информатики, математики и физики Вятского государственного гуманитарного университета (ВятГГУ); адрес: 610002,
г. Киров, ул. Красноармейская, д. 26; телефон: (8332) 67-53-01; e-mail: okulov@vshu.kirov.ru
S. M. Okulov, A. V. Lyalin,
Vyatka State Humanities University

THE STERN—BROCOT TREE AS A NOTATION
Abstract
The Stern—Brocot Tree enables to reconsider the studying of the notations at school.
Keywords: algorithm, rational numbers, the Stern—Brocot Tree, notations.

72

ЗАДАЧИ
Ðåøåíèå.
Ïðåäñòàâëåíèå çàäàåò ïóòü îò êîðíÿ äåðåâà äî

a
. Ïðîñòî ñëåäóåì ïî ýòîìó ïóòè.
b

procedure ToRac(s: string; var a, b: word);
var i, m1, n1, m2, n2: word;
begin
m1:=0; n1:=1;
m2:=1; n2:=0;
for i:=1 to length(s) do
if s[i]='L' then
begin
m2:=m1+m2;
n2:=n1+n2;
end
else
begin
m1:=m1+m2;
n1:=n1+n2;
end;
a:=m1+m2;
b:=n1+n2;
end;

Ñäåëàåì äâà íàáëþäåíèÿ.

2
ñî1
âïàäàåò ñî âñåì äåðåâîì, åñëè ïðèáàâèòü 1 ê êàæäîé âåðøèíå ïîñëåäíåãî. Îáúÿñíåíèå — èíäóêòèâm1 0
=
íîå. Ïðåäêàìè âñåãî äåðåâà ÿâëÿþòñÿ äðîáè
n1
1
Ïåðâîå íàáëþäåíèå. Ïîääåðåâî ñ êîðíåì

è

2
m2 1
. Ïðåäêàìè ïîääåðåâà ñ êîðíåì
— íà
=
1
n2
0

'
åäèíèöó áîëüøèå
äðîáè:

m2
1
m1
+1=
è
+1=
n2
1
n1

1
. Ñâîéñòâî «îòëè÷àòüñÿ íà 1» ñïðàâåäëèâî ïåð0
âîíà÷àëüíî. Ïðè÷åì ïàðû äðîáåé, îòëè÷íûå íà 1,
äàþò ìåäèàíòû, êîòîðûå âíîâü îòëè÷íû íà 1. Ïîýòîìó ñâîéñòâî ñîõðàíÿåòñÿ è íà âñåõ øàãàõ ïîñòðîåíèÿ.
Âòîðîå íàáëþäåíèå. Ïðàâîå ïîääåðåâî ñ êîðíåì
=

1
2
ñîâïàäàåò ñ ëåâûì ïîääåðåâîì ñ êîðíåì
, åñëè
2
1
«ïåðåâåðíóòü» åãî äðîáè.
0
1
Îáúÿñíåíèå — òàêæå èíäóêòèâíîå.
è
—
1
1
1
1
ïðåäêè ëåâîãî ïîääåðåâà;
è
— ïðåäêè ïðàâî1
0
ãî ïîääåðåâà. Âèäèì, ÷òî äëÿ ïðåäêîâ ïîääåðåâüåâ
ñâîéñòâî âûïîëíÿåòñÿ. Ïðè÷åì ïîñòðîåíèå ìåäèàíò,
î÷åâèäíî, íå íàðóøàåò åãî.
Ââåäåì îáîçíà÷åíèÿ. Ïóñòü S — íåêîòîðàÿ LR-

ñòðîêà. f(S) — äðîáü, ñîîòâåòñòâóþùàÿ S. S — ñòðîêà, ïîëó÷åííàÿ èç ñòðîêè S åå èíâåðòèðîâàíèåì,
ò. å. çàìåíîé L íà R è R íà L. Íàïðèìåð, f(LRRL) =
7
5
, à f(LRRL) = f(RLLR) = .
5
7
Ïåðåâåäåì òåïåðü íàáëþäåíèÿ íà ÿçûê îáîçíà÷åíèé.

=

Ïåðâîå:
f(RS) = f(S) + 1
èëè
f(S) = f(RS) – 1
Âòîðîå:
f(RS) =
Îòêóäà:

f ( LS) =

1
f (S )

1
f ( LS)

(1)

.

=

1

f ( RS)
1
f (S )
=
=
1
(
f
S) + 1
+1
f (S )

=

1
f (S ) + 1

=

èëè
f ( RS) =

f ( LS)
.
1 - f ( LS)

(2)

Íà ýòèõ äâóõ ôîðìóëàõ (1) è (2) îñíîâûâàþòñÿ
íîâûå àëãîðèòìû ïåðåâîäîâ, áîëåå ëàêîíè÷íûå è
êðàñèâûå. Âòîðîé ðàç çàäàåìñÿ òåìè æå âîïðîñàìè:
Êàê ïî äàííîìó ïîëîæèòåëüíîìó ðàöèîíàëüíîìó ÷èñëó ïîñòðîèòü LR-ñòðîêó?
Åñëè à > b, òî åñòü âîçìîæíîñòü ïðèìåíèòü ôîðìóëó (1), ïîñêîëüêó ïåðâûì ñèìâîëîì â ïðåäñòàâa
ëåíèè òàêîé äðîáè âñåãäà áóäåò R, èëè f(RS) = .
b
Âûâîäèì R. Çàäà÷à ñâîäèòñÿ ê îòûñêàíèþ ïðåäñòàâëåíèÿ äëÿ äðîáè
a
a-b
f (S) = f ( RS) - 1 = - 1 =
.
b
b
Åñëè æå à < b, òî åñòü âîçìîæíîñòü ïðèìåíèòü
ôîðìóëó (2), ïîñêîëüêó ïåðâûì ñèìâîëîì â ïðåäñòàâëåíèè òàêîé äðîáè âñåãäà áóäåò L, èëè f(LS) =
a
= . Âûâîäèì L. Çàäà÷à ñâîäèòñÿ ê îòûñêàíèþ ïðåäb
ñòàâëåíèÿ äëÿ äðîáè
a
f ( LS)
a
.
f (S ) =
= b =
1 - f ( LS) 1 - a
b-a
b
Ïðîäîëæàåì òàêîé ïðîöåññ ïîëó÷åíèÿ î÷åðåäíîãî ñèìâîëà ïðåäñòàâëåíèÿ è ñâåäåíèÿ çàäà÷è êî
âñå áîëåå ïðîñòûì äðîáÿì, ïîêà ýòî âîçìîæíî. Îñòàíîâêà àëãîðèòìà ïðîèçîéäåò ïðè a = b.

Òàê, åñëè

a 7
= , òî ïîñëåäîâàòåëüíî ïîëó÷àåì:
b 3

a

7

4

1

1

1
1

b

3

3

3

2

LR-ñòðîêà

R

R

L

L

Çàäà÷à 3.
Íàïèøèòå ôóíêöèþ, êîòîðàÿ ïî äàííîìó ïîëî-

a
íàõîäèò åãî
b
ïðåäñòàâëåíèå â ñèñòåìå ñ÷èñëåíèÿ Øòåðíà—Áðîêî. Èñïîëüçóéòå íîâûé àëãîðèòì.

æèòåëüíîìó ðàöèîíàëüíîìó ÷èñëó

73

ISSN 0234-0453 • ИНФОРМАТИКА И ОБРАЗОВАНИЕ • 2012 • № 5 (234)
Ðåøåíèå.

begin
a:=1; b:=1;
for i:=length(s) downto 1 do
if s[i]='L'
then b:=b+a
else a:=a+b;
end;

function ToSB(a, b: word): string;
var s: string;
begin
s:='';
while ab do
if a --">