分数逼近

实现

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-15;
int m,n;
int l1=0,l2=1,r1=1,r2=0,m1,m2;
double r;
int sgn(double x)
{
	return (x>eps)-(x<-eps);
}
double f(int x,int y)
{
	return (y!=0?x*1.0/y:1e18);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>m>>n>>r;
	while(l1+r1<=m&&l2+r2<=n)
	{
		m1=l1+r1;
		m2=l2+r2;
		int tmp=sgn(r-f(m1,m2));
		if(tmp==1)
		{
			l1=m1;
			l2=m2;
		}
		else if(tmp==-1)
		{
			r1=m1;
			r2=m2;
		}
		else
		{
			cout<<m1<<'/'<<m2<<'\n';
			return 0;
		}
	}
	int tmp=sgn((r-f(l1,l2))-(f(r1,r2)-r));
	if(tmp==1)
	{
		cout<<r1<<'/'<<r2<<'\n';
	}
	else if(tmp==-1)
	{
		cout<<l1<<'/'<<l2<<'\n';
	}
	else
	{
		cout<<"TOO MANY"<<'\n';
	}
	return 0;
}

例题

洛谷 P1298 最接近的分数

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-15;
int m,n;
int l1=0,l2=1,r1=1,r2=0,m1,m2;
double r;
int sgn(double x)
{
	return (x>eps)-(x<-eps);
}
double f(int x,int y)
{
	return (y!=0?x*1.0/y:1e18);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>m>>n>>r;
	while(l1+r1<=m&&l2+r2<=n)
	{
		m1=l1+r1;
		m2=l2+r2;
		int tmp=sgn(r-f(m1,m2));
		if(tmp==1)
		{
			l1=m1;
			l2=m2;
		}
		else if(tmp==-1)
		{
			r1=m1;
			r2=m2;
		}
		else
		{
			cout<<m1<<'/'<<m2<<'\n';
			return 0;
		}
	}
	int tmp=sgn((r-f(l1,l2))-(f(r1,r2)-r));
	if(tmp==1)
	{
		cout<<r1<<'/'<<r2<<'\n';
	}
	else if(tmp==-1)
	{
		cout<<l1<<'/'<<l2<<'\n';
	}
	else
	{
		cout<<"TOO MANY"<<'\n';
	}
	return 0;
}