Единое окно доступа к образовательным ресурсам

Троичная система и равновесие

Голосов: 0

Авторы статьи, опубликованной в рубрике "Учебная мастерская", рассказывают об уравновешенной троичной системе счисления, о свойствах этой системы. Разобраны задачи о взвешивании и логические задачи, изящно решаемые с помощью симметричного троичного представления чисел.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    Àãàôîíîâà È.Â., Äìèòðèåâà Î.Ì.




                                                    Àãàôîíîâà Èðèíà Âèòàëüåâíà,
                                                   Äìèòðèåâà Îêñàíà Ìèõàéëîâíà


            ÒÐÎÈ×ÍÀß ÑÈÑÒÅÌÀ È ÐÀÂÍÎÂÅÑÈÅ

×ÅÌ ÒÐÈ ÌÎÆÅÒ ÁÛÒÜ ËÓ×ØÅ ÄÂÓÕ?             ñòàâëåíèå äàííûõ è èñïîëüçîâàòü òðèòû è
                                           òðàéòû âìåñòî áèòîâ è áàéòîâ?
                                                 ×àùå âñåãî ïðè îáñóæäåíèè äîñòî-
                                           èíñòâ òðîè÷íîé ñèñòåìû ñ÷èñëåíèÿ ãîâî-
                                           ðÿò î åå ýêîíîìè÷íîñòè.
                                                 Äåéñòâèòåëüíî, òðîè÷íàÿ ñèñòåìà
                                           ñ÷èñëåíèÿ ýêîíîìè÷íåå äðóãèõ ñèñòåì, åñëè
                                           ïîêàçàòåëåì ýêîíîìè÷íîñòè ñ÷èòàòü êîëè-
                                           ÷åñòâî ÷èñåë, êîòîðûå ìîæíî çàïèñàòü ñ
                                           ïîìîùüþ ôèêñèðîâàííîãî êîëè÷åñòâà
                                           öèôð äàííîé ñèñòåìû. Äîêàçûâàþò ýòî òàê.
                                                 Îáîçíà÷èì N (m, x) – êîëè÷åñòâî
                                           ÷èñåë, êîòîðûå ìîæíî çàïèñàòü ñ ïîìî-
                                           ùüþ m ðàçðÿäîâ ñèñòåìû ñ îñíîâàíèåì õ.
                                                  äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ ñ ïî-
                                           ìîùüþ m ðàçðÿäîâ ìîæíî çàïèñàòü 2 m íà-
                                           òóðàëüíûõ ÷èñåë, â òðîè÷íîé 3 m, è âîîá-
      Ó÷åáíèêè èí-                         ùå â ñèñòåìå ñ îñíîâàíèåì õ áóäåò
ôîðìàòèêè ðàññêàçûâàþò                     N (m, x) = xm . Íà ýòó çàïèñü óéäåò mx öèôð
íàì î äâîè÷íîé ñèñòåìå                     äàííîé ñèñòåìû.
ñ÷èñëåíèÿ è î òîì, ïî÷åìó èìåííî ýòà ñè-         Çàôèêñèðîâàâ êîëè÷åñòâî èñïîëüçóå-
ñòåìà, ïðåäñòàâëÿþùàÿ äàííûå è êîìàí-      ìûõ öèôð n = mx, ïîëó÷àåì ÷èñëî ðàçðÿäîâ
äû öèôðàìè 0 è 1, ðåàëèçîâàíà â ñîâðå-                                             n

ìåííûõ êîìïüþòåðàõ.                        m = n/x è êîëè÷åñòâî ÷èñåë N (n/x, x) = x .
                                                                                   x
                                                            n
      Èçâåñòíî, îäíàêî, ÷òî â 60-õ ãîäàõ
                                                 Ôóíêöèÿ x x èññëåäóåòñÿ ñðåäñòâàìè
ó÷åíûìè Ìîñêîâñêîãî óíèâåðñèòåòà (ãëàâ-
íûé êîíñòðóêòîð — Íèêîëàé Ïåòðîâè÷         ìàòåìàòè÷åñêîãî àíàëèçà. Åå ãðàôèê ïðè
Áðóñåíöîâ) áûë ñïðîåêòèðîâàí è óñïåø-      ëþáîì n èìååò åäèíñòâåííûé ìàêñèìóì
íî ðàáîòàë òðîè÷íûé êîìïüþòåð, ïîëó-       ïðè x = e = 2,718281828... (ñì. ðèñóíîê 1).
÷èâøèé íàçâàíèå «Ñåòóíü». Áûëî âûïóùå-           Íàèáîëåå áëèçêèì ê e ÿâëÿåòñÿ îñ-
íî íåñêîëüêî äåñÿòêîâ ìàøèí, ðàçìåùàâ-     íîâàíèå õ = 3, îíî è áóäåò ñàìûì ýêîíî-
øèõñÿ ïî áîëüøåé ÷àñòè â âûñøèõ ó÷åá-      ìè÷íûì. Äåéñòâèòåëüíî, äâà òðîè÷íûõ ðàç-
íûõ çàâåäåíèÿõ. Äðàìàòè÷åñêóþ èñòîðèþ      ðÿäà (6 öèôð) ïîçâîëÿþò çàïèñàòü 9 ÷è-
òðîè÷íîãî êîìïüþòåðà è åãî îïèñàíèå        ñåë, â òî âðåìÿ êàê òðè äâîè÷íûõ ðàçðÿäà
ìîæíî íàéòè â [1].                         (òîæå 6 öèôð) – òîëüêî 8.
      Êàêîâû æå áûëè ïðè÷èíû, ïîáóäèâ-           Îäíàêî íàçâàíèå «ýêîíîìè÷íîñòü»
øèå ðàçðàáîò÷èêîâ âûáðàòü òðîè÷íîå ïðåä-   åùå íå îçíà÷àåò âûãîäó âî âñåõ îòíîøåíè-

78        © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2004 ã.


                                                     Òðîè÷íàÿ ñèñòåìà è ðàâíîâåñèå

ÿõ. Ñàì îòåö «Ñåòóíè» Í.Ï. Áðóñåíöîâ ãî-
âîðèë îá «èëëþçîðíîé ýêîíîìíîñòè òðî-
è÷íîãî êîäà» è íå åå ñ÷èòàë ãëàâíûì äîñ-
òîèíñòâîì òðîè÷íîé çàïèñè. Âûáîð òðîè÷-
íîé ñèñòåìû îí îáîñíîâûâàë ïðåæäå âñå-
ãî òåì, ÷òî ñ òðåìÿ öèôðàìè âîçìîæåí
íàòóðàëüíûé êîä ÷èñåë ñî çíàêîì, à ñ äâó-
ìÿ íåâîçìîæåí. Áðóñåíöîâ îòìå÷àë, ÷òî
äâîè÷íûì êîäîì åñòåñòâåííî ïðåäñòàâè-                              Ðèñóíîê 1.
ìû ëèáî òîëüêî íåîòðèöàòåëüíûå ÷èñëà,
ëèáî òîëüêî íåïîëîæèòåëüíûå. À âîò â òðî-     ìû ñòåïåíåé ÷èñëà 3. Äëÿ öåëîãî a ýòî âû-
è÷íîì êîäå ñ öèôðàìè +1, 0, –1 (êàê è âî      ðàæåíèå
âñÿêîé ñèñòåìå ñ íå÷åòíûì ÷èñëîì öèôð)          a = αn–1 ⋅ 3n–1 + αn–2 ⋅ 3n–2 +… ... + α1 ⋅ 31 + α0
èìååò ìåñòî åñòåñòâåííîå ïðåäñòàâëåíèå
                                                    Öèôðû αk ìîãóò ïðèíèìàòü îäíî èç
÷èñåë ñî çíàêîì. Ïðè ýòîì íåò íåîáõîäè-
                                              òðåõ áàçîâûõ çíà÷åíèé è îáû÷íî áåðóòñÿ
ìîñòè â ñïåöèàëüíîì ðàçðÿäå çíàêà: åñëè
                                              èç íàáîðà {0, 1, 2}. Íàïðèìåð,
ñòàðøàÿ çíà÷àùàÿ öèôðà ÷èñëà ïîëîæèòåëü-
íà, òî è ÷èñëî ïîëîæèòåëüíîå, åñëè îòðè-               11 = 9 + 2 = 1 ⋅ 32 + 0 ⋅ 31 + 2,
öàòåëüíà, òî ÷èñëî îòðèöàòåëüíîå.             òàê ÷òî ìîæíî çàïèñàòü 11 = (102)3. Íèæ-
      Ïðèâëåêàòåëüíà ïðîñòîòà àðèôìåòè-       íèé èíäåêñ 3 îçíà÷àåò, ÷òî ÷èñëî 102 çà-
÷åñêèõ îïåðàöèé íàä ÷èñëàìè ñî çíàêîì â       ïèñàíî â òðîè÷íîé ñèñòåìå. Åñëè â ýòîé
òðîè÷íîé ñèììåòðè÷íîé ñèñòåìå. Âàæíî è        ñèñòåìå íàäî ïðåäñòàâèòü îòðèöàòåëüíîå
òî, ÷òî óñå÷åíèå äëèíû ÷èñëà â òàêîé ñè-      ÷èñëî, òî çíàê ïîòðåáóåòñÿ óêàçûâàòü äî-
ñòåìå ðàâíîñèëüíî ïðàâèëüíîìó îêðóãëå-        ïîëíèòåëüíî.
íèþ, ïîñêîëüêó àáñîëþòíàÿ âåëè÷èíà îò-              Íàñ áóäåò ïðåæäå âñåãî èíòåðåñîâàòü
áðàñûâàåìîé ÷àñòè ÷èñëà âñåãäà ìåíüøå         òðîè÷íàÿ ñèñòåìà, èñïîëüçóþùàÿ áàçîâûé
ïîëîâèíû åäèíèöû ïîñëåäíåãî ñîõðàíÿå-         íàáîð èç öèôð {–1, 0, 1}. Îíà íàçûâàåòñÿ
ìîãî ðàçðÿäà.                                 ñèììåòðè÷íîé, óðàâíîâåøåííîé èëè ñáà-
                                              ëàíñèðîâàííîé. ×òîáû öèôðà –1 íå îòëè-
                ÁÀËÀÍÑ –1, 0, 1               ÷àëàñü îò 0 è 1 ëèøíåé ïîçèöèåé äëÿ çíà-
                                              êà, âûáåðåì äëÿ íåå îáîçíà÷åíèå 1 . Òàê
                                              êàê 11 = 9 + 3 – 1 = 1 ⋅ 32 + 1 ⋅ 31 + 1 , òî çà-
                                              ïèøåì 11=( 11 1 ) 3 , ãäå íèæíèé èíäåêñ
                                               3 áóäåò îçíà÷àòü çàïèñü â óðàâíîâåøåí-
                                              íîé òðîè÷íîé ñèñòåìå.
                                                    Ïðèâåäåì ïðåäñòàâëåíèå öåëûõ ÷è-
                                              ñåë îò – 6 äî 6 â óðàâíîâåøåííîé òðîè÷-
                                              íîé ñèñòåìå (ñì. òàáëèöó 1).
                                                    Êàê âèäèì, çíàê ÷èñëà ïðèñóòñòâó-
                                              åò â ñàìîì åãî ïðåäñòàâëåíèè: åñëè ïåð-
                                              âàÿ öèôðà 1 , òî ÷èñëî îòðèöàòåëüíîå, à
                                              åñëè 1, òî ïîëîæèòåëüíîå. ×òîáû èç ïî-
     Ïîãîâîðèì îá óïîìÿíóòîé òðîè÷íîé         ëîæèòåëüíîãî ÷èñëà a ïîëó÷èòü ýòî îòðè-
ñèñòåìå ïîäðîáíåå. Òðîè÷íàÿ ñèñòåìà èñ-       öàòåëüíîå ÷èñëî (–a), íàäî â óðàâíîâå-
ïîëüçóåò ïðåäñòàâëåíèå ÷èñëà a â âèäå ñóì-    øåííîì òðîè÷íîì ïðåäñòàâëåíèè ÷èñëà

                                        Òàáëèöà 1.

   a     –6       –5     –4   –3   –2    –1     0      1      2       3       4        5       6
 (a) 3   11 0     1 11   11   10   11     1     0      1     11      10      11     11 1     110

Ó×ÅÁÍÀß ÌÀÑÒÅÐÑÊÀß                                                                              79


Àãàôîíîâà È.Â., Äìèòðèåâà Î.Ì.

                            Òàáëèöà 2.                      íåò â 3 ðàçà áîëüøå, òî åñòü
                                                            3Q (n – 1) = Q (n) – 1, è èõ
  (a) 3    ( a′ ) 3   ( a ′′ ) 3 a         a′      a ′′
                                                            àáñîëþòíûå âåëè÷èíû âñå
  001       1 11       1 1 0     1         11      –12      áóäóò ðàçëè÷íû è îõâàòÿò
  0 11      11 0       1 01      2          6      –8       âåñü íàáîð ïîëîæèòåëüíûõ
  010       11 1       1 01      3          7      –10      ÷èñåë, çàïèñûâàåìûõ n òðî-
  011       11 1       1 00      4          5      –9       è÷íûìè ðàçðÿäàìè, êðîìå
                                                            íàèáîëüøåãî ÷èñëà Q (n),
                                              ñîñòîÿùåãî èç n åäèíèö. Ýòî áóäåò î÷åíü
ïðîèçâåñòè îäíîâðåìåííóþ çàìåíó âñåõ
                                              êðàñèâûé íàáîð ÷èñåë, óðàâíîâåøåííûé
öèôð 1 íà 1 , à âñåõ 1 íà 1. Òàêóþ çàìåíó
                                              ïî âñåì ðàçðÿäàì. Ïîñìîòðèì, êàê îí âûã-
íàçîâåì èíâåðñèåé.
                                              ëÿäèò ïðè n = 3. Èñõîäíûé íàáîð äâóõðàç-
       Èñïîëüçóÿ n òðîè÷íûõ ðàçðÿäîâ,
                                              ðÿäíûõ ïîëîæèòåëüíûõ ÷èñåë ñ ïðèïèñàí-
ìîæíî çàïèñàòü 3n ðàçëè÷íûõ öåëûõ ÷èñåë,
                                              íûìè ñëåâà íóëÿìè ñîñòîèò èç ÷åòûðåõ ÷è-
              3n − 1                 3n − 1
â òîì ÷èñëå          ïîëîæèòåëüíûõ,           ñåë:
                 2                     2
îòðèöàòåëüíûõ è 0. Ýòî áóäóò ÷èñëà îò                        a       (a) 3
                                                                     1       0   01
( 1 1 1 ... 1 1 ) 3 äî ( 111...3 ) 3 , íàèáîëüøåå
  14 42 3                12 11
                          4 4                                        2       0   11
     n öèôð             n öèôð
                                                                     3       0   10
                                          3n − 1                     4       0   11
èç êîòîðûõ îáîçíà÷èì Q(n) =                      =
                                            2
= ( 111...3 ) 3 .                                           Çàíåñåì â òàáëèöó ÷èñëà a è èõ öèê-
    12 11
     44
      n öèôð                                          ëè÷åñêèå ñäâèãè a′ è a′′ â òðîè÷íîì è â
       Ïîìèìî îïåðàöèè èíâåðñèè, îòìå-                äåñÿòè÷íîì ïðåäñòàâëåíèè è ïîëó÷èì 12
òèì åùå îäíó îäíîìåñòíóþ îïåðàöèþ, âîç-               ÷èñåë (ñì. òàáëèöó 2).
ìîæíóþ â òðîè÷íîé ñèñòåìå – îïåðàöèþ                        Îáðàòèì âíèìàíèå íà ïîðàçðÿäíóþ
ïîðàçðÿäíîãî öèêëè÷åñêîãî ñäâèãà. Öèêëè-              ñèììåòðèþ: â êàæäîì òðîè÷íîì ðàçðÿäå
÷åñêèì ñäâèãîì âïðàâî ÷èñëà a, çàïèñàí-               ïîðîâíó öèôð 0, 1 è 1 (ïî 4 öèôðû).
íîãî ïîñðåäñòâîì ðîâíî n ðàçðÿäîâ òðî-                      Ýòîò ïîðàçðÿäíî óðàâíîâåøåí-
è÷íîé ñèììåòðè÷íîé ñèñòåìû (âîçìîæíî,                 íûé íàáîð èç 12 ÷èñåë îáîçíà÷èì
ñ äîáàâëåíèåì íóëåé ñëåâà) íàçîâåì ÷èñ-               D12 = {+1, +2, +3, +4, +5, +6, +7, +11, –8,
ëî a′ , ïîëó÷åííîå èç a ïîðàçðÿäíîé çàìå-             –9, –10, –12}. Îí áóäåò èñïîëüçîâàí ïðè
íîé öèôð 0 íà 1, 1 íà 1 è 1 íà 0. Êðàòêàÿ             ðåøåíèè îäíîé èç ïðèâîäèìûõ íèæå çà-
ñõåìà çàìåíû 0 → 1 → 1 → 0. Òàêèì æå îá-              äà÷.
ðàçîì îò a′ ìîæíî ïåðåéòè ê a′′ . Î÷åâèä-                   Ïîñìîòðèì, êàê â òðîè÷íîé óðàâíî-
íî, ÷òî a′′′ = a è ÷òî a + a′ + a′′ = 0. ×èñëî        âåøåííîé ñèñòåìå âûãëÿäÿò îñíîâíûå
a′′ ïîëó÷àåòñÿ èç a çàìåíîé 0 ← 1← 1 ← 0,             àðèôìåòè÷åñêèå îïåðàöèè ñëîæåíèÿ è óì-
òî åñòü äâóêðàòíûé öèêëè÷åñêèé ñäâèã                  íîæåíèÿ.
âïðàâî – ýòî öèêëè÷åñêèé ñäâèã âëåâî.                       Òàáëèöà ñëîæåíèÿ â ðàññìàòðèâàå-
       Íàïðèìåð, äëÿ a = ( 1 1 1 0 ) 3 ïîëó-          ìîé ñèñòåìå èìååò âèä
÷èì a′ = ( 1 001 ) 3 , a′′ = ( 011 1 ) 3 . Äåñÿòè÷-
íîå ïðåäñòàâëåíèå ýòèõ ÷èñåë 15, –26                    1 + 1 = 11       1 +0= 1       1 +1=0
è 11.                                                    0+0=0           0+1=1        1 + 1 = 11
       Âîçüìåì âñå Q (n – 1) ïîëîæèòåëü-
íûõ ÷èñåë, çàïèñûâàåìûõ (n – 1) òðîè÷-                     Ñóììû 1 + 1 è 1 + 1 îáðàçóþòñÿ ïå-
íûìè ðàçðÿäàìè. Ê êàæäîìó èç íèõ ïðè-                 ðåíîñîì ñîîòâåòñòâóþùåé öèôðû â ñëå-
ïèøåì ñëåâà 0 è äëÿ êàæäîãî íàéäåì ñäâèã              äóþùèé ðàçðÿä è äîáàâëåíèåì öèôðû ïðî-
âïðàâî (ïîëîæèòåëüíîå ÷èñëî) è ñäâèã                  òèâîïîëîæíîãî çíàêà, à îñòàëüíûå ñóììû
âëåâî (îòðèöàòåëüíîå ÷èñëî). ×èñåë ñòà-               ïîëó÷àþòñÿ åùå ïðîùå.

80             © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2004 ã.


                                                       Òðîè÷íàÿ ñèñòåìà è ðàâíîâåñèå

      Òàáëèöà óìíîæåíèÿ ñîâñåì ïðîñòà:
    1⋅1 = 1          1 ⋅0 = 0       1 ⋅1 = 1
    0⋅0 = 0          0⋅1 = 0        1⋅1 = 1
     Ïðèâåäåì ïðèìåð óìíîæåíèÿ «ñòîë-
áèêîì» (óìíîæàåì 39 íà 2 â òðîè÷íîé óðàâ-
íîâåøåííîé ñèñòåìå):
         Ч   111 0                                                Ðèñóíîê 2.
             11
                                                         Êàêîé ìèíèìàëüíûé íàáîð ãèðü, ïî
       111
                                                  îäíîé ãèðå êàæäîãî âåñà, ïîçâîëÿåò âçâåñèòü
      111                                         íà äâóõ÷àøåâûõ âåñàõ âñåâîçìîæíûå ãðóçû â
      1 0 010                                     1 êã, 2 êã è ò. ä. äî N êã?
      Ïîëîæèòåëüíîå öåëîå ÷èñëî ìîæíî                   Ðåøåíèå ýòîé çàäà÷è èçâåñòíî â äâóõ
ïåðåâåñòè èç îáû÷íîé äåñÿòè÷íîé ôîðìû             âàðèàíòàõ:
çàïèñè â óðàâíîâåøåííóþ òðîè÷íóþ ñëåã-                  1) ãðóç íàõîäèòñÿ íà îäíîé ÷àøå âå-
êà èçìåíåííûì îáû÷íûì àëãîðèòìîì ïîñ-             ñîâ, à âñå ãèðè äîëæíû ïîìåùàòüñÿ íà
ëåäîâàòåëüíîãî äåëåíèÿ ñ îñòàòêîì [2]. Èç-        äðóãóþ;
ìåíåíèå çàêëþ÷àåòñÿ â òîì, ÷òî äåëåíèå                  2) ãèðè ðàçðåøàåòñÿ ïîìåùàòü íà îáå
íà 3 ñ îñòàòêîì èíîãäà çàìåíÿåòñÿ äåëå-           ÷àøè âåñîâ, òî åñòü è íà òó, ãäå íàõîäèòñÿ
íèåì íà 3 «ñ èçáûòêîì». À èìåííî: äàííîå          ãðóç.
÷èñëî a äåëÿò íà 3 ïî ïðàâèëó äåëåíèÿ ñ                  [3] ïðèâåäåíû ðåøåíèÿ äëÿ îáîèõ
îñòàòêîì. Åñëè îñòàòîê 0 èëè 1, çàïîìè-           âàðèàíòîâ, îïèðàþùèåñÿ íà çàïèñü ÷èñåë
íàþò åãî, à åñëè îñòàòîê 2, òî âìåñòî íåãî        â äâîè÷íîé è òðîè÷íîé ñèñòåìàõ ñ÷èñëå-
çàïîìèíàþò îñòàòîê, ðàâíûé 1 , è â êà÷å-          íèÿ, ñîîòâåòñòâåííî. Íàì ïðåäñòàâëÿåòñÿ
                                a +1              èíòåðåñíûì ïîêàçàòü, êàê êðàñèâî âûãëÿ-
ñòâå ÷àñòíîãî ïðèíèìàþò              . Ïî ýòîìó   äèò ðåøåíèå, åñëè ïðèáåãíóòü ê óðàâíîâå-
                                  3
ïðàâèëó ïîëó÷åííîå ÷àñòíîå ñíîâà äåëÿò            øåííîé òðîè÷íîé ñèñòåìå. Áîëåå òîãî,
íà 3 è ò. ä., ïîêà ÷àñòíîå íå ñòàíåò ðàâíî 1.     ìîæíî ñêàçàòü, ÷òî ýòà çàäà÷à åñòåñòâåííî
Çàïèñûâàþò ýòî ÷àñòíîå, à çà íèì îñòàòêè          ïîðîæäàåò òàêóþ ñèñòåìó ñ÷èñëåíèÿ.
îò äåëåíèÿ â îáðàòíîì ïîðÿäêå.                          Ïîìåñòèì ãðóç, ñêàæåì, íà ëåâóþ
      Íàïðèìåð, äëÿ ÷èñëà 15 ïîëó÷àåòñÿ           ÷àøó âåñîâ. Ðàñïîëîæåíèå ãèðü áóäåì îò-
ïîñëåäîâàòåëüíîñòü îñòàòêîâ 0, 1 , 1 è            ìå÷àòü çàïèñÿìè èç öèôð 0, 1 è 1 .  ýòîé
ïîñëåäíåå ÷àñòíîå 1 (ñì. ðèñóíîê 2).              çàïèñè 1 áóäåò îçíà÷àòü, ÷òî ãèðÿ êëàäåò-
Ýòî äàåò ïðåäñòàâëåíèå 15 = (1 1 1 0 ) 3 .        ñÿ íà ëåâóþ ÷àøó, 1 – ÷òî íà ïðàâóþ, à
                                                  0 – ÷òî äàííàÿ ãèðÿ íà âåñû íå êëàäåòñÿ.
       ÍÀ ÐÀÇÍÛÕ ×ÀØÀÕ ÂÅÑΠ                     Ïîçèöèÿ öèôðû 1 èëè 1 áóäåò îïðåäåëÿòü
                                                  âåñ ãèðè: k-ÿ ïîçèöèÿ (ïðè îòñ÷åòå ñïðàâà
     Ðàññìîòðèì äâå çàäà÷è î âçâåøèâà-            íàëåâî) ñîîòâåòñòâóåò ãèðå âåñîì 3k–1 êã.
íèè, èçÿùíî ðåøàåìûå ñ ïîìîùüþ ñèì-
ìåòðè÷íîãî òðîè÷íîãî ïðåäñòàâëåíèÿ ÷è-
ñåë.

     I. Çàäà÷à î âûáîðå ñèñòåìû ãèðü äëÿ
âçâåøèâàíèÿ íà ðû÷àæíûõ âåñàõ.
     Ýòà çàäà÷à, êðàòêî íàçûâàåìàÿ «çà-
äà÷åé î ãèðÿõ» è ïðåäëîæåííàÿ â XIII âåêå
èòàëüÿíñêèì ìàòåìàòèêîì Ëåîíàðäî Ïè-
çàíñêèì (Ôèáîíà÷÷è), ôîðìóëèðóåòñÿ òàê:


Ó×ÅÁÍÀß ÌÀÑÒÅÐÑÊÀß                                                                       81


Àãàôîíîâà È.Â., Äìèòðèåâà Î.Ì.

                            Òàáëèöà 3.                                                3n − 3
                                                                       ëî ìîíåò N ≤          . ×åì
 ÷èñëî âçâåøèâàíèé n       2     3        4       5        6                            2
                                                                   áîëüøå N, òåì ñèëüíåå
 ÷èñëî ìîíåò mn            3     12       39      120      363
                                                                   âïå÷àòëÿåò ïðèâåäåííûé
 (mn) 3                    10    110      1110    11110    111110
                                                                   ðåçóëüòàò: äîñòàòî÷íî,
                                                                   íàïðèìåð, âñåãî ïÿòè
Íàáîð ãèðü, òàêèì îáðàçîì, ñîñòîèò èç
                                                   âçâåøèâàíèé, ÷òîáû îáíàðóæèòü ôàëüøè-
ãèðü âåñîì 1, 3, 9, 27 è òàê äàëåå êèëî-
                                                   âóþ ìîíåòó ñðåäè íàáîðà â 120 ìîíåò.
ãðàììîâ, à êîëè÷åñòâî èñïîëüçóåìûõ ãèðü
                                                                             3n − 3
çàâèñèò îò N.                                             Îáîçíà÷èì mn =            è âçãëÿíåì íà
      Íàïðèìåð, çàïèñü 1 1 1 0 áóäåò îçíà-
                                                                               2
                                                   ýòîò ðåçóëüòàò â ñâåòå òðîè÷íîé óðàâíîâå-
÷àòü, ÷òî íà ïðàâóþ ÷àøó âåñîâ êëàäåòñÿ            øåííîé ñèñòåìû. Èìååì ñëåäóþùåå ñîîò-
ãèðÿ â 27 êã, à íà ëåâóþ ãèðè â 9 è 3 êã.          âåòñòâèå (òàáëèöà 3).
Ãèðÿ â 1 êã íà âåñû íå êëàäåòñÿ. Òàêèì                    Èç íèæíåé ñòðîêè òàáëèöû âèäíî:
îáðàçîì, âçâåøåí ãðóç â 15 êã, ÷òî åñòå-           ÷èñëî mn åñòü íàèáîëüøåå èç ÷èñåë, êîòî-
ñòâåííî, òàê êàê (ñì.âûøå) 15 = ( 1 1 1 0 ) 3 .    ðûå ìîæíî çàïèñàòü ñ ïîìîùüþ n ðàçðÿ-
        27 êã    9 êã     3 êã     1 êã            äîâ òðîè÷íîé óðàâíîâåøåííîé ñèñòåìû,
          1       1        1        0              åñëè ïîòðåáîâàòü äîïîëíèòåëüíî, ÷òîáû íå
       óðàâíîâåøåííîé òðîè÷íîé ñèñòå-             âñå öèôðû â çàïèñè áûëè îäèíàêîâûìè.
ìå ìîæíî çàïèñàòü ëþáîå íàòóðàëüíîå ÷èñ-                  Ìåòîä ðåøåíèÿ çàäà÷è II, èñïîëüçó-
ëî è íåìåäëåííî ïîëó÷èòü ðàñïîëîæåíèå              þùèé òðîè÷íóþ íóìåðàöèþ ìîíåò, íàçî-
ãèðü äëÿ ãðóçà ñîîòâåòñòâóþùåãî âåñà. Ñà-          âåì ìåòîäîì Äàéñîíà, ñëåäóÿ [4].
ìûé áîëüøîé âåñ áóäåò, êàê ìû óæå âèäå-                   Ïîêàæåì, êàê ðàáîòàåò ýòîò ìåòîä
                    3n − 1                         ïðè N = 12 (êëàññè÷åñêèé ñëó÷àé).
ëè, ðàâåí Q (n) =          , òî åñòü Q (1) =1,            Ïðèïèøåì êàæäîé èç 12-òè ìîíåò
                      2
Q (2) = 4, Q (3) = 13, Q (4) = 40, Q (5) = 121,    íîìåð, ñíàáæåííûé çíàêîì è âçÿòûé èç
Q (6) = 364 è òàê äàëåå.                           ïîðàçðÿäíî óðàâíîâåøåííîãî íàáîðà
      Èòàê, äëÿ âçâåøèâàíèÿ ãðóçîâ, íà-            D 12 = {+1, +2, +3, +4, +5, +6, +7,–8, –9,
ïðèìåð, îò 1 äî 300 êã äîñòàòî÷íî 6 ãèðü           –10, +11, –12} ={001, 01 1 , 010, 011, 1 1 1 ,
âåñîì â 1, 3, 9, 27, 81, 243 êã, à ïÿòè ãèðü       1 1 1 , 1 1 0, 1 1 1, 1 01, 1 00, 1 0 1 , 11 1 ,
íå õâàòèò, òàê êàê Q (5) < 300 < Q (6). Ðàç-       1 1 0} 3 .
ìåùåíèå ãèðü äëÿ âåñà q ïðîèçâîäèòñÿ ñî-                  Ïîðÿäîê âçâåøèâàíèÿ îïðåäåëÿåòñÿ
ãëàñíî òðîè÷íîìó ïðåäñòàâëåíèþ ÷èñëà q.            òðîè÷íûìè íîìåðàìè ìîíåò. Ïðè i-ì âçâå-
                                                   øèâàíèè (i = 1, 2, 3) íà îäíó ÷àøó âåñîâ
     II. Çàäà÷à îá îáíàðóæåíèè ôàëüøè-             (íàçîâåì åå ÷àøà 1 ) êëàäóòñÿ ìîíåòû, íî-
âîé ìîíåòû.                                        ìåðà êîòîðûõ èìåþò i-þ öèôðó 1 , íà ïðà-

      Èìååòñÿ N îäèíàêîâûõ ñ âèäó ìîíåò.
Îäíà èç íèõ ôàëüøèâàÿ, ÷òî ìîæíî îïðåäå-
ëèòü ïî âåñó: îíà ëåã÷å èëè òÿæåëåå äðóãèõ.
Òðåáóåòñÿ âçâåøèâàíèåì íà äâóõ÷àøåâûõ âå-
ñàõ (áåç ãèðü) âûÿâèòü çà ìèíèìàëüíîå ÷èñëî
âçâåøèâàíèé, êàêàÿ èç ìîíåò ôàëüøèâàÿ è
áóäåò ëè îíà ëåã÷å èëè òÿæåëåå îñòàëüíûõ?
       Ýòà çàäà÷à èçâåñòíà â ëèòåðàòóðå êàê
çàäà÷à î 12 ìîíåòàõ. Íàçâàíà îíà òàê ïîòî-
ìó, ÷òî, êàê ìû óâèäèì íèæå, ðåøàåòñÿ
çà 3 âçâåøèâàíèÿ, åñëè ìîíåò 12 èëè ìåíü-
øå, è âîîáùå çà n âçâåøèâàíèé, åñëè ÷èñ-



82          © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2004 ã.


                                                          Òðîè÷íàÿ ñèñòåìà è ðàâíîâåñèå

âóþ, êîòîðóþ íàçîâåì ÷àøåé 1, – íîìåðà                     Ðåçóëüòàò 1 1 0 äàåò ÷èñëî ( 1 1 0) 3 =
ñ i-é öèôðîé 1. Îáðàòèì âíèìàíèå, ÷òî                = –6 è ïîêàçûâàåò, ÷òî ôàëüøèâîé ÿâëÿ-
êàæäîå èç âçâåøèâàíèé ïðîâîäèòñÿ íåçà-               åòñÿ ìîíåòà ñ íîìåðîì 6 è ÷òî ýòà ìîíåòà
âèñèìî îò ðåçóëüòàòîâ ïðåäûäóùèõ.                    ëåã÷å äðóãèõ.
      Ðåçóëüòàò êàæäîãî âçâåøèâàíèÿ îáî-                   b) Äîïóñòèì, ïîëó÷èëîñü, ÷òî â ïåð-
çíà÷èì òðîè÷íîé öèôðîé α i = 1 , åñëè ïå-            âûé ðàç òÿæåëåå ÷àøà 1, âî âòîðîé è â òðå-
ðåâåñèëà ÷àøà 1 , αi =1, åñëè ïåðåâåñèëà             òèé íàáîðû ìîíåò ðàâíû ïî âåñó.
÷àøà 1, è αi = 0, åñëè âåñû îñòàëèñü â ðàâ-                Ðåçóëüòàò 1 0 0 äàåò ÷èñëî (1 0 0) 3 =
íîâåñèè.                                             = 9 è ïîêàçûâàåò, ÷òî ôàëüøèâîé ÿâëÿåò-
      Öèôðû αi, çàïèñàííûå â ïîðÿäêå                 ñÿ ìîíåòà ñ íîìåðîì –9 è ÷òî ýòà ìîíåòà
âçâåøèâàíèé, îáðàçóþò òðîè÷íîå ÷èñëî                 ëåã÷å äðóãèõ.
a = α1 ⋅ 3n–1 + α 2 ⋅ 3n–2 + ... + αn–1 ⋅ 31 + αn.
                                 …
      ×èñëî a – ëèáî íîìåð êàêîé-òî ìî-                      ÍÅ ÒÎËÜÊÎ «ÄÀ» È «ÍÅÒ»
íåòû, ëèáî åãî èíâåðñèÿ (òîãäà íîìåð áó-
äåò – a). Ýòà ìîíåòà ôàëüøèâàÿ. Åñëè åå
íîìåð a, òî îíà òÿæåëåå äðóãèõ, à åñëè
íîìåð – a, òî ýòà ìîíåòà ëåã÷å äðóãèõ .
      Ýòîò âûâîä ñäåëàí èç ñëåäóþùèõ
ñîîáðàæåíèé.
      • Ðåçóëüòàò αi = 0 ãîâîðèò î òîì, ÷òî
ïðè i-ì âçâåøèâàíèè ôàëüøèâîé ìîíåòû
íà âåñàõ íå áûëî.  ýòîì ñëó÷àå 0 – i-ÿ öèô-
ðà â íîìåðå ìîíåòû.
      • Åñëè ôàëüøèâàÿ ìîíåòà áûëà òÿ-
æåëåå äðóãèõ, òî ðåçóëüòàò α i = 1 ãîâîðèò
î òîì, ÷òî ïðè i-ì âçâåøèâàíèè îíà áûëà
íà ÷àøå 1, ðåçóëüòàò αi = 1 – î òîì, ÷òî
                                                           Î òðîè÷íîé ëîãèêå ñëûøàëè ìíîãèå.
ïðè i-ì âçâåøèâàíèè îíà áûëà íà ÷àøå 1 .
                                                     Ýòî ÷àñòíûé ñëó÷àé êîíå÷íîçíà÷íîé ëî-
Öèôðà α i – i-ÿ öèôðà â íîìåðå ìîíåòû.
                                                     ãèêè. Ìû ëèøü ñëåãêà êîñíåìñÿ ýòîé îá-
      • Åñëè ôàëüøèâàÿ ìîíåòà áûëà ëåã-
                                                     øèðíîé òåìû, ðàññìîòðåâ èçâåñòíûå çà-
÷å äðóãèõ, òî ðåçóëüòàò α i = 1 ãîâîðèò î
                                                     äà÷è î çàäóìàííîì ÷èñëå [5].
òîì, ÷òî ïðè i-ì âçâåøèâàíèè îíà áûëà
                                                           Íåêòî çàäóìàë ÷èñëî îò 1 äî N. Âû
íà ÷àøå 1 , ðåçóëüòàò α i = 1 – î òîì, ÷òî
                                                     äîëæíû îòãàäàòü ýòî ÷èñëî, çàäàâ íàèìåíü-
ïðè i-ì âçâåøèâàíèè îíà áûëà íà ÷àøå 1.              øåå êîëè÷åñòâî âîïðîñîâ, íà êîòîðûå çà-
Öèôðà α i – èíâåðñèÿ i-é öèôðû â íîìåðå              äóìàâøèé îáÿçàí ïðàâäèâî îòâå÷àòü
ìîíåòû.                                                    1) «äà» èëè «íåò»;
      Ïðèâåäåì ïðèìåð, êàê çà 3 âçâåøè-                    2) «äà», «íåò» èëè «íå çíàþ».
âàíèÿ îïðåäåëèòü ôàëüøèâóþ ìîíåòó ñðå-                     Ðåøåíèå ïåðâîé çàäà÷è ñâîäèòñÿ ê
äè 12-òè ìîíåò, êîòîðûå ïðîíóìåðóåì ÷èñ-             çàïèñè ÷èñëà â äâîè÷íîé ñèñòåìå ñ÷èñëå-
ëàìè èç íàáîðà D12.                                  íèÿ. ×èñëî âîïðîñîâ çàâèñèò îò N è äëÿ
1-å âçâåøèâàíèå: íà ÷àøå 1 ìîíåòû –8,                N ≤ 2m íå ïðåâûøàåò m. Íàïðèìåð, äëÿ
–9, –10, –12, íà ÷àøå 1 ìîíåòû 5, 6, 7, 11.          N = 100 < 128 < 27 äîñòàòî÷íî ñåìè âîïðî-
2-å âçâåøèâàíèå: íà ÷àøå 1 ìîíåòû 5, 6,              ñîâ, ïåðâûì èç êîòîðûõ ìîæåò áûòü âîï-
7, –12, íà ÷àøå 1 ìîíåòû 2, 3, 4, 11.                ðîñ «Áóäåò ëè çàäóìàííîå ÷èñëî áîëüøå
3-å âçâåøèâàíèå: íà ÷àøå 1 ìîíåòû 2, 5,              40?» Äàëüíåéøèå âîïðîñû çàâèñÿò îò ðà-
–10, 11 íà ÷àøå 1 ìîíåòû 1, 4, 7, 8.                 íåå ïîëó÷åííûõ îòâåòîâ è êàæäûé ðàç äå-
      a) Äîïóñòèì, ïîëó÷èëîñü, ÷òî â ïåð-            ëÿò îáëàñòü îòãàäûâàíèÿ ïîïîëàì èëè ïî-
âûé ðàç òÿæåëåå ÷àøà 1 , âî âòîðîé ÷àøà              ÷òè ïîïîëàì. Øåñòè âîïðîñîâ íå õâàòèò,
1, â òðåòèé íàáîðû ìîíåò ðàâíû ïî âåñó.              òàê êàê 100 > 64 = 26.

Ó×ÅÁÍÀß ÌÀÑÒÅÐÑÊÀß                                                                            83


Àãàôîíîâà È.Â., Äìèòðèåâà Î.Ì.

      Ìîæíî ïîñòðîèòü ñõåìó âîïðîñîâ è          èç äèàïàçîíà îò 1 äî 3m (âêëþ÷àÿ 3m, åñëè
èíà÷å. Äâîè÷íàÿ çàïèñü ÷èñëà 0 ≤ N < 2m ñî-     íå çàáûòü ñäåëàííîå âûøå çàìå÷àíèå è ïå-
äåðæèò íå áîëåå m öèôð. Äîïîëíèâ, åñëè          ðåâîäèòü â ýòîì ñëó÷àå â òðîè÷íûé êîä íå
íóæíî, ýòó çàïèñü íóëÿìè ñëåâà, ïîëó÷à-         N, à N–1). Îòðèöàòåëüíûå ÷èñëà íå çàäó-
åì ðîâíî m öèôð, êàæäóþ èç êîòîðûõ              ìûâàþòñÿ, òàê ÷òî óðàâíîâåøåííàÿ ñèñ-
ìîæíî îòãàäàòü çà 1 âîïðîñ «ßâëÿåòñÿ ëè         òåìà çäåñü íå íóæíà. ×èñëî áóäåò çàïèñû-
ýòà öèôðà åäèíèöåé?». Òàê êàê 0 íå çàäó-        âàòüñÿ â ñòàíäàðòíîé òðîè÷íîé ñèñòåìå ñ
ìûâàåòñÿ, òî ïðè N = 2m â äâîè÷íûé êîä          íàáîðîì öèôð {0, 1, 2}. Áóäóò èñïîëüçî-
ìîæíî ïåðåâîäèòü N–1, ÷òîáû è â ýòîì            âàòüñÿ âñå m ðàçðÿäîâ, ñëåâà ïðè íåîáõî-
ñëó÷àå õâàòèëî m âîïðîñîâ, íàäî òîëüêî          äèìîñòè áóäóò äîáàâëåíû íóëè. Âîïðîñ
íå çàáûòü ïðèáàâèòü 1 ê îòâåòó. Ïðèäåòñÿ        ìîæåò çâó÷àòü ïðèìåðíî òàê: «Åñëè ÿ çàäó-
åùå ïðåäîñòàâèòü çàäóìàâøåìó òàáëè÷êó           ìàë ÷èñëî, i-ÿ öèôðà êîòîðîãî îòëè÷àåòñÿ
äâîè÷íûõ ïðåäñòàâëåíèé âñåõ ÷èñåë îò 1          îò i-é öèôðû òâîåãî ÷èñëà, òî áóäåò ëè îíà
äî N.                                           ìåíüøå, ÷åì ó òåáÿ?» Ïðè îòâåòå «äà» çà-
      Íàñ áîëüøå èíòåðåñóåò âòîðàÿ çàäà-        ïèñûâàåì öèôðó 2, ïðè îòâåòå «íåò» –
÷à, ñâÿçàííàÿ ñ òðîè÷íîé ñèñòåìîé ñ÷èñ-         öèôðó 0, ïðè îòâåòå «íå çíàþ» – öèôðó 1.
ëåíèÿ. Ïðè N = 3 åå ìîæíî ðåøèòü çà îäèí               Åñëè, íàïðèìåð, N = 200, òî m = 5,
âîïðîñ, íàïðèìåð, òàêîé: «Åñëè ÿ çàäó-          òàê êàê 34 < 200 < 35. Åñëè íà 5 âîïðîñîâ
ìàë ÷èñëî, îòëè÷àþùååñÿ îò òâîåãî, òî           ïîëó÷åíà ïîñëåäîâàòåëüíîñòü îòâåòîâ «íå
áóäåò ëè îíî ìåíüøå, ÷åì òâîå?» Îòâåò           çíàþ», «äà», «íå çíàþ», «íåò», «äà», òî çà-
«äà» áóäåò îçíà÷àòü, ÷òî çàäóìàíî ÷èñëî         äóìàíî ÷èñëî (12102)3 = 146.
3, îòâåò «íåò» – ÷òî çàäóìàíî ÷èñëî 1, à               Áîëåå åñòåñòâåííîé âûãëÿäèò ñèñòå-
îòâåò «íå çíàþ» ñîîòâåòñòâóåò ÷èñëó 2.          ìà âîïðîñîâ, íå òàê ÿâíî ïðèáåãàþùàÿ ê
       òàêîì ñëó÷àå ìû ìîæåì îæèäàòü,          òðîè÷íîé ñèñòåìå. Åå ìîæíî ñâÿçàòü ñ äå-
÷òî çà îäèí âîïðîñ îòãàäûâàåòñÿ îäèí ðàç-       ëåíèåì äèàïàçîíà ïîèñêà íà òðè ÷àñòè.
ðÿä òðîè÷íîãî ïðåäñòàâëåíèÿ ÷èñëà è ÷òî         Ôîðìóëèðîâêè âîïðîñîâ ïðåäîñòàâëÿþòñÿ
çà m âîïðîñîâ ìû ìîæåì îòãàäàòü ÷èñëî           ÷èòàòåëþ.


      Ëèòåðàòóðà
      1. Ìàëèíîâñêèé Á.Í. Èñòîðèÿ âû÷èñëèòåëüíîé òåõíèêè â ëèöàõ. Êèåâ: Ôèðìà ÊÈÒ, ÏÒÎÎ
«ÀÑÊ», 1995.
      2. Øàóöóêîâà Ë.Ç. Îñíîâû èíôîðìàòèêè â âîïðîñàõ è îòâåòàõ. Ó÷åáíîå ïîñîáèå. Íàëü÷èê:
Èçäàòåëüñêèé öåíòð «ÝËÜ-ÔÀ», 1994.
      3. Ðîìàíîâñêèé È.Â., ×åðêàñîâà Ï.Ã. Íàáîðû èç íóëåé è åäèíèö: Çàî÷íàÿ øêîëà ñîâðåìåííî-
ãî ïðîãðàììèðîâàíèÿ. Çàíÿòèå 2: Ó÷åáíîå ïîñîáèå. ÑÏá.: Èçä-âî ÖÏÎ «Èíôîðìàòèçàöèÿ îáðàçî-
âàíèÿ», 1999.
      4. Øåñòîïàë Ã. Êàê îáíàðóæèòü ôàëüøèâóþ ìîíåòó. «Êâàíò», ¹ 10, 1979.
      5. Àëôóòîâà Í.Á., Óñòèíîâ À.Â. Àëãåáðà è òåîðèÿ ÷èñåë. Ñáîðíèê çàäà÷ äëÿ ìàòåìàòè÷åñêèõ
øêîë. Ì.: ÌÖÍÌÎ, 2002.




                                                Àãàôîíîâà Èðèíà Âèòàëüåâíà,
                                                äîöåíò êàôåäðû ìàòåìàòèêè
                                                Ñàíêò-Ïåòåðáóðãñêîãî Ìîðñêîãî
                                                Òåõíè÷åñêîãî óíèâåðñèòåòà,
                                                Äìèòðèåâà Îêñàíà Ìèõàéëîâíà,
                                                äîöåíò êàôåäðû ìàòåìàòèêè
                                                Ñàíêò-Ïåòåðáóðãñêîãî
                                                ãîñóäàðñòâåííîãî óíèâåðñèòåòà
                                                Òåëåêîììóíèêàöèé.

84         © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2004 ã.



    
Яндекс цитирования Яндекс.Метрика