\input style ߸À°¼¸´°»Ì½ÃÎ Á¾À¸À¾²ºÃ ¸½¾³´° ¾¿¸Á˲°Î º°º \hslogo-°»³¾À¸Â¼; ; ¾±¾·½°Çµ½¸µ ú°·Ë²°µÂ ½° Å°À°ºÂµÀ ¸·¼µ½µ½¸Ï ¿µÀµ¼µ½½ËÅ~$l$ ¸~$r$. ÒµÀŽ¸¹ ÂÀµÃ³¾»Ì½¸º Á¾¾Â²µÂÁ²õ İ·µ ¿¾ÁÂÀ¾µ½¸Ï ¿¸À°¼¸´Ë, º¾³´°~$r=N$, ° $l$~ñ˲°µÂ ´¾~$1$; ½¸¶½¸¹ ÂÀµÃ³¾»Ì½¸º ¿Àµ´Á°²»ÏµÂ Ä°·Ã ²Ë±¾À°, º¾³´°~$l=1$, ° $r$~ñ˲°µÂ ´¾~$1$. Ò Â°±».~2 ¿¾º°·°½ ¿À¾ÆµÁÁ ¿¸À°¼¸´°»Ì½¾¹ Á¾À¸À¾²º¸ ²Áµ µŠ¶µ ȵÁ½°´Æ°Â¸ ǸÁµ». (Ò º°¶´¾¹ ÁÂÀ¾ºµ ¸·¾±À°¶µ½¾ Á¾Á¾Ͻ¸µ ¿¾Á»µ È°³°~H2, Áº¾±º¸ ú°·Ë²°Î ½° ·½°Çµ½¸Ï ¿µÀµ¼µ½½ËÅ~$l$ ¸~$r$.) {\catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}} \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}} \def\cell#1{$\phantom{[}#1\phantom{]}$\bskip} \htable{â°±»¸Æ° 2}% {ßÀ¸¼µÀ ¿¸À°¼¸´°»Ì½¾¹ Á¾À¸À¾²º¸}% { \cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&% \cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&% \hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\hfil\cr K_1 & K_2 & K_3 & K_4 & K_5 & K_6 & K_7 & K_8 & K_9 & K_{10} & K_{11} & K_{12} & K_{13} & K_{14} & K_{15} & K_{16} & l & r & K \cr 503 & 087 & 512 & 061 & 908 & 170 & 897 &[275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 703] & 8 & 16 & 275\cr 503 & 087 & 512 & 061 & 908 & 170 &[897 & 703 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 275] & 7 & 16 & 897\cr 503 & 087 & 512 & 061 & 908 &[170 & 897 & 703 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 275] & 6 & 16 & 170\cr 503 & 087 & 512 & 061 &[908 & 612 & 897 & 703 & 653 & 426 & 154 & 509 & 170 & 677 & 765 & 275] & 5 & 16 & 908\cr 503 & 087 & 512 &[061 & 908 & 612 & 897 & 703 & 653 & 426 & 154 & 509 & 170 & 677 & 765 & 275] & 4 & 16 & 061\cr 503 & 087 &[512 & 703 & 908 & 612 & 897 & 275 & 653 & 426 & 154 & 509 & 170 & 677 & 765 & 061] & 3 & 16 & 512\cr 503 &[087 & 897 & 703 & 908 & 612 & 765 & 275 & 653 & 426 & 154 & 509 & 170 & 677 & 512 & 061] & 2 & 16 & 087\cr [503 & 908 & 897 & 703 & 426 & 612 & 765 & 275 & 653 & 087 & 154 & 509 & 170 & 677 & 512 & 061] & 1 & 16 & 503\cr [908 & 703 & 897 & 653 & 426 & 612 & 765 & 275 & 503 & 087 & 154 & 509 & 170 & 677 & 512] & 908 & 1 & 15 & 061\cr [897 & 703 & 765 & 653 & 426 & 612 & 677 & 275 & 503 & 087 & 154 & 509 & 170 & 061] & 897 & 908 & 1 & 14 & 512\cr [765 & 703 & 677 & 653 & 426 & 612 & 512 & 275 & 503 & 087 & 154 & 509 & 170] & 765 & 897 & 908 & 1 & 13 & 061\cr [703 & 653 & 677 & 503 & 426 & 612 & 512 & 275 & 061 & 087 & 154 & 509] & 703 & 765 & 897 & 908 & 1 & 12 & 170\cr [677 & 653 & 612 & 503 & 426 & 509 & 512 & 275 & 061 & 087 & 154] & 677 & 703 & 765 & 897 & 908 & 1 & 11 & 170\cr [653 & 503 & 612 & 275 & 426 & 509 & 512 & 170 & 061 & 087] & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 10 & 154\cr [612 & 503 & 512 & 275 & 426 & 509 & 154 & 170 & 061]& 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 9 & 087\cr [512 & 503 & 509 & 275 & 426 & 087 & 154 & 170]& 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 8 & 061\cr [509 & 503 & 154 & 275 & 426 & 087 & 061]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 7 & 170\cr [503 & 426 & 154 & 276 & 170 & 087]& 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 6 & 061\cr [426 & 275 & 154 & 061 & 176]& 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 5 & 087\cr [275 & 170 & 154 & 061]& 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 4 & 087\cr [170 & 087 & 154]& 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 3 & 061\cr [154 & 087]& 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 2 & 061\cr [061]& 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 & 1 & 1 & 061\cr }} \prog H.(߸À°¼¸´°»Ì½°Ï Á¾À¸À¾²º°.) ×°¿¸Á¸, ½°Å¾´ÏɸµÁÏ ² Ïǵ¹º°Å Á~$|INPUT|+1$ ¿¾~$|INPUT|+N$, Á¾À¸ÀÃÎÂÁÏ ¿À¸ ¿¾¼¾É¸ °»³¾À¸Â¼°~H; Àµ³¸ÁÂÀË ¿À¸½¸¼°Î Á»µ´ÃÎɸµ ·½°Çµ½¸Ï: $|rI1|\equiv l-1$, $|rI2|\equiv r-1$, $|rI3|\equiv i$, $|rI4|\equiv j$, $|rI5|\equiv r-l$, $|rA|\equiv K \equiv R$, $|rX|\equiv R_j$. \code START & ENT1 & N/2 & 1 & H1. Ý°Ç°»Ì½°Ï ÃÁ°½¾²º° $l\asg \floor{N/2}+1$. & ENT2 & N-1 & 1 & $r\asg N$. 1H & DEC1 & 1 & \floor{N/2} & $l\asg l-1$. & LDA & INPUT+1,1 & \floor{N/2} & $R\asg R_l$, $K\asg K_l$. 3H & ENT4 & 1,1 & P & H3. ßÀ¸³¾Â¾²¸ÂÌÁÏ º "¿À¾Â°Áº¸²°½¸Î". $j\asg l$. & ENT5 & 0,2 & P & DEC5 & 0,1 & P & $|rI5|\asg r-j$. %% 180 & JMP & 4à & P & Ú È°³Ã~H4. 5H & LDX & INPUT 4 & B+A-D & H5. Ý°¹Â¸ "±¾»Ìȵ³¾" Á˽°. & CMPX & INPUT+1,4 & B+A-D & JOE & 6F & B+A-D & ßµÀµÅ¾´, µÁ»¸~$K_j\ge K_{j+1}$. & INC4 & 1 & C & Ò ¿À¾Â¸²½¾¼ Á»ÃÇ°µ ÃÁ°½¾²¸ÂÌ~$j\asg j+1$. & DECS & 1 & C 9H & LDX & INPUT,4 & C+D & $|rX|\asg R_j$. 6H & CMPA & INPUT,4 & B+A & H6. Ѿ»Ìȵ~$K$? & JGE & 8F & B+A & Ú H8, µÁ»¸~$K\ge K_j$. 7H & STX & INPUT,3 & B & H7. ß¾´½ÏÂÌ µ³¾ ²²µÀÅ. $R_i \asg R_j$. 4H & ENT3 & 0,4 & B+P & H4. ßÀ¾´²¸½ÃÂÌÁÏ ²½¸·. & DEC5 & 0,4 & B+P & $|rI5|\asg|rI5|-j$. & INC4 & 0,4 & B+P & $j\asg j+j$. & J5P & 5B & B+P & Ú H5, µÁ»¸~$j1$. & STA & INPUT+1 & 1 & $R_1\asg R$. \endcode \progend í° ¿À¾³À°¼¼° ¿À¸±»¸·¸Âµ»Ì½¾ »¸ÈÌ ²´²¾µ ´»¸½½µµ ¿À¾³À°¼¼Ë~S, ½¾ ¿À¸ ±¾»ÌȸÅ~$N$ ¾½° ³¾À°·´¾ ±¾»µµ ÍÄĵºÂ¸²½°. Õµ ²Àµ¼Ï À°±¾ÂË ·°²¸Á¸Â ¾Â $$ \eqalign{ P &= N+\floor{N/2}-2 = \hbox{ǸÁ»¾ "¿À¾Â°Áº¸²°½¸¹"};\cr A &= \hbox{ǸÁ»¾ ¿À¾Â°Áº¸²°½¸¹, ¿À¸ º¾Â¾ÀËÅ º»ÎÇ~$K$ ² º¾½Æµ ¿¾¿°´°µÂ ²¾ ²½ÃÂÀµ½½¸¹ ÷µ» ¿¸À°¼¸´Ë};\cr B &=\hbox{Áü¼°À½¾µ ǸÁ»¾ º»Îǵ¹, ¿À¾Á¼¾ÂÀµ½½ËÅ ²¾ ²Àµ¼Ï ¿À¾Â°Áº¸²°½¸¹;}\cr C &= \hbox{ǸÁ»¾ ¿À¸Á²°¸²°½¸¹~$j\asg j+1$ ² È°³µ~H5};\cr D &= \hbox{ǸÁ»¾ Á»ÃÇ°µ², º¾³´° ² È°³µ~H4 $j=r$.}\cr } $$ í¸ ²µ»¸Ç¸½Ë ¿À¾°½°»¸·¸À¾²°½Ë ½¸¶µ. Ú°º ¿¾º°·Ë²°µÂ ¿À°ºÂ¸º°, ¾½¸ ÁÀ°²½¸Âµ»Ì½¾ ¼°»¾ ¾Âº»¾½ÏÎÂÁÏ ¾Â Á²¾¸Å ÁÀµ´½¸Å ·½°Çµ½¸¹: $$ \matrix{ A \approx 0.349 N;\hfill & B \approx N \log_2 N - 1.87 N;\hfill \cr C \approx {1\over 2}N\log_2 N - 0.9N;\hfill & D \approx \ln N.\hfill\cr } \eqno(7) $$ ßÀ¸~$N=1000$, ½°¿À¸¼µÀ, ǵÂËÀµ ͺÁ¿µÀ¸¼µ½Â° Á¾ Á»ÃÇ°¹½Ë¼¸ ¸Áž´½Ë¼¸ ´°½½Ë¼¸ ¿¾º°·°»¸ Á¾¾Â²µÂÁ²µ½½¾ Àµ·Ã»Ì°ÂË $(A, B, C, D)=(371, 8055, 4056, 12)$, $(351, 8072, 4087, 14)$, $(341, 8094, 4017, 8)$, $(340, 8108, 4083, 13)$. ޱɵµ ²Àµ¼Ï À°±¾ÂË %% 181 \bye