ガロア理論2
方程式を解くというのは、歴史的に見れば解の公式を求めることと同義であった。ここではそもそも解の公式とは一体何なのか、反省してみる。
解の公式とは何か
方程式が決まれば、その解が定まる。「方程式が決まる」ということをもう少し詳しく説明すれば、それは係数が決まることである。n次方程式にはn+1個の係数があるが、定数倍は方程式の解を変えないので、n次の係数を1と仮定して一般性を失わないから、結局n次方程式はn個の係数を決めれば決定されると言える。
最初に書いたように、我々は解そのものに興味があるのではない。からどうやって解が定まるのか、ということに興味がある。この過程fに注目し、それを「代数的に」表現をしたものが解の公式である。「代数的に」というのは、「足す・引く・掛ける・割る・ルートを取る」という5種類の操作だけを許すという意味である。
わざわざ「代数的に」と付けたのは、本来から解が決定される過程が、別に代数的に表現する必要性が無いからである。(例えば三角関数を取るという操作を含めてもいいはずだ。)つまり我々は「代数的に」と言って、自らに制限を課していることになる。
似たような状況に、作図がある。ある図形が作図できるか、というのは暗に「定規とコンパスのみを用いて」という制限が課されている。例えば角の三等分を作図せよという問題は、分度器を使えば容易いのであって、「定規とコンパスのみを用いて」という制限が加わって初めて難問足り得る。*1
制限というのはマイナスイメージを伴って用いられることが多いが、制限をすることがクリエイティビティを生み出すということもある。例えばサッカーを見てみると良い。手を使わないで足だけでボールを扱え、という制限を課しているが、それによって華麗な足技を我々は鑑賞することが出来る。
ガロア理論でも同じことだ。過程fを代数的に表現せよと、問題を解く手法を制限したから、このような豊かな理論が生まれたのである。
解の公式を求めてみる
まず手始めに、思いっきり簡単なところからスタートしてみよう。
1次方程式
の解の公式を求めてみる。
等式の性質を利用すればこれをxについて解くのは難しくない:
これは与えられた方程式の解xを係数だけを用いて明示的に与えている。そしてさらに代数的な手段のみを用いて、xを求める過程を表現している。よってこれは確かに1次方程式の解の公式である。
次に、2次方程式
の解の公式を求めてみる。
1次方程式の場合のように、等式の性質を素朴に利用したのでは、2次方程式は解くことができない。なぜならxが2つの項に分離して存在しているからである。この分離の問題を解消するためには、平方完成と呼ばれるテクニックを用いる必要がある。
以下、計算式を簡略化するため、方程式の最高次の係数は1としよう。
平方完成とは要するに、
という2次式を
と変形することである。
ここでで新しい変数yを定義すれば、上の式はyを用いて
と書ける。
平方完成を単に式変形のテクニックとして説明するのも良いが、このように変数変換によってより解きやすい式に書き換えるという見方の方が分かりやすい。
つまり変数変換を行うことで、xの2次式
を、新しい変数yによる2次式
に書き換えることが、平方完成だというわけだ。2つに分離していた変数が一つの項にまとまったのが分かる。こうして分離の問題を克服できたことに注意する。
変数変換によって問題を単純化するということは広く行われることであり、例えば微分方程式を解く時にも用いられる。物理学で座標を問題の状況にあったものに取り替えるというのも、結局は変数変換で微分方程式を解きやすいものに書き換えているだけなのだ。
平方完成というテクニックも、こう見ると、変数変換というテクニックの一つの方法に過ぎないことが分かる。
一旦平方完成をしてしまえば、
を変形して
となる。
この先へ進む前に、ここで一度虚数iの復習をしておく。
虚数の復習
最も基本的な事実からスタートする。それは「どんな実数も2乗すると0以上となる」というものだ。従って「2乗して負になる数」は実数には存在しない。
そこで数の概念を拡張して「2乗して負になる数」も我々の数のカタログに含めることにしよう。それはそれで良いのだが、何かその数を表現する記号を新しく用意しなければならない。なぜなら実数だけ扱ってきた我々は、そのような数を表す記号を持ち合わせていないからである。
実は、「2乗して負になる数」より前にも、我々は新しい数が出てくる度に、新しい記号を導入して、その新しい数をなんとか表現してきた。自然数1,2,3...を拡張して、新しく「負の数」を導入した時、それを表すためにマイナスという記号を導入した。また、何もないことを表す数を導入した時、0という記号を導入した。こうして整数...,-3, -2, -1, 0, 1, 2, 3,...を書き表せる。次に0と1の間の数、つまり少数を導入した時、0.5あるいは1/2という分数の記法を導入した。こうして我々は有理数を書き表せる。次に無理数を導入した時、我々はルート記号を導入した。ただしここで今までと事情が変わって、ルート記号を導入しただけでは、全ての無理数を書き表すことは出来ない。これは無理数の定め方に問題がある。無理数とは「有理数以外の全ての実数」と定義される。有理数以外なら何でもいいのだから、無理数は単一の記号法で書き表すにはあまりにヴァラエティに富みすぎているのだ。
さて、兎に角も「2乗して2になる数」なら、これをと書き表せるようになった。「2乗して負になる数」についても、同じようなことをしようというのである。負の数のなかで、最も基本的な数は-1であろうから、これを基準として、「2乗して-1になる数」をiと書き表すことにする。ただし、ここで一つ注意して置かなければいけないことがある。それはiも-iも2乗すると-1になるということである。つまり単に「2乗して-1になる数」と言っても、数が一つに定まらないのである。同じことはルート記号の場合にもあって、単に「2乗して2になる数」といっても定まらない。そこでは「2乗して2になる数」の中でも、正のものを表すという約束をする。
しかし残念ながら、虚数に正とか負とかいう概念は適応できない。このことは簡単に見ることが出来る:もし仮に虚数に正負の概念が適応出来たとすると「2乗して-1になる数」のうち、正のものをiとおける。もちろん
である。しかし両辺を2乗すると
となって矛盾を生ずる。したがって虚数に正負の概念は無い。
どちらをiと書き表すか、明確な基準がないから、ここに大きな選択の自由が生まれてしまう。「私のiは貴方の-iだった」ということが起こりうる。
しかし、これは問題とはならない。「2乗して-1になる数」のどちらをiと書き表すことにしても良いのである。なぜか? それは、iが「本当は」どちらの虚数を表しているのか誰にも分からないからである。
卑近な例を取ってみよう。今、瓜二つで全く、誰にも(親にでさえも!)区別出来ない双子がいたとしよう。双子の一方にA、もう一方にBと名付けたとしよう。いや……「名付けたとしよう」と言ったが、考えてみて欲しい、そもそも二人は区別できないのだから、どちらがAかは重要ではないのである。せいぜい言えるのは「Aでない方がB」(あるいはその逆「Bでない方がA」)ということだけである。つまり二人の関係は相対的なものでしかないのだ。もちろん、もし仮に双子を区別する方法があれば、話は別になる。この場合二人の関係は絶対的であり、どちらをAと名付けるのかはちゃんと意味がある。
別の言い方をすると、我々は虚数について語る時「どちらかをiとすれば、もう一方は-iとなる」という、2つの虚数についての相対的な関係性だけを知っていれば十分なのである。「2乗すると-1になる数」は2つあって、それをと表す……と言えばこれからの議論にとって十分であり「2つのうちどちらをiとしたか」という情報は一切必要ないのである。この情報の不必要性が、逆にiと-iの相対性を表しているとも言える。
さて、iと-iの相対性が明らかになったところで、次のステップに移ろう。
Aを正の数としたとき、「2乗して-Aになる数」はの2つである。ここでと定めて、ルート記号を負数に拡張する。ちなみに、こう約束するととなる。(でiを定義できないことに注意しよう。なぜなら虚数を定義する前は、負数に対するルート記号が定義されていないからである。)
取り敢えず一旦、この辺りで虚数の復習を終わろう。
2次方程式の解の公式
から
を得る。もちろんルート記号の中身が負でも問題ない。
こうして2次方程式を解くことが出来た。xの値が欲しければ変数変換が
であったことを思い出せばよくて、
を得る。これが2次方程式の解の公式である。
次に、3次方程式
の解の公式を求めてみよう。
(次回へ続く)
(番外編)虚数は発明か、発見か
「2乗して-1になる数」をi,-iと書き表すことにした。ここでふと気になるのは、「2乗して-1になる数」はiと-iだけか?ということである。数の世界はもっと広くて、実は「2乗して-1になる数」はもっとたくさんあることだって有り得るのではないだろうか?
こう考える時、その人は「数はそこに最初から在って、人間はそれを発見しているだけである」という立場に立っていると言える。しかし、本当にそうだろうか? 我々は実数を飛び越えた時点で、新しい数を創造してしまったのではないだろうか? (この立場に立つと、虚数の存在という問題に頭を悩ませる必要はなくなる。)
いや、そもそも実数の存在だって怪しい。
果たして数とは人間の知的活動とは別に存在するものなのか、それとも数は人間が作り出した道具に過ぎないのか......
この壮大な問題に回答を出すことは諦めて、次のもう少し実際的な事実を述べるに留めよう:
論理的に矛盾がなければ、それは数学の対象足り得る
例えば「2乗して-1になる数」にはi,jという2つが「独立に」あるとしよう。ここで「独立に」という意味はであるのはの時のみに限るということである。(もしそうでなければ、jは複素数に過ぎないことになり、新しい数を導入したことにならない。)
ここで問題になってくるのはiとjの積が何になるかである。これは少し計算すると分かることだが、を満たすような実数a,b,cは存在しない。つまり、jのような数をそれまでの数の体系と無矛盾に定義することは(少なくとも複素数の素朴な拡張としては)できない。
しかし、4元数の存在を見れば分かるように、工夫すれば「2乗して-1になる数」がi,j,kの3つある数体系を無矛盾に構築することが出来る。
複素数や4元数の存在に頭を悩ませない方法は、それらをチェスのルールのようなものだと思うことである。つまり複素数や4元数は人間が想像力豊かに生み出した架空の数であり、それらは一定のルールに従うことを要請されているものだと考えるのだ。複素数の計算をする時、単にルールに従って記号を操作しているに過ぎないと割り切ってしまえばよい。これならどんな突飛な概念が出てきたとしても許される。
ただしそれでも唯一要請されることがあって、それはルールそれ自体に矛盾が無いことである。あるいはそれまであったルールとの整合性がちゃんと取れていることである。逆に言えば、これさえ守られていれば、その新しい概念は数学的対象足り得るのだ。
しかし、例えば複素数は、それを「数学者の空想の産物」として除くにしては、あまりにも便利すぎることを心に留めておく必要はあるだろう......
*1:ちなみに、定規とコンパスだけを使って与えられた任意の角を三等分することは不可能であることが証明されている。
ガロア理論
ガロア理論は代数方程式についての理論だ。そこで、ガロア理論を学ぶ前に、まずそもそも代数方程式とは何か、方程式とは何かについて考えておくことは良い準備になるだろう。
そもそも論
代数方程式について考える前に、そもそも方程式とは何か考えてみよう。方程式と名のつくものをよく観察すると、方程式に共通するものが見えてくる:方程式とは何か分からないものがあって、それについてのヒントを表したものだ。
分からないものが数で、それについてのヒントが代数的に与えられたものが、つまり代数方程式
である。
分からないものが関数であり、それについてのヒントが微分で与えられていれば、それは微分方程式と呼ばれる。
ちなみに、もちろん分からないものが数であったとしても、
のように、ヒントが代数的に与えられていないものも、もちろん考えることができる。
このように様々な方程式が考えられるわけだが、そんな中でガロア理論は特に代数方程式を扱う。なので以下では方程式といえば代数方程式を指すことにする。
さあ方程式を解こう。でも、その前に
方程式があればそれを解きたくなるのが人の性である。
代数方程式は紀元前からその解き方が研究されてきた。ガロア理論はある意味で人類の長大な代数方程式論研究の集大成と言える。
また、微分方程式もその解法が盛んに研究されている。それは微分方程式がこの世界の基本法則を表現するものとしてよく使われるからである。例えば力学で言えば、物体の運動の様子が分からないもの(時間を変数とする未知関数)であり、それについてのヒントがニュートンの運動方程式と呼ばれる微分方程式で与えられる。
このように方程式は解くことが注目されがちであるが、実はその前に考えておくべきことがある。それはそもそもその方程式に解が存在するのか、ということである。例えば今適当に方程式を作ってみる:
この方程式を満たすような数が本当に存在するかどうかは、明らかなことではない。もっと複雑な方程式も考えることができるが、そのような複雑な条件を満たすような数はちゃんとあるのだろうか?
この疑問について決定的な回答を与えるのが、いわゆる代数学の基本定理である。要は「複素数まで探索の範囲を広げれば、どんな方程式にも解が存在する」ということだ。しかもただ存在するだけでなく、\(n\)次方程式には(重複度を含めて)\(n\)個の解があることまで保証されている。
方程式を解くとは一体どういうことか
方程式に解が存在することは保証されたので、安心して方程式を解こう。
方程式を解くというのは、その方程式を満たすような数を明らかにすることだ。そのための一つの方法として、コンピュータによる計算がある。実際、ニュートン法などの方程式を解くアルゴリズムが知られている。これによれば、任意の方程式を任意の精度で解くことができる。
しかしここである問題が生じる。方程式が与えられた時、それをコンピュータで解いたとしても、何か不満足を感じるのである。よくよく考えてみると、それはコンピュータで方程式の解を求めたところで、方程式についての本質的な理解が深まらないということから来ることに気がついた。もちろん、単に方程式の解が欲しいということもある。例えば先に挙げた微分方程式で言えば、微分方程式の解を兎に角出してしまえば、それが実際的に役に立つ。
そこで方程式を単に解くだけではなく、方程式について何か本質的な理解ができるような方法が欲しいのである。
Numeronアルゴリズムのpythonソースコード
ここで議論したNumeronアルゴリズム(戦術T2')をpythonで実装した。
一行一行注釈を付けていく。*1*2
main.py
# -*- coding: utf-8 -*- N = 3 #ゲームで扱う桁数 import functions P = [] f = [] c = [[]] a = [7,1,9] #setup functions.Generate_P(P) functions.Generate_P0(P) print 'possible = ', functions.Calc_P_size(P) print '' count = 0 while True: functions.Make_call(P, c) count += 1 print 'c = ', c[0] functions.Make_feedback(f, c[0], a) print 'feedback = ', f if f[1] == 3: print 'answer is ...', c[0] print 'try = ', count break else: functions.Generate_next(P,f) f = [] print 'possible = ', functions.Calc_P_size(P) print ''
functions.py
# -*- coding: utf-8 -*- N = 3 #推測値cと正解値aを比べてfeedback fを作成する def Make_feedback(f, c, a): f.append(c) f.append(Eat(c,a)) f.append(Bite(c,a)) #Pから推測値を抽出する #Pの最初の数を推測値とする #推測値はcに格納する def Make_call(P, c): for i in range(10 ** N): if P[2 * i] == True: c[0] = P[2 * i + 1] break else: pass def Generate_next(P, f): for i in range(10 ** N): if P[2 * i] == True: #signがTrueの場合のみ考えれば良い。Falseならそれ以上触れる必要がない。 P[2 * i] = Sign(P[2 * i + 1], f) if P[2 * i] == False: pass #P0を生成する def Generate_P0(P): for i in range(10 ** N): if Judge(P[2 * i + 1]) == True: pass if Judge(P[2 * i + 1]) == False: P[2 * i] = False #numがゲームルールに適合しているか判定する def Judge(num): for i in range(N): for j in range(N): if i != j and num[i] == num[j]: #桁は異なるのに数字は一致する=重複あり return False else: pass return True #Pを生成する def Generate_P(P): num = [] for i in range(10 ** N): P.append(True) Convert_int_to_num(num,i) P.append(num) num = [] #初期化 #integer intを各桁毎に分解してデータ型numへ変換する def Convert_int_to_num(num, int): for i in range(N): num.append(int % 10) int /= 10 num.reverse() #|P|を計算をする #|P|を返す def Calc_P_size(set_num): count = 0 for i in range(10 ** N): if set_num[2 * i] == True: count += 1 else: pass P_size = count return P_size #num gの feedback fに対するsign sを計算する #num gがfeedback fに適合していればTrue, 適合していなければFalseを返す def Sign(num_sbj, feedback): if Eat(num_sbj, feedback[0]) == feedback[1] and Bite(num_sbj, feedback[0]) == feedback[2]: s = True else: s = False return s #num gがnum cに対して返すeatを計算する #eatは桁数も数字も合っているものの数 def Eat(num_sbj, num_src): count = 0 #初期化 for i in range(N): if num_sbj[i] == num_src[i]: count += 1 else: pass eat = count return eat #num gがnum cに対して返すbiteを計算する #biteは数字はあっているが桁数が異なるものの数 def Bite(num_sbj, num_src): count = 0 for i in range(N): for j in range(N): if j != i and num_sbj[j] == num_src[i]: #桁数が一緒の時はたとえ数字が一致してもカウントしない count += 1 else: pass bite = count return bite
実行結果
possible = 720 c = [0, 1, 2] feedback = [[0, 1, 2], 1, 0] possible = 126 c = [0, 3, 4] feedback = [[0, 3, 4], 0, 0] possible = 40 c = [5, 1, 6] feedback = [[5, 1, 6], 1, 0] possible = 9 c = [5, 7, 2] feedback = [[5, 7, 2], 0, 1] possible = 4 c = [7, 1, 8] feedback = [[7, 1, 8], 2, 0] possible = 1 c = [7, 1, 9] feedback = [[7, 1, 9], 3, 0] answer is ... [7, 1, 9] try = 6
main.pyについての注釈
- ソースコードを意味の単位で記述したいので関数を多用する。
- メインのコードをmain.pyとし、関数定義を集めたものをfunctions.pyとする。
- オブジェクト指向プログラミング(OOP)は一切使っていない。そのため完全に意味の単位で記述できていない。
# -*- coding: utf-8 -*-
pythonが日本語と相性が悪いので、最初にこう書いておくと良いおまじない。これ無しだとコメントすら日本語で書けない。
N = 3
Nは桁数を表す。Numeronでは3桁の数を用いているが、別に4桁でも構わない。ソースコードは一般的にN桁の数当てゲームのアルゴリズムとなっている。4桁の数当てがやりたいならN=4とすればよい。
P = [] f = [] c = [[]]
ここでの記法に従う。ソースコードで数学のように簡潔な記号法を使う問題点はコードの視認性の低下である。コードの視認性を高めるためには、変数の名前を一目見て内容が分かるようなものにするのが望ましい。ただ今回はここの議論を前提とするので、あえて数学的な記号法を用いている。本来は、例えばPはPossible、fはfeedbackとか省略しない方が良いのかもしれない。
a = [7,1,9]
正解数を719と設定する。
正解数を設定し直す度にコードを書き直すのは面倒だし、コードを変更すること自体望ましくないように思える。
コンソールから正解数を取得するようなプログラムを書くことも出来るが、(面倒なので)やめておいた。このプログラムにUI等の完成度は求めない。
while True:
数を当てるまで推測をし続けるので、ループを設定する必要がある。
ループの回数は不明なのでwhileを使う。無限ループで、答えが見つかったらループを抜ける。
if f[1] == 3:
fの構造上、f[1]にはeat数が保管されている。
それが3であるということは、推測と答えが一致したことを意味する。
なのでここでbreakによりループを抜ける。
文章の書き方
解説しようとして変にアレンジせずに、自分が理解している通りに書く。着飾らずに、コアをそのまま書く。
オブジェクト指向プログラミングとは何か
プログラムとはそもそも何か。*1
プログラムとは、何らかの方法で保管されたデータを、何らかの方法で操作・加工することである。
a→b→c→...→x
入力したaというデータを加工していって、最終的にxというデータを得る。aからxを得るのがプログラムの目的である。*2
オブジェクト指向プログラミング(OOP)以前のプログラマは、二つの指揮を同時に行なっていた:
- データ加工i→jが具体的にどんなプロセスで行われるべきか
- aからxに到るまでのデータ加工の工程がどうあるべきか
厄介なのは1と2は相互作用していることだ。データ構造や加工の方法を変更すると、それが工程にも影響を与えるし、逆もまた然りである。
二つの変数があると問題は難しくなる。そこでよく採られる常套手段は、どちらか一方を固定するというものである。それがOOPのアイデアに他ならない。
OOP以後のプログラマは、二つの指揮を個別に行えばよくなった:
- オブジェクトの中身の設計
- オブジェクト間の情報の流れの制御
要はプログラムをオブジェクトの内と外に分けて、困難を分割したのである。このオブジェクトの内と外に分けるというのが、カプセル化という概念が表している意味である。
2の作業、つまりデータの流れ (stream) の制御を行なっているとき、プログラマは1について知る必要がない。知るべきなのは単にiというデータがjに加工されるという事実のみである。具体的にどうやってi→jが実現されるのかは(2の作業中は)どうでもよい。このことを指して、オブジェクトはブラックボックスなどと言われたりもする。つまりオブジェクトがブラックボックになって、中身が見えなくなってしまっても一向に構わないということだ。
オブジェクトがカプセル化され、中身が見えなくなったことによって、プログラマは2の作業に専念出来る。また、他人が作ったオブジェクトの中身をわざわざ理解しなくても、「iを入れたらjが出る」という情報(これをインターフェースと呼ぶ*3)が分かってさえいればそれが使える。こうしてプログラムの再利用も容易になる。
また逆に1の作業中は2を気にする必要はない。オブジェクトが持つべきインターフェース(=iを入れたらjが出る)さえ実現すれば、どんな設計をしても良い。*4*5
これらの利点はすべてコードをオブジェクトの内と外に分けるというカプセル化の概念から出てきた。したがって次が言える:
オブジェクト指向プログラミングの本質はカプセル化にある。*6
OOPは上で述べたようなものだが、そこではクラスベースとか継承や多様性といった概念は登場してこなかった。なぜならクラスベースや継承や多様性といった概念はOOPの本質ではないからである。それは単にOOPをより効率的に実現するためのテクニックでしかない。しかしそれはあまりに便利であるから、OOPを行うときには必ずといって良いほど紹介される。だが、何度も繰り返すがそれはOOPの本質ではない。
最後に
残念ながらOOPの本質を理解しても、OOPが出来るようになるわけではない。OOPを実際に行うためには、用いる言語でOOPを行うための仕様を理解し、それを覚えて使えるようにしなければならない。それにクラスベースや継承、多様性といった概念も身につける必要がある。そのためには練習 (practice)あるのみだ。ただ練習する上でOOPのアイデアを理解しておくのはとても有用であるのは間違いない。
*1:以下では特定の言語に依らない説明を心がける。言語を決めてしまうと、その言語仕様に気が取られたり、そもそもその言語を知らないといったことが足かせになってしまう。オブジェクト指向プログラミング (OOP) はプログラム記述方法のアイデアであり、その記述方法で具体的にプログラムを書くときにやっと言語が問題になってくる。OOPの本質的アイデア自体は特定の言語を設定しなくても語れるし、そうするべきだとも思う。
*2:もちろん実際のプログラムはこのような単純な一本道とは限らない。入力がたくさんあったり、道が分岐したり、ループしたりするだろう。ただ一本道としても議論の本質は失われない。
*3:元々インターフェースというのは外界とのやりとりを司る部分という意味である。別の言い方をすれば「上っ面」だ。OOPでは物事の上っ面だけみればよいから楽なのだ。
*4:もちろん効率の良い設計が望ましいだろうが。
*5:ただもちろんその肝心のインターフェースがどんなものか知るためには、2についての理解が必要にはなるだろう。しかしそれでも1が2に影響することはない。これが肝心であり、カプセル化の利点である。
戦術T2'の実装を通じて学んだこと
プログラミング初心者が学んだこと
1.プログラミングの心得
まずこの本のすごさを改めて実感した。
プログラムはこうして作られるプログラマの頭の中をのぞいてみよう
- 作者: 平山尚(株式会社セガ)
- 出版社/メーカー: 秀和システム
- 発売日: 2013/09/25
- メディア: 単行本
- この商品を含むブログ (5件) を見る
プログラムを作る上でのモノの見方を教えてくれる。個々の技術的アドバイスよりも、こういった考え方それ自身を教えてくれる本は貴重である。
- 手を付けられる部分から初める。あるいは、手を付けられるよう問題を変形して小さくする。
- 知識は必要になった時に学べば良い
2.名前の重要性
変数や関数に付ける名前は、非常に重要。一目見て分かるようになるべく情報量が多く、なおかつ簡潔な名前にするとよい。良い名前の付け方については
リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)
- 作者: Dustin Boswell,Trevor Foucher,須藤功平,角征典
- 出版社/メーカー: オライリージャパン
- 発売日: 2012/06/23
- メディア: 単行本(ソフトカバー)
- 購入: 68人 クリック: 1,802回
- この商品を含むブログ (137件) を見る
3.データ構造とオブジェクトの重要性
データ構造が決まるとアルゴリズムが自ずと定まるというのは、大きな発見だった。
戦術T2'の実装
前回からの続き。
戦術T2'の実装
ソースコードの良い構造とは
コードはなるべく意味の単位で分割されていることが望ましい。そのためには関数を適宜定義したりするのも良いが、最も効果的なのはオブジェクトを用いる方法である。今回はまずオブジェクトを用いないでプログラミングをして、そこから逆にオブジェクトの有用性を考察する。
データ構造
アルゴリズムを決定する上で、データ構造が重要となる。実際、データ構造を決定するとアルゴリズムは自ずと定まる場合が多い。逆に言うとデータ構造について十分な考察をしないまま始めて、後々データ構造を変更するということになると、アルゴリズムの大部分を書き換える必要が出て来る。なのでデータ構造は予め決めておきたいところだが、難しいのはある程度アルゴリズムが決まらないとデータ構造の良し悪しが判断できないという点である。実は、この点もオブジェクトを用いれば解決できる。
戦術T2'はciをPiの最小数として決定する。Piのデータ構造が決まっていれば、Piの最小数を探す方法=アルゴリズムは自ずと定まってくる。それではPiのデータ構造はどうやって定めるのが良いだろうか。そのためにはPiが他にどんな操作を加えられるのか見てみるのが良い。
PiはP(i-1)からフィードバックf(i-1)によって生成される。*1要はP(i-1)の中でf(i-1)に適合する数だけを集めたのがPiである。
こういう扱われ方をするPiのデータ構造には色々な方法があるだろうが、ここでは次のようにデータ構造setを定める:
[[sign], num, [sign], num, [sign], num, ..., [sign], num]
ただしここでsignはbool型でnumは配列である。
setがどのようにしてPiを表すのか説明する。i番目のnumは自然数iを各桁毎に格納した配列である。i番目のsignはi番目のnumがPiに含まれている場合はTrueで含まれない場合はFlaseである。
例
P1はsetによって次のように表現される:
[[False], [0,0,0], [False], [0,0,1], ..., [True], [0,1,2], ..., [False], [9,9,9]]
データ構造setが集合Piを表す最善のものと言うつもりは全く無い。ただ採用するデータ構造がいかにアルゴリズムに影響するかを見るためには丁度よい。
*1:数学ではこのような動的な記述は嫌われるかもしれない。ただ今は具体的な手順を考察する立場なので、このような動的な記述のほうが役に立つ。