题目192:最优近似值
本帖最后由 永恒的蓝色梦想 于 2020-8-31 10:54 编辑Best Approximations
Let x be a real number.
A best approximation to x for the denominator bound d is a rational number r/s in reduced form, with s ≤ d, such that any rational number which is closer to x than r/s has a denominator larger than d:
|p/q-x| < |r/s-x| -> q>d
For example, the best approximation to √13 for the denominator bound 20 is 18/5 and the best approximation to √13 for the denominator bound 30 is 101/28.
Find the sum of all denominators of the best approximations to √n for the denominator bound 1012, where n is not a perfect square and 1 < n ≤ 100000.
题目:
定义 x 为一个实数。
对应于分母界限 d,x 的最优近似值(另一题翻译成了最佳逼近)为 r/s,其中 s≤d,并且是最简形式。也就是说,任何一个比 r/s 更接近 x 的有理数,它的分母一定比 d 大:
|p/q-x| < |r/s-x| -> q>d
比如,如果界限为 20 的话,√13 的最优近似值是 18/5,而界限为 30 时,则是 101/28。
对于1 < n ≤ 100000,且 n 不是完全平方数,找出界限为 1012 时, √n 的最优近似值的分母之和。
本帖最后由 guosl 于 2020-5-19 12:04 编辑
首先题目的翻译有致命错误!题目要求的是n的平方根的最佳逼近。
应用√n的连分数展开中分母最靠近 10^12的那个渐近分数。
但对分母最靠近 10^12的那个渐近分数的分母到10^12之间的验证没有好办法。{:10_250:} guosl 发表于 2020-5-18 08:50
应用n的连分数展开中分母最靠近 10^12的那个渐近分数。
大佬NP{:10_245:}
页:
[1]