はじめに
42の課題で、2次方程式を解くプログラムをRustで作成したため、その備忘録として書いています。
作成した手順や、どこに工夫したかなどを重点的に書いているため、課題全体の解説というわけではない点についてはご了承ください。
作成したものはこちらにあります。
また42の他の活動についてはこちらにありますので、42自体に興味がある方はぜひこちらもどうぞ。
ちなみに前回解いた課題の記事はこちらになります。
作ったもの
ということで、まずは作ったものについてです。
できること
以下のように、1変数の代数方程式を与えると、その次数と、2次以下であれば解を教えてくれるプログラムを作成しました。
> ./computor "5 * X^0 + 4 * X^1 - 9.3 * X^2 = 1 * X^0"
Reduced form: 4 * X^0 + 4 * X^1 - 9.3 * X^2 = 0
Polynomial degree: 2
Discriminant is strictly positive, the two solutions are:
-0.47513146390886934
0.9052389907905898
これは整理すると2次方程式になるため、その解を出力してくれます。
ちなみに、こんな風に少し簡略化した書き方に対応したり
> ./computor "1 + 2X + X^2 = 0"
Reduced form: 1 * X^0 + 2 * X^1 + 1 * X^2 = 0
Polynomial degree: 2
Discriminant is zero, the solution is:
-1
うまく計算できた場合には分数で表示してくれたり
> ./computor "-3 + X + 2X^2 = 0"
Reduced form: - 3 * X^0 + 1 * X^1 + 2 * X^2 = 0
Polynomial degree: 2
Discriminant is strictly positive, the two solutions are:
1
-3 / 2
また複素数解にも対応しています。
> ./computor "1 + 4X + 5X^2 = 0"
Reduced form: 1 * X^0 + 4 * X^1 + 5 * X^2 = 0
Polynomial degree: 2
Discriminant is strictly negative, the two complex solutions are:
-0.4 ± 0.2i
ちなみに、1次以下にも対応しています。
> ./computor "1 + 4X = 0"
Reduced form: 1 * X^0 + 4 * X^1 = 0
Polynomial degree: 1
The solution is:
-1 / 4
実装
次にどのように作ったかについてですが、Rust言語を使い、数学系のライブラリはほとんど使わずに（四則演算くらい）作りました。
例えば二次方程式を解くうえで平方根の計算があったり、既約分数にするために最大公約数を求める必要がありますが、そのあたりもつくる必要がありました。
詳細は最初にあげたgithubのリンクを見ていただくのがいいかと思います。
作成した手順
続いてどのように課題を解いていったかについてまとめます。
だいたい時系列順で書いています。
課題の理解
課題は英語で与えられるため、まずは翻訳しつつ、自分の作るものの仕様をまとめていきます。
これくらいの内容で、しかも一人で行っているので、きちんとした仕様書や、シーケンス図みたいなものは作りませんが、あとで困らないようにちゃんと必要事項はまとめておきます。（といいつつ今回は失敗した。詳細は後ほど）
文字の読み取り
続いてプログラムが受け取った文字を構造体に入れて扱いやすくするところを作成しました。
今回の課題はそんなに重くなかったため、だいたい入力から出力まで順々に作成していった感じになります。
文字列のまま扱わなかったのは、マジックナンバーのままにしないとか、まぁ色々と理由があったりします。
また、ここでは変な文字が入ってきたときに「変な文字がきたで！」とはじくような役割も持たせています。
> ./computor "X ~ 0"
Unsupported characters: ~
ちなみに構造体……というか正確にはenumですが、以下のようになっています。
pub enum Elem {
X,
Plus,
Minus,
Prod,
Power,
Equal,
NumInt(i64),
NumFloat(f64),
}
これをこんな感じでVecにしまって、このフェーズはおしまいです。
> ./computor "5 * X^0 + 4 * X^1 - 9.3 * X^2 = 1 * X^0"
Ok([NumInt(5), Prod, X, Power, NumInt(0), Plus, NumInt(4), Prod, X, Power, NumInt(1), Minus, NumFloat(9.3), Prod, X, Power, NumInt(2), Equal, NumInt(1), Prod, X, Power, NumInt(0)])
※ ここから先も、もっと効率の良いやり方はあると思いますが、完成させることが大事という精神も大事だなと言い訳をしながら、そしてそれをこうやってアウトプットすることもまぁ大事かなと思いながら、筆を進めていますので、どうかお手柔らかに
項にまとめる
続いて、項ごとにまとめて、その情報を項用の構造体に入れる、ということをやっていきます。
項は例えば「- 9.3 * X^2」で一つの項です。
ここのフェーズでは、変な文字の順番になっていたときに、はじくような役割もあります。
./computor "1 + X + 2X^+ = 0"
Incorrect syntax
また、項の情報は、今回の２次方程式を解くだけなら、係数と次数だけで十分なので、その二つの情報を持つ構造体を用意しました。
pub struct Term {
pub coefficient: Coefficient,
pub degree: i64,
}
ここで、Coefficientは以下のようになっています。
pub enum Coefficient {
NumInt(i64),
NumFloat(f64),
}
係数を小数点つきで渡されていたらNumFloatに、そうでなければNumIntにしています。
これのおかげで、より精度を気にしたい場合には少数を使わないで計算する、みたいなことができたり、また分数表示のときに役に立ったりしています。（そして自分で課題の難易度を上げることにも役立てられました）。
項をまとめる
今回は以下のように整理されていない形式でも受け取れるようにしたため、それを左辺にまとめることを行いました。
before
> ./computor "5 * X^0 + 4 * X^1 - 9.3 * X^2 = 1 * X^0"
after
Reduced form: 4 * X^0 + 4 * X^1 - 9.3 * X^2 = 0
このとき、計算する２つの項の係数がどちらもintであればそのままintで、少なくともどちらかがfloatであればfloatになるように計算を行っています。
（一応計算誤差を少なくする工夫です）
解を求める
そしていよいよ解を求める部分です。
次数が少ない方から対応していきました。
この過程で、以下のような分数の計算ができる構造体を作ったりしました。
pub struct Fraction {
top: i64,
bottom: i64,
}
例えば「ax + b = 0 (a ≠ 0)」を解くと「x = -b / a」ですが、この分数の形のまま……そしてそれを既約分数にして表示することをこの構造体にやらせています。
また２次方程式の場合は判別式を事前に計算し、解の個数や複素数解なのかどうかなどを事前に求めたうえで、それぞれの処理として解を求めるようにしました。
数学系の関数の自作
最後に、今まで使っていた数学系の関数を自作のものに変える作業をしました。
最初に行っていた課題の理解が甘かったせいで、この段階で数学系の関数が禁止だったことに気づいたためです。（でも課題提出前に気づけてよかった）
大きなものとしては平方根を求めるものと最大公約数を求めるものですが、この２つについては以下を参考にしました。（アルゴリズムは知っていたのですが、間違えるのと考えるのが嫌だったので参考にしたというのはここだけの話）
おわりに
大学で数学をやっていたのもあって、今回のような解を求めたり、文字列を数式に変換するみたいなことには少し興味があったので、楽しかったです。