187
CHINA RING考
植 松 茂 暢
第1図の九連環は，中国で2000年以上昔に作られ，西洋に伝わり CHINA
RING と呼ばれ，日本へは17世紀ごろには既に伝わっていたという。現在も 同類の玩具が多く作られ市販されている。第1図の九連環は第2図の環を9個 連ねたものと同じと考えられるので， CHINARINGとしては第2図の塑の ものをとり，問題は第3図の状態から 紐をRINGに通すことにより第4図 の状態に変えることであるとします。 CHINARINGの解法については， 古くから研究され，この一般教育研究 第18号においても小林氏によって論じ られています。 ここでは，CHINARINGの解法を マイコンのプログラミングの立場から 考察する。 第1図 第2図 A B C D 第4図 第3図植 松・ 茂 暢 188 1．解法のTaぐticsについて CHINARINGの解法を環の数がn＝2，n＝3の場合など簡単な場合につい て考察すると，解法はつぎの4個の Tacticから成ることが帰納的に容易にわ かる。 （1）UP してCOVER（UC） 第5図の状態から第6図の状態に変える操作 （2）UNCOVER してDOWN（UD） 挽作UCの逆操作で，第6図の状態を第5図の状態に変える操作 （3）UP してSEPARATE（US） 第7図の状態から第8図の状態に変える操作
189 CHINA RING考
（4）DOWN してLEVEL（DL）
操作USの逆操作で，第8図の状態を第7図の状態に変える操作
2．解法のStrategyCHINARINGの問題解決には，第9図のように，i番目の棒まで囲んだ紐
をi−1番目の樺まで囲むようにすることが基本で，これをnからn−1，n−2， …，2と進めるとよい。そこでつぎの2つの操作を定義する。（1）STEP FORWARD（SFi）
第9図のように，棒の囲みを一・歩前進させる振作 （2）STEP BACK（SI∋i） 操作SFの逆操作で，棒の囲みを−・歩後退させる操作 第9図第9図で操作SFiを行うには，RINGiについて操作UCを行ない，つぎ
に囲いを1番目の棒から2番目の棒に後退させるSBヱ，2番目から3番目に後 退するSB3，‥，SBi＿1を行ない，最後にDLをすればよい。すなわちSFi＝UC＋SB2＋SB，＋…l＋SBト1＋DLl
① 以上のことを逆に見れば，i−1番目の棒まで囲んだ紐をi番目の棒まで囲むよ うに後退させる操作SBiになるからSBi＝US＋SFト1＋SFi＿2＋・…＋SF2＋UD
①となる。CHINA RINGの解法は第3図を第4図に変えることであるから，
植 松 茂 暢 190
RINGの数がn個のときの解法は
SOLn＝SFn＋SFn＿1＋…＋SF2
である。 StI・at喝y①，④，⑧のうち①，⑧は再帰的定義であってFORTRAN言語， ALGOL言語などではプログラミングすることばできない。しかしLISP言 語では，この定義をこのままの形でプログラミングすることができる。第11図 は環の数が4個のとき，LISP言語のプログラムを実行した結果である。 り：l1‖㌧→旧 王寺：− 工トト王■丁王剛 申ユー∵んて︺ヰ5畠T−︹︹こり■いl L l R・E：】．l・ −Ilt 臣l【−・ ‥R・〔；tl［t・ tロー E；l‘［t （（白二・E：二・l∴t い ‥一目−〔：tl●、・1・ ・・Rlローl−［− ・：白：・巳二・仁［．・ 白 日：・l−、い 事百 日tI■ ぎノ・ 用 E；＝ −【■■ −・：1百・lt r’・ t Fl臼l一、・r・ tlH ヒ王I＿・r＝ ■二自 E：し【：り tし！P 甜伯 に削1EF：：l 一：二l．1F，榊J【：t 5EF一和洋汀E：・ t＝ト紆：l：li碓二ドニ 荷トjDiニりコ州イ り．】‡FI封仰 望：EF■R鍔：RTE：t り」Flき］ト拒 に鉦艦Rニ‘ ・：■D〔lU＝ 榊抑 LEりEL．：・ くl」伸ニl二Il，肱F：l■神化■［り二‖朴j く．【■祀削目 口†旧 L＿EしtELニー り．j薯＝t：〕トJ【）仁亡軋tER二二・ 8 ・しIP Rトj【二・5EF■R拝：RT■E：：‘ 圧糾‡亡l招請一 甜附［州一昭ノ ・「りl榊j Rト附 LEllEl■ ‖．鰐■ 剛柑l．1：lttE筐●− ・【り：砧IH 卯損 LEりEL‘ 第11図 第11図について説明する。 （A）BCD は，Aの環の棒にのみ紐がかかっている INITIALの状態を示している。また （（（A）BC）D） は，第12図のようにAの環の樺を囲ん だ紐がAの環を通って上り Dの環の 棒まで囲んだ（点線の部分）状態から， 操作USによってCの環を通して紐を 第12医lCHINA RING考
191上にあげた状態になったことを示している。他は類推できるであろう。
3．もう1つのStrategy
CHINA RING の解法のもう1つのStrategyは，第13図の実線の状態を
REVERSE（REVi）して点線の状態に変える操作を用いる方法である。 第13図 第14図 第14図の実線のようにi番目の棒を囲んだ紐（ロ）の状態をi−1番目の棒を囲んだ紐（ハ）の状態に変化させる操作をTRANSFER（TRi）とすると
TRi＝REVi＋SB2＋SB3＋…＋SBト1
と表わすことができる。i番目の環の棒を囲む紐（イ）をi−1番目の環の棒を 囲む紐（ハ）の状態に変化させる操作は，i≒n のときは，i＋1番目の環を通してLIFT しなければならないので，CHINA RINGの解法は
SOLn＝TRn＋（LIFT＋TRn＿1）＋…＋（uFT＋TR2）＋LIFT①
となる。このStrategyでLISP言語でプログラミングして実行した結果が第15図である。REVERSEを回数に入れていないのは，紐が環の中をくぐらない からである。
植 松 茂 暢 （一rニIHト膵Iヰ：− ￠ り＝1†■目礼∴・ 192 ︹ロ ︹H 一：：F：E廿IEF：5E二・ り！ド’fl＝D さ：：Eド■！祁モ自†E：・ り．．什げ：＝L．1ER F削骨〔：り：：旭日二‘ り用＝− 甜濫・罰≡戸口托11■rEニ・ ・：．し甲 ロー拒 仁■：：霊■二Il．1ER：・ −：［：り：ル榊 揮・ぎにIiEl‡El∴t tl．．J‖lニlニ礼IE托 ロト拒【：り：）しl廿：− （二】…エ；＝ぎー一 く鍔：EリEF；：5E：・ く童．．1Ft RH［：・ご三走F■鞘耶吊‘E了：・ ・：l．什忙仇JE拝：RトJD【昭l湖山 （．l．．．‡F■i■：・ t二REしJEド：5E1 （。i”王！＝T〉 l 門ヒ一日 −1− −I l ●H■〓∵H 卜lノ ユ J ヰ 5 亡一 一 l ⊂1 1㊥ 11 日王L． ：＋： −H∵H⊥H−H−日日
州臼
﹁し
■■■− 臣 l こし ︻ ′ l− ■ R〓出 ︹n rL − R二日 一日一日 ． ■ ︰ ︵∴L●l −ビ一日穴一 一〓−H︻H 第15図 4．解法の手数について多くの書物で説明しているCHINARINGの解法はREVERSEを用いない
方法であり，手数の計算もそれによっている。ここでも先づ，それによって説
明しよう。操作SFiの手数をm（SFi）で示し，他の操作の手数も，これにならうこと
にする。公式①，④より
m（SFi）＝1＋m（SB2）＋m（SB3）＋…＋m（SBipl）＋1 m（SBi）＝1＋m（SFi＿1）＋m（SE卜2）＋…＋m（SF2）＋1 となり，また明らかに m（SFi）＝m（SBi） であるから m（SOLn）＝m（SFn）＋m（SFn＿1）＋l・・＋m（SF2）＝2（m（SFn＿1）＋m（SFn，2）＋…＋m（SF2））＋2
＝22‡m（SFn＿2）＋m（SFn＿3）＋・…＋m（SF2））＋22＋2CHINA RING考
193 ■●●●●● ＝2n￣2m（SF2）＋2n￣2＋2n￣3＋…＋2 ＝2n−2 このように解法の手数を計算したが，これは環の中を紐が通る回数を数えた手 数である。操作 UC では UP するとき紐が環の中を通るので1回と数え， COVERするときは紐が環の外を通るので回数に入れていない。 同じ解法でも，操作UCをUPで1回，COVERで1回，封2回の手数と 数えると m（SFi）＝2＋m（SB2）＋m（SB3）＋…＋m（SBト1）＋1 m（SBi）＝1＋m（SFi＿1）＋m（SFi＿2）＋…＋m（SF2）＋2 となり，前と同様に計算して− m（SOLn）＝3（2n￣1−1） となる。 REVERSEを用いたときの解法の手数は，紐がRINGの中を通る回数のみ 数えるならつぎのようになる。④より m（TRi）＝m（SB2）＋m（SB3）＋…＋m（SBト1） ＝2＋2（m（SB2）＋m（SB3）＋…＋m（SBi＿2）） ＝2＋22＋22（m（SB2）＋m（SB3）＋・…＋m（SB卜3）） ＝2＋22＋…＋2i￣3＋2i￣3m（SB2） ＝2＋22＋…＋2卜3＋2i￣2＝2i￣1−2 従って，解法の手数は⑤より m（SOLn）＝（2n￣1−2）＋（1＋2n￣2−2）＋（ト十2n￣i−2）＋… ＋（1＋2i−2）＋1 ＝2n−n−1植 松 茂 暢 194 となる。このように，操作 REVERSEを用いる解法は多くの書物に記されて いる手数2n−2より少い回数となる。 多くの書物には「CHINARINGの解法の手数は2n−2である」ように託 されているが，その書き方はあたかも「それが最小手数である」かのように書 かれているが，「CHINARINGは2n−2回の手数で解ける」とすべきであろ う。2n−2回が最小手数であることを証明することば容易でなく恐らく，すべ ての方法を片っ端しから調べるという方法でしか分らないこと，従って，一・般 には証明不可能な問題ではなかろうかと思う。 5．＄ASIC言語による解法プログラミング
CHINA RING の解法を学生に BASIC言語でプログラミングさせようと
思って，BASIC言語でもプログラミングしてみました。Strategy①，⑧は
BASIC言語を用いてプログラムできないので，つぎのような T鱒Ctic を用い ました。 操作UCとUD，操作US とDLは互に逆操作であるから，これらを続け て操作することば無意味である。したがって，続けて行なう操作はつぎのもの だけである。uc
uD
us
DL
操作USよりDLを，操作UCより UDを憂先するTacticをとります。操 作REVは，これを許すならば，可能な場合には，いつも優先します。このよ うに考えて作ったフロチャートが第16図です。ブログラムば簡単である。 最後にLISP言語のシステムを提供し，説明をして下さった本田道夫氏（経 済学部）に謝意を表記します。195
