”部分分数分解(m/nのｍ,ｎは整数)のアルゴリズム化の方針を示せ。”

質問

”部分分数分解(m/nのｍ,ｎは整数)のアルゴリズム化の方針を示せ。”です。
内容は情報ではなく数学なので、ここで質問をさせていただきます。

m/n * x/x = mx/nx

mx/nx = (mx-n)/nx + n/nx = (mx-n)/nx + 1/x
ただし、mx-n>0, mx>n

∴mx/nx　=　m/nより

m/n = mx/nx = (mx-n)/nx + 1/x , ただし、mx>nとなるxを定める必要がある。
x={n(分母)/m(分子)の小数点以下切り捨て}+1であれば常にmx>nは満たされる。

あとは再帰的にm ← mx-n (次の分子をmx-nに更新), n ← nx (次の分母をnxに更新)
でループ処理をして最新の分子が1の時にブレイクすれば処理完了。

というプログラム化の方針でどうでしょうか？
プログラムの作成より、方向性を示せと言われる方が細部の説明において難しいですね…orz

回答No.2

nag0720 · ベストアンサー

＞ループに入る前に入力された数値のチェックを入れればOKでしょうか？

ループに入る前だけではなく、ループの中でもチェックする必要があります。

例えば、5/6の場合、
5/6 = (5*2-6)/6*2 + 1/2 = 4/12 + 1/2
4/12 = (4*4-12)/12*4 + 1/4 = 4/48 + 1/4
4/48 = (4*13-48)/48*13 + 1/13 = 4/624 + 1/13
これ以上やっても無限ループになります。

m/n = mx/nx = (mx-n)/nx + 1/x
としたあとで、(mx-n)/nxを約分して既約分数にする必要があります。

ただし、上記のチェックだけで本当に無限ループにならないかどうかの数学的な証明は必要です。

お礼

>>既約分数にする必要

頭から抜けていました、実際にコーディングしてテストした方がいいですね。

取りあえず、ループの継続条件をMOD(ｎ,m)<>0にして、
余りなく分子で分母を割り切れた時に終了させる方向で考えます。

ありがとう御座いました！

回答No.1

nag0720

方針としては大丈夫でしょうが、
無限ループになる可能性はありませんか？

補足

先ずは、書き込み、有難うございます。

”有理関数は必ず部分分数分解できる”っていう文章をどこかで見たので、
必ずいつかは最新の分子が1になると思ったのですが…

よく考えると、最初のmとnの入力の際に
変な数値を入力されれば無限ループですね…orz

ループに入る前に入力された数値のチェックを入れればOKでしょうか？