« 2015年07月 | メイン | 2015年12月 »

2015年08月 アーカイブ

2015年08月10日

フィボナッチ数列の任意の項を高速に計算する方法

そんなプログラミングの問題を見かけて、反射的に思ったのは、一般項を用いることだった。
フィボナッチ数列の漸化式はan=an-1+an-2なので、一般項anを求めることは可能である。

3項を含む漸化式は、特性方程式を用いて解くのが基本であるが、やり方を忘れてしまったので、自己流で解いてみた。
a_{n+1} = a_{n} + a_{n-1}

a_{n+1} + Aa_n = (1+A)(a_n+ Aa_{n-1})
という形にできると、
(1+A)(a_n+ Aa_{n-1}) = (1+A)^2 (a_{n-1}+ Aa_{n-2}) = \cdots = (1+A)^n(a_1+Aa_0)
であることと、a1=1, a0=0であることを用いて
a_{n+1} + Aa_n = (1+A)^n
とできる。このAは、an-1の係数を見ると、(1+A)A=1となるAなので、A=(-1±√5)/2である。従って、

\left\{
\begin{array}{c}
a_{n+1} + \frac{-1+\sqrt{5}}{2} a_n = \left(1 + \frac{-1+\sqrt{5}}{2}\right)^n \\
a_{n+1} + \frac{-1-\sqrt{5}}{2} a_n = \left(1 + \frac{-1-\sqrt{5}}{2}\right)^n
\end{array}
\right.
であり、上の式から下の式を引いて整理すると、
a_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right) と求まる。
念の為申し上げるが、このanはnが何であろうとも整数である。実にミラクルである。

√5のn乗なんてのがあるのでは、誤差が出まくるだろうとは思ったが、CやJavaでは浮動小数点の精度が低くて無理でも、PythonのmathパッケージにMathematicaやMaxima並の驚異の性能が無いとは限らないので、試しに

#!/usr/bin/python
from math import pow
from math import sqrt

def fib(n):
    return int(1/sqrt(5)*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n)))

an_2 = 0  #a_{n-2}
an_1 = 0  #a_{n-1}
an = 1    #a_{n}
for i in range(1, 100):
    print "n =", i, "a_n =", an, "fib(n) =", fib(i)
    if fib(i) != an:
        print "error!"
    an_2 = an_1
    an_1 = an
    an = an_1 + an_2
とやってみた所、72項目で誤差が出た。
Maximaはn>200000でも正確な整数を弾き出す(下記入出力参照、下3桁が正しいことを確認)が、さすがにPythonでは無理だった。おそらく、Maximaは内部で√5を√5として保存しながら数式処理をしてるからであろう。Pythonの言語仕様上、pow()の結果は一度float値にしないといけないので、正確な整数値を出すには無限の精度が必要になってしまう。

Maximaへの入力とその出力
(%i1) 1/sqrt(5)*(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n),n=234567,ratsimp;
(%o1) 179607932890115544888825400217[48962 digits]014673023583001136817746498978

MathematicaやMaximaを使って良いなら、一般項を用いる方法もあるが、今回の問題は、「複数言語選択可能」としながら、MathematicaもMaximaも選択肢に無かった。 フィボナッチ数列のn項目を高速に計算する方法は、他には思い付かなかったのだが、少し調べると、計算量がO(log N)になる簡単な方法があった。

M=\pmatrix{1 & 1 \cr 1 & 0} とすると、Mn-1の{1,1}要素がフィボナッチ数列のn項目だというのが使える。
さらに、M=M*Mという計算を繰り返すことにより、M^(2k)は計算量少なく求められるので、Mn-1をM^(2k)の積とすることによって、高速に計算できる。
例えば、
M5 = 0*M8 · 1*M4 · 0*M2 · 1*M
M10 = 1*M8 · 0*M4 · 1*M2 · 0*M
であるように、2進数にした時の1のビットに対応するM^(2k)を掛け合わせれば良いのである。

従って、例えば次のようにすれば、n=10000でも高速に計算される。(Pythonで扱える整数の上限はメモリが許す限り無限である)

#!/usr/bin/python

class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a;
        self.b = b;
        self.c = c;
        self.d = d;
    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)
    
def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a

2015年08月30日

10キーで棋譜入力するiモードアプリ

筆者は未だにdocomoのガラケーを使っている。会社でも家でもネットに繋がったPCが手元にあるし、電車通勤ではないし、遠出も頻繁にはしないので、スマホを使う時間が無いのである。外出先では携帯電話は電話とメールとカメラさえ使えれば良く、音楽はiPodで聞くので、日常生活でスマホの必要性を感じる瞬間が全く無い。今だと携帯電話のランニングコストが年間2万円以下で済んでいるので、端末費合わせて2年で20万円かかるようなスマホを購入する気にはならない。

というより、今使ってるP-01Cを大変気に入っているのである。シンプルなデザインで軽くて薄くて自作アプリが動く。完璧である。

筆者はこのiモード携帯に自作の棋譜再生アプリをインストールして活用しており、筆者の1日数分間の将棋ライフに欠かせないものとなっている。

日々、数字ボタンと*#だけで将棋盤を操作していて、ある日、ふと、「7六歩」といった符号を761とかで入力できたら、意外と高速に棋譜入力できて、出先で棋譜を記録できて便利だったりしないか、と思った。筆者は時々、反省のために対局後に盤面を撮影するのだが、記憶力が無く、家に帰って写真を見ると既にそこまでの手順が再現できないことがよくあり、できるなら棋譜を記録したいのである。

携帯電話のアプリでよくある、カーソルキーで駒を選択して動かすUIは、ボタンを押す回数が尋常ではなく、あまりにも手間で時間がかかる。
パソコンやスマホであれば、棋譜入力はマウス操作やタッチパネル操作で行うのが通常で、これは相当に楽だし高速であるが、1手当たり3キーで入力できれば、それよりも速いのではなかろうか。
棋譜の符号に慣れている人でないと使入力しにくいだろうが(チェス初級者の筆者はコマンドライン版gnuchessのNf3とかBxf6といった符号入力に最後まで慣れなかった)、記録した棋譜は符号で書かれているのが一番読みやすいと思うので、そういう棋譜を求めるなら、記録される通りに符号で入力できるのが最善だと思う。


棋譜の符号の数字部分は2桁であり、数字ボタン2発で打てる。数字は1-9なので、0ボタンを「同」にすれば、到達地点の部分は全て2ストローク以内で入力できる。
その次の駒の種類(以下、3キー目と記す。実際には「同」なら2キー目である。)は、成駒を含めると14種類あるので、数字ボタン1回で入力可能とは限らないが、9種類以上の駒が1つのマス目に行ける(または打てる)ことは稀であるので、大抵数字ボタン1回で入力できる。
それ以上に入力が必要な場合というのは、「成」と「不成」がある場合と、同じ種類のそこに行ける(または打てる)駒が2つ以上あり、「打」「左」「引」とかで特定しないといけない場合である。飛車は2枚しかないので、例えば左右で特定するとして、最大でも「左成」「左不成」「右成」「右不成」の4通りである。角も2枚しか無いので同様、桂も最大2ヶ所からしか来ないので同様に最大4通りである。金の動きをする駒は成れないので、最大で「と」の場合に6つの駒を特定する為の6通りである。銀は最大4枚で全て盤上にあってそれぞれ「成」「不成」があれば8通りである。香歩は特定が必要になることがないので、「成」「不成」の2通りである。
従って、駒の種類より後の部分は最大8通りであり、8つのボタンに動的に割り当てれば、数字ボタン1回で入力できる。(以下、4キー目と記す。)

さらに、3キー目と4キー目の組み合わせが10種類を超えることは稀だから、それらをまとめて、例えば「玉」と「金左」と「金右」の選択肢が一緒に出るようにする方がボタンを押す回数は減るだろうが、5八金右は「5」「八」「金」「右」と4キーで入力する方が直感的だし、3キーで確定する場合の方が多いので、「金右」の時だけ異なるボタンになるのでなく、「金」のボタンが固定される方が、慣れによる入力速度UPが期待できるので、3キー目と4キー目は分ける方が良いだろう。

同じ理由で、3キー目は、数字ボタンに固定的に
1: 歩 2: 香 3: 桂 4: 銀 5: 金 6: 角 7: 飛 8: 玉
と割り当て、成駒はその時空いている番号とする方が良かろう。それも、空いてればなるべく成る前の駒の番号(馬なら角の6)、空いてなければなるべく成る前の駒の次になる(角、馬の順になる)ように、次に空いている番号にすると良いだろう。


という訳で、夏休みにそういうiアプリを作成した。

・スクリーンショット
1キー目待ち状態の画面

3キー目待ち状態の画面

4キー目待ち状態の画面

サブメニュー画面

i-mode用ダウンロードページへのリンク

・ソースコード
 iKifuRecorder.java
 Board.java
 KifTree.java
 CGI.java

・作成者
 maruinen(筆者のネット将棋でのハンドル)

3キー目は、選択し得る駒が10種類以下なら0-9ボタンで指定、11種類以上なら0をページ切替ボタンとした。
ソフトキーで棋譜入力モード/再生モードを切り替えたり、サブメニュー画面を開いたり、アプリを終了したりできる。
棋譜の途中から入力を開始すると、元の棋譜が消えるのでなく、棋譜の分岐ができる。分岐を消すには、消したい手の先頭まで再生して、サブメニューの「ここまでの棋譜の最終手以降を消去」のボタンを押す。

入力した棋譜は、ソフトキーで終了すると、スクラッチパッドに保存される。終話キーで終了すると、保存されない。スクラッチパッドに保存された棋譜は、次回の起動時に自動的に読み込まれる。
また、入力した棋譜は、このサーバーのWebページにアップロードすることもできる。アップロードされた棋譜は、
http://ynomura.dip.jp/tmp/uploaded_kifus.html
で見ることができる。このページから棋譜をコピー&ペーストして、柿木将棋やMacの桜花で読み込めることを確認済である。
なお、棋譜をアップロードするには、このアプリの「ソフト設定」の通信設定を「する」にしてから起動する必要がある。また、このページにアップロードされた棋譜は誰でも閲覧可能だし、古いものは勝手に消えていく。


参考リンク
棋譜の表記方法:日本将棋連盟

続きを読む "10キーで棋譜入力するiモードアプリ" »

About 2015年08月

2015年08月にブログ「Weblog on mebius.tokaichiba.jp」に投稿されたすべてのエントリーです。過去のものから新しいものへ順番に並んでいます。

前のアーカイブは2015年07月です。

次のアーカイブは2015年12月です。

他にも多くのエントリーがあります。メインページアーカイブページも見てください。

Powered by
Movable Type 3.35