Best Rational Approximation( 法里数列)

亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述Best Rational Approximation( 法里数列)相关的知识，希望能为你提供帮助。
Best Rational Approximation 时间限制: 3 Sec 内存限制: 128 MB
提交: 297 解决: 25
[提交][状态][讨论版][命题人:admin] 题目描述 Many microcontrollers have no floating point unit but do have a (reasonably) fast integer divide unit. In these cases it may pay to use rational values to approximate floating point constants. For instance,
355/113 = 3.1415929203539823008849557522124
is a quite good approximation to
π = 3.14159265358979323846
A best rational approximation, p/q, to a real number, x, with denominator at most M is a rational number, p/q (in lowest terms), with q < = M such that, for any integers, a and b with b < = M, and a and b relatively prime, p/q is at least as close to x as a/b:
|x – p/q|≤ |x – a/b|
Write a program to compute the best rational approximation to a real number, x, with denominator at most M. 输入 The first line of input contains a single integer P, (1≤ P≤ 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of a single line of input. It contains the data set number, K, followed by the maximum denominator value, M (15≤ M≤ 100000), followed by a floating-point value, x, (0≤ x < 1). 输出 For each data set there is a single line of output. The single output line consists of the data set number, K, followed by a single space followed by the numerator, p, of the best rational approximation to x, followed by a forward slash (/) followed by the denominator, q, of the best rational approximation to x. 样例输入

3 1 100000 .141592653589793238 2 255 .141592653589793238 3 15 .141592653589793238

样例输出

1 14093/99532 2 16/113 3 1/7

提示来源Greater New York Regional Contest 2017

c++ code:

#include < bits/stdc++.h> using namespace std; int main() { int p,t,m; double x; scanf("%d",& t); while(t--) { scanf("%d%d%lf",& p,& m,& x); inta=0,b=1,c=1,d=1,e,f; while(true) { e=a+c; f=b+d; int gcd=__gcd(e,f); e/=gcd; f/=gcd; if(f> m) break; if(1.0*e/f< =x) { a=e; b=f; } else { c=e; d=f; } } printf("%d ",p); if(fabs(1.0*a/b-x)> fabs(1.0*c/d-x)) printf("%d/%d\n",c,d); else printf("%d/%d\n",a,b); } return 0; }

【Best Rational Approximation( 法里数列)】