因数分解を行うプログラムについて

質問

こんにちは。

今日は教えてほしいことがあってきました。
学校の課題で

a,b,cは整数で、しかもaは0でないものとして、
このとき２次式
　　　ax^2 + bx + c
を、整数係数の範囲で因数分解するプログラムを作る

ことになったのですが、

１.任意のa,b,cの値を入れてもらう。

２.二次方程式の解で
　 整数係数の範囲で因数分解できるか判別する。

３.なにかを用いて分解する。

４.結果を表示する。
　　(dX + e)(fX + g)のような形で。

とまでは考えられるのですが、
３.の所が難しくて、考えてからかなり時間がたってしまい
らちがあかない感じです。
たすきがけを使うにしても、いまいち、よくわかりません。

どなたか、教えてください。お願いします。

回答No.5

noname#30727 · ベストアンサー

No.3 ですが、計算部分を省略せずに書きます。

x = (-b ± √(b^2 - 4ac)) / 2a
この式をこれ変形させる必要はありません。

実際に、3x^2 + 14x + 8 を順に計算してみます。
a = 3
b = 14
c = 8
このa, b, cの値を代入するわけだから、

x = (-14 ± √(14^2 - 4×3×8)) / 2×3
x = (-14 ± √100) / 6
ここで、±を２つに分けて、
x = (-14 + 10) / 6, x = (-14 - 10) / 6
x = -4 / 6, x = -24 / 6
x = -2/3, x = -4

プログラムとして考えていくと、√(b^2 - 4ac) から考えて、
int q = (b * b - 4 * a * c); // q = 100
int r = sqrt(q); // r = 10
if (r * r != q) { // sqrt の結果が整数でなければ解なし
return 解なし;
}

この後、割り算を計算せずに、分数として別の変数に持ちます。
int n1 = -b + r; // +の分子 (n1 = -4)
int m1 = 2 * a; // 分母 (m1 = 6)

この時点で、(6x + 4) と表示させる事もできますが、なんらかの方法で n1/m1 を約分することで、(3x + 2) と表示させる事は難しくないと思います。

同様に、
int n2 = -b - r; // -の分子 (n2 = -24)
int m2 = 2 * a; // 分母 (m2 = 6)
これも、-24/6 を -4/1 に約分することで (x + 4) と表示できるでしょう。

ここで符号について考えてみると、(3x + 2)(x + 4) の符号を全て反転させて、(-3x - 2)(-x - 4) としたとしても全く同じですが、あえて２つ表示する必要はないのではないかと思います。

お礼

返事が遅くなりすみません。
参考にさせていただきました。
ありがとうございました。
今度もこのようなことがあったときは
よろしくお願いします。

回答No.9

jmh

No.7 の
　　for (d = 0; d <= D; ++d) /* Dの平方根を探す */
　　　　if (d * d == D) break;
　　if (d * d != D) {
の３行を、
　　for (d = 0; d * d < D; ++d) /* Dの平方根を探す */
　　　　;
　　if (d * d != D) {
に変更させてください。
ここで sqrt() を使わないのは、単に「整数の問題は整数だけで解きたい」という気持ちからです。

お礼

返事が遅くなりすみません。
参考にさせていただきました。
ありがとうございました。
今度もこのようなことがあったときは
よろしくお願いします。

回答No.8

noname#148473

＃４＆＃６です。

とりあえず、先の回答（＃６）に載せたマクロの使用方法だけ書いておきます。
Excelさえあれば、簡単に使えますので試してみてください。

１．セルB2,E2,G2にそれぞれ ax^2+bx+c の a,b,cを入力しておきます。

２．Excelのメニューバーの「ツール」－「マクロ」－「VisualBasicEditor」をクリック

３．VisualBasicEditorが表示されますので、「挿入」－「標準モジュール」を選びます

４．右側の白紙のウィンドウ（コードウィンドウ）に、＃６の点線内を貼り付けてください。

５．Excelに戻って、「ツール」－「マクロ」－「マクロ」をクリック、「因数分解」を選んで「実行」してください。

お礼

返事が遅くなりすみません。
参考にさせていただきました。
ありがとうございました。
今度もこのようなことがあったときは
よろしくお願いします。

回答No.7

jmh

テキトーなこと言って、1724 さんを困らせてしまってようです。ごめんなさい。jmh は反省しました。そして作ってみました。

#include<stdio.h>

/* 符号 */
int sgn(int n) { return n >= 0 ? n != 0 ? 1: 0: -1; }
/* 絶対値 */
int abs(int n) { return n < 0 ? -n: n; }
/* 最大公約数 */
int gcd(int n, int m) { return m == 0 ? n: gcd(m, n % m); }

int main(void) {
　　int a = 3; /* a = 0 だと壊れます */
　　int b = 14;
　　int c = 8;
　　int D = b * b - 4 * a * c; /* 判別式 */
　　int d;
　　for (d = 0; d <= D; ++d) /* Dの平方根を探す */
　　　　if (d * d == D) break;
　　if (d * d != D) {
　　　　printf("irreducible\n"); /* 既約だ */
　　} else {
　　　　int alph_bunbo = abs(2 * a); /* 分母は＞０ */
　　　　int alph_bunshi = (-b - d) * sgn(a); /* 符号は分子に */
　　　　int beta_bunbo = abs(2 * a);
　　　　int beta_bunshi = (-b + d) * sgn(a);
　　　　{ /* 約分 */
　　　　　　int g;
　　　　　　g = gcd(abs(alph_bunshi), alph_bunbo);
　　　　　　alph_bunbo /= g;
　　　　　　alph_bunshi /= g;
　　　　　　g = gcd(abs(beta_bunshi), beta_bunbo);
　　　　　　beta_bunbo /= g;
　　　　　　beta_bunshi /= g;
　　　　}
　　　　printf ("%d(%dx - (%d))(%dx - (%d))\n",
　　　　　　　　a / alph_bunbo / beta_bunbo, /* 割り切れるはず */
　　　　　　　　alph_bunbo, alph_bunshi,
　　　　　　　　beta_bunbo, beta_bunshi);
　　}
　　return 0;
}

回答No.6

noname#148473

＃４です。
ちょっと長いですが、全部貼り付けます。

－－－－－－－－－－－－－－－－－－－－－－－－－－
Sub 因数分解()
　　Dim prm(2 To 65535) As Boolean
　　Dim a, b, c, d, e, f, g, h As Double
　　Dim x1, x2 As Double
　　Dim i, j, k As Integer
　　Dim es, fs, gs, hs As String

　　'シートから数値を取り込み
　　a = Range("B2")
　　b = Range("E2")
　　c = Range("G2")
　　d = a
　　e = 1
　　g = 1

　　'虚数解になる場合
　　If (b ^ 2 - 4 * a * c) < 0 Then
　　　　MsgBox "因数分解できません"
　　　　Exit Sub
　　End If

　　'解の公式
　　x1 = (-b + Sqr(b ^ 2 - 4 * a * c)) / (2 * a)
　　x2 = (-b - Sqr(b ^ 2 - 4 * a * c)) / (2 * a)
　　f = x1
　　h = x2

　　'ａの約数を調べる
　　i = 2
　　Do
　　　　prm(i) = False
　　　　If (a Mod i) = 0 Then
　　　　　　prm(i) = True
　　　　End If
　　　　i = i + 1
　　Loop While i <= 65535 Or i <= a

　　'解１（x1）にａの約数を掛けて、整数になるか調べる
　　If x1 - Int(x1) <> 0 Then
　　　　For i = 2 To a
　　　　　　If prm(i) = True And Abs((x1 * i) - Int(x1 * i)) = 0 Then
　　　　　　　　d = d / i
　　　　　　　　e = e * i
　　　　　　　　f = f * i
　　　　　　　　i = a
　　　　　　End If
　　　　Next
　　End If

　　g = g * d
　　h = h * d

　　'表示用に符号を調整
　　es = StyleEdit1((e))
　　gs = StyleEdit1((g))

　　fs = StyleEdit2((f))
　　hs = StyleEdit2((h))

　　Range("b6") = StrConv("'=(" & es & "x" & fs & ")(" & gs & "x" & hs & ")", vbWide)

End Sub
Function StyleEdit1(NumberArg As Double) As String
　　If NumberArg = 1 Then
　　　　StyleEdit1 = ""
　　Else
　　　　If NumberArg = -1 Then
　　　　　　StyleEdit1 = "-"
　　　　Else
　　　　　　StyleEdit1 = NumberArg
　　　　End If
　　End If
End Function
Function StyleEdit2(NumberArg As Double) As String
　　If NumberArg > 0 Then
　　　　StyleEdit2 = "-" & NumberArg
　　Else
　　　　If NumberArg < 0 Then
　　　　　　StyleEdit2 = "+" & -NumberArg
　　　　Else
　　　　　　StyleEdit2 = ""
　　　　End If
　　End If
End Function
－－－－－－－－－－－－－－－－－－－－－－－－－－

セルB2,E2,G2にそれぞれa,b,cを入力しておきます。
セルB6に結果が表示されます。

Ｃ言語は既に忘れてしまいましたので、Basicです。ごめんなさい。
Gotoなどは使ってませんので、比較的見やすい・・・かな？
いくつか実際に数値を入れて試して見ましたが、問題無いようです（自信なし）

ただ、inthefloiさんの方法と比べると、きっと数学的に美しくないですね。
文系なんで、つい力技に頼ってしまいます。

補足

inthefloiさん、fuji2002さんありがとうございます。

＞fuji2002さん
自分はＣ言語すら、今一理解してなくて…
その上、basicは全然分からないので、どう読んでいいか…
どれがＣ言語の何と対応するのか、分からないです。

回答No.4

noname#148473

面白そうな話なので、私も色々考えてみたのですが、
inthefloiさんが言われるように、

＞-0.6666667 などから、整数係数となる (3x + 2) = 0 を導きだす

の部分が最も難しいですね。特に

6x^2-x-2=0
　　↓
(3x-2)(2x+1)=0

のように、x^2の係数6が、3と2に分かれるような場合。
6を素因数分解して、それをαとβに掛けて、整数になるかどうかチェックする・・・
というような手順を踏むことになるでしょうか。
BASICなどの繰り返し処理が可能な言語なら、何とかできそうですが、
Excel関数程度では無理そうですね。

今日はお休みですし、これからVBAで上記の事を試してみます。

回答No.3

noname#30727

jmh さんの、二次方程式の解の公式で解くというのは面白そうですね。

例えば、3x^2 + 14x + 8 は、(3x + 2)(x + 4) ですが、そのまま計算すると、
x = (-b ± √(b^2 - 4ac)) / 2a より
x = -2/3, x = -4
となって、(x + 2/3)(x + 4) が得られることになります。
-0.6666667 などから、整数係数となる (3x + 2) = 0 を導きだすのは困難ですが、
√(b^2 - 4ac) が整数の時に、分数の通分だけで求まるので、計算時間的には相当有利になりそうです。

補足

皆さん、回答本当にありがとうございます。
昨日考えた結果二次方程式の解の公式を利用する方法で解くことに決めました。

そして、考えた（変形した？）のですが、
D=(double)(b*b-4*a*c)として、
(1/4*a*a)((2*a*ｘ)+ｓｑｒｔ(Ｄ))((2*a*ｘ)-ｓｑｒｔ(Ｄ))と導いたのですが、inthefloiさんが例で出された3x^2 + 14x + 8 の場合、
導いた式に各値を代入すると、
1/36（6ｘ+10)（6ｘ-10）となり、(3x + 2)(x + 4) になりません。

今の自分の考え方だと、因数分解するには程遠いのでしょうか？
皆さん、教えて下さい。お願いします。

回答No.2

jmh

> ３.なにかを用いて分解する。

２次方程式の解の公式を用いたらどうですか？
ａｘ^２ ＋ ｂｘ ＋ ｃ = ０ の解が α と β なら
ａｘ^２ ＋ ｂｘ ＋ ｃ = ａ(ｘ － α)(ｘ － β) と
（複素数の範囲で）因数分解できます。
α と β が有理なら、
ａｘ^２ ＋ ｂｘ ＋ ｃ = ｒ(ｐｘ － ｐα)(ｑｘ － ｑβ) と
できるんでは、ないでしょうか？

お礼

返事が遅くなりすみません。
参考にさせていただきました。
ありがとうございました。
今度もこのようなことがあったときは
よろしくお願いします。

回答No.1

100Gold

いわゆる貪欲なアルゴリズムを使用することにして、可能性がある物を総当たりで調べてゆかれては如何でしょうか。
ネストしたforループで順番にループして
a=df
b=dg+ef
c=e+g
の全てを満たす場合を正解にすれば良いと思います。

お礼

返事が遅くなりすみません。
参考にさせていただきました。
ありがとうございました。
今度もこのようなことがあったときは
よろしくお願いします。