журнал «Информатика и образование» - Информатика и образование 2012 №05
Название: | Информатика и образование 2012 №05 | |
Автор: | журнал «Информатика и образование» | |
Жанр: | Околокомпьютерная литература, Газеты и журналы, Современные российские издания | |
Изадано в серии: | неизвестно | |
Издательство: | неизвестно | |
Год издания: | 2012 | |
ISBN: | неизвестно | |
Отзывы: | Комментировать | |
Рейтинг: | ||
Поделись книгой с друзьями! Помощь сайту: донат на оплату сервера |
Краткое содержание книги "Информатика и образование 2012 №05"
Аннотация к этой книге отсутствует.
Читаем онлайн "Информатика и образование 2012 №05". [Страница - 74]
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 --">
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 --">
Книги схожие с «Информатика и образование 2012 №05» по жанру, серии, автору или названию:
журнал «Информатика и образование» - Информатика и образование 2011 №08 Жанр: Газеты и журналы Год издания: 2011 |
Другие книги автора « журнал «Информатика и образование»»:
журнал «Информатика и образование» - Информатика и образование 1988 №02 Жанр: Советские издания Год издания: 1988 |
журнал «Информатика и образование» - Информатика и образование 2011 №01 Жанр: Околокомпьютерная литература Год издания: 2011 |
журнал «Информатика и образование» - Информатика и образование 2017 №08 Жанр: Газеты и журналы Год издания: 2017 |