0<x<1,N>0 に対し |x-q/p| が最小になる 0<p<N を求めよ

0<x<1,N>0 に対し　|x-q/p| が最小になる　0<p<N を求めよ。なお、p,q,N は整数です。

例えば、
x =√3/2, N=256 の場合の p、
x=π-3, N=1024 の場合の p
などを求めるアルゴリズムでもOKです。

No.1 ベストアンサー 回答者： cage64 回答日時： 2021/07/05 19:33

要するに、分母の最大数を指定して、実数の最良近似分数を求める問題ですね。

連分数近似とその中間近似の中から探せばよかったはずですので検索してください。

今検索したら、
https://www.ma.noda.tus.ac.jp/u/ha/SS2006/Data/H …
で詳しく説明してありました。
ここの記号を使えば、p[k]/q[k] や (m*p[k+1]+p[k])/(m*q[k+1]+q[k]) (m=1,2,..,c[k+2]) が候補です。

一応例の場合の計算を書いておくと（手計算なのでまちがってるかも）以下のようになります。

√3/2 の連分数展開は
[1,6,2,6,2,6,...]　で対応する近似分数は
1 6/7 13/15 84/97 181/209 1170/1351 ... です。
181/209と1170/1351 の間の中間近似分数で一番分母が小さいのは 209+97>256 だから中間近似は該当なしで、181/209 が求めるもの。

π-3 の連分数展開は
[7,15,1,292,...] で、対応する近似分数は
1/7 15/106 16/113 4687/33102 ...　です。
16/113 と 4487/33102 の間には (15+k*16)/(106+k*113) (k=1,2,.,291) があり、分母が1024未満で一番大きいのは1010だから、143/1010が一番いい中間近似。
これと16/113 を比べると 16/113 の方が近いのでこれが求めるもの(292と8では差がありすぎるので勝負にならないのは人間なら最初から分かります）。

なお、Nが1000程度であれば、今の計算機なら全数検査(分母pを2からN-1 まで動かしてq/pを求める)しても十分実用的だと思います。

この回答へのお礼

ありがとうございます。

連分数近似とその中間近似の中から探せばよいのですね
助かります。

お礼日時：2021/07/06 17:49