Webページでは数式を表すためにLaTeX表記が使えるMathJaxを利用しています。 WebブラウザにはSafari/Chrome/Firefoxを使って下さい（IEでは表示できないようです。）

紙折り列とタートル

Pythonの亀グラフィックスのメソッドで確かめたように、亀グラフィックスでは

• 現在アタマが向いている方向に指定された距離だけ進む
• 現在のアタマの方向から指定された角度だけ左右に向きを変える

という単純な行動様式に従って地面を這って、その軌跡を描く。

ここでは、カメの動きを2つの文字 'd' と 'u' だけからなる紙折り文字列を使って、カメを這わせることを考えてみよう。

紙折り文字列

細長い紙の両端を持って水平に保す。 左端を固定したまま、紙の右端を反時計回りに回して左端に正確に重ねて2つに折り畳む操作を2 folding　といい、$F$ で表そう。 操作 $F$ で紙の長さは元の長さ $L$ の半分 $\frac{L}{2}$ になるので、 この操作を $n$ 　回続けると、紙の長さは次々と半分になって $L/2^n$ になる。

操作 $F$ の後に紙を開いてみる（unfolding）と \[ F:\quad \vee \qquad \rightarrow d \] のように 谷型の折れ目 $\vee$が1つある。 更に紙折り操作 $F$ を続けると \[ F^2:\quad \vee \vee\wedge\qquad \rightarrow ddu \] のように左端から、谷（$\vee$）、谷（$\vee$）、山（$\wedge$）の折れ目となっている。 では、もう一度 $F$ を行った $F^3$ の折れ目はどうなるだろうか。

確かめてみると、次のようなっているはずだ。 \[ F^3:\quad \vee \vee\wedge \vee \vee\wedge\wedge \qquad \rightarrow ddudduu \] 以下、谷型折れ目 $\vee$ を 記号 d で、山型折れ目 $\wedge$ を 記号 u で表すことにしよう。

この操作を続けて、$n$ 回の折り畳み操作で得られる（左端から読んだ）d または u の記号列を $F^n$ で表し、紙折り列という。

$n+1$ 回目の紙折り列 $F^{n+1}$ と $n$ 回目の紙折り列 $F^n$ とは次の関係にあることに直ぐに気づくはずだ（ $n$ 回折り畳んだ紙片を更にもう一回折り畳んで得られる紙折り列を考えると理解できる） \[ F^{n+1} = F^n \,d\, \overline{F^n} \] ここで、$\overline{F^n}$ は、次のような記号列を表している。

• 記号列 $F^n$ の記号 d と u とを入れ替え、
• さらに、記号列を反転（順番をひっくり返して逆順に）する

実際、次にように確認することができる。 \begin{align*} F &= d\\ F^2 &= F\, d\, \overline{F} =d \,d\, \overline{d} = d d u\\ F^3 &= F^2\, d\, \overline{F^2} = d d u\, d\, \overline{d d u} = ddu\,d\, duu\\ F^4 &= F^3\, d\, \overline{F^3} =ddudduu\, d\, \overline{ddudduu}=ddudduu\, d\, dduuduu \end{align*}

$n$回目の紙折り列を生成する

$n$回目の紙折り列を文字 'd' と 'u' からなる文字列として生成することは難しくない。 次の3つを実行すればよい。

• 文字列 mystring 1 と mystring2 の連接は mystring 1 + mystring2 である。
• 2つの検索文字列を「同時に置き換える」の技法を使って、文字列 'd' と 'u' とを入れ換える。
• 文字列の反転

次は、紙折り操作 $F$ をstep 回（1以上を仮定）繰り返してに得られる紙折り文字列を返す関数 paper2folding_string(step) である。 1回目の紙折り文字列 を folding = 'd' としておき、4,5行目で folging + 'd' + [foldingの入れ替え反転] で次回の紙折り文字列を求めている。

def paper2folding_string(step):
    # step is assumed step > 0
    folding = 'd'
    for i in range(1, step):
        folding = folding + 'd' + folding.replace('d','x').replace('u','d').replace('x','u')[::-1]
    return folding

次のスクリプト turtle_paperfolding.py は、5回までの紙折り記号列を文字列としてprintしている。

#!/usr/bin/env python
# -*- coding: utf-8 -*-


import turtle

def paper2folding_string(step):
    # step is assumed step > 0
    folding = 'd'
    for i in range(1, step):
        folding = folding + 'd' + folding.replace('d','x').replace('u','d').replace('x','u')[::-1]
    return folding


for i in range(1, 5):
    print 'i = ', i, ': ', paper2folding_string(i)

カメに紙折り曲線を描かせる

文字 'd' と 'u' からなる紙折り文字列の文字を先頭から読んで、カメに進むべき左右方向（いれずれの左右90°に頭を向けさせる）を指示して、カメを這わせよう。

プログラミング上扱いやすくするために、文字列を関数 list を使って文字からなるリストにしておく。 たとえば、次のようである。

>>> mylist = 'ddudduu'
>>> list(mylist)
['d', 'd', 'u', 'd', 'd', 'u', 'u']

次は、たとえば、4回目の紙折り文字列リストを mylist = list(paper2folding_string(4)) とした上で、順番に文字列を読み込んだときに、カメの向きを変えながら這わせている。

length = 50
mykame.forward(length)
for symbol in mylist:
    if symbol == 'd':
        mykame.left(90)
    elif symbol == 'u':
        mykame.right(90)
    mykame.forward(length)

ドラゴン dragon曲線との関係

ドラゴン dragon曲線で指摘したように、紙折り曲線はドラゴン曲線を与えている。

---

Copyright 2004 水谷正大