二次式の因数分解

数値の因数分解の解答がわかったので、二次式の因数分解にチャレンジしてみた。ターゲットになる2次式は、

x ^ 2 + (a + b) x + ab

で、二次の項の計数が1になるものにした。もちろん二次方程式の解の公式を使えば一瞬でとけるが、中学の時のように公式を使わない方法で解けないか考えてみた。

この形の数式を因数分解する場合は、最初に、定数項を二つの因数に分解することから始める。定数項 ab を二つの因数に分解する可能な組み合わせを取り出す関数はどのようなものになるかと考えた。

普通に考えつくのは定数項を素因数分解して、その因数の組み合わせでできる数を全て列挙することだ。たとえば定数項が 6 の場合 6 を素因数分解すると、1 も含めて 6 = 1*2*3 だから、(1,6), (2,3), (3,2), (6,1) というような因数に分解できる。

ところがこの方式だと、素因数の組み合わせを全て考えなければならない、12 = 1*2*2*3 のような場合は、片方の因数を考えるのに、素因数をひとつだけ含む場合、素因数2個の組み合わせ、素因数3個の組み合わせなどを全て考えなければならないので大変な操作になる。プログラム化するにしても、素因数分解する関数、素因数の組み合わせを抽出する関数など複雑になりすぎる。

しばらく考えていたら、n という整数を二つの因数に分解する方法なら、1から初めて2,3、.. と順番に割っていって割り切れたときの数とその数による n の商とのペアを作ればよいことに気がついた。これなら簡単にできる。ちょっと実験してみた。

Hugs> [(n, 6 `div` n)| n <- [1..6], 6 `mod` n == 0]
[(1,6),(2,3),(3,2),(6,1)]

定数項が負の場合を含めて、定数項を2つの因数に分解する関数 splitNum は次のようになる。

splitNum :: Int -> [(Int,Int)]
splitNum n = [(m, n `div` m)| m <- [1..(abs n)], n `mod` m == 0]

試してみた。

Main> splitNum (-6)
[(1,-6),(2,-3),(3,-2),(6,-1)]

定数項が負の場合でもうまくいくようだ。あとは、こうして得られた二つの因数が a + b と一致するかどうかを検出して選び出すだけなので Haskell の得意分野だ。因数分解したときの結果をペアで返す関数 factor を次のソースリストのように記述した。整数では因数分解できない場合も考えて、戻値は Maybe 型にした。splitNum も因数の両方が負数の場合も考えて拡張した。

import List

splitNum :: Int -> [(Int,Int)]
splitNum n = [(m, n `div` m)| m <- (delete 0 [(-(abs n))..(abs n)]), n `mod` m == 0]

factor :: Int -> Int-> Maybe (Int,Int)
factor m n = if factor' == [] then Nothing else Just (factor' !! 0)
  where
    factor' = [(i, j)| (i, j) <- splitNum n, (i + j) == m]

試してみた。

Main> factor 1 (-6)
Just (3,-2)
Main> factor 1 1
Nothing

大成功!!

このプログラムを作っていて気づいたのは、定数項を素因数分解してからその因数の組み合わせで定数項を分解するというやり方は、分かりづらいのではないかということだ。例えば 6 を因数に分解するときは次のように、1から6までの数字を並べて、そのうちの6の因数に丸をつけ、その下にもう片方の因数を書くほうが初めて学ぶ人間にも分かりやすいのではないだろうか。

1 2 3 4 5 6
6 3 2 * * 1

これなら、因数分解や組み合わせを全て列挙するという知識がなくても、簡単に定数項を二つの因数に分解できる。Haskell のプログラムを作成することによって、逆に人間の思考のありかたの新しい面を発見できるのが面白い。


今日の Haskell
Haskell では負の数は必ずカッコで括らなければならない。
Main> 1 + (-2)
-1
[PR]
by tnomura9 | 2010-11-23 09:27 | Haskell | Comments(0)
<< Ruby でパターンプログラミング 素因数分解 >>