1. 题目分析

问题描述

我们需要为股市上涨/下跌股票比例生成一系列逐步精确的有理数近似值序列。给定上涨股票数$a$和下跌股票数$b$，要求：

1. 生成序列$a_1, a_2, ..., a_n$，其中：

   • $a_1$是分母为1的最佳近似
   • 每个后续$a_{i+1}$是分母更大但更精确的近似
   • 最终$a_n$为最简分数$\frac{a}{b}$

2. 近似标准：选择使$|\frac{p}{q} - \frac{a}{b}|$最小的分数$\frac{p}{q}$

输入输出

• 输入：多组$a\ b$（$a,b \leq 5000$）
• 输出：每组对应的近似序列，每行一个分数，组间空行分隔

2. 解题思路

关键步骤

1.计算真实比例：$\frac{a}{b}$（需约分） 2.生成近似序列：

• 初始化当前最佳误差$\delta_{min} = \infty$
• 对每个分母$q$从1到$b$：
  • 计算最佳分子$p = \lfloor q \times \frac{a}{b} + 0.5 \rfloor$
  • 计算新误差$\delta = |\frac{p}{q} - \frac{a}{b}|$
  • 如果$\delta < \delta_{min}$：
    • 记录$\frac{p}{q}$
    • 更新$\delta_{min} = \delta$

数学表达

• 最佳分子计算：$$p = \arg\min_p \left| \frac{p}{q} - \frac{a}{b} \right| $$
• 误差比较：$$\delta_{new} < \delta_{current} \Rightarrow \text{记录新分数} $$

3. 复杂度分析

• 时间复杂度：$O(b)$（对每个$q \in [1,b]$计算）
• 空间复杂度：$O(1)$（只需存储当前最佳）

4. 代码实现

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<ctype.h>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<string>
#include<map>
#include<stack>
using namespace std; 


int gcd(int big,int small)
{
	if (big<small)
		swap(big,small);
	if (big%small==0)
		return small;
	return gcd(small,big%small);
}

int  get(long double a,long double b,int k,long double div)
{
	int  i,j;
	long double c=a/b;
	i=1;
	j=(int)(a/b)+10;
	j*=a;

	while (i<j)
	{
		
		int m=i+(j-i)/2;
		if (fabs((long double)m/(long double)k-c)<div)
			return m;
		else if (fabs((long double)j/(long double)k - c)<fabs((long double)i/(long double)k-c))
			i=m+1;
		else
			j=m-1;
	}
	//cout<<i<<endl;
	return i;
}

int main()
{
	int i,j,k;

	int a,b;
	//cout<<377.0/227.0-749.0/451.0<<' '<<93.0/56.0-749.0/451.0<<endl;
	long double c;
	while (cin>>a>>b)
	{
		int g=gcd(a,b);
		a/=g;
		b/=g;
		long double fa=a;
		long double fb=b;
		long double div=1.0;
		c=fa/fb;
		//cout<<c<<endl;
		long double aa,bb;
			
		div=100000000;
		for (i=1;i<(int)c+10;i++)
		{
			if (div>=fabs((double)i-c))
			{
				div=fabs((double)i-c);
				j=i;
			}
		}
		printf("%d/1\n",j);  //第一个单独判断最好，不然后面混合在一起容易混。

		for (i=2;i<b;i++)
		{	
			j=get(fa,fb,i,div);
			aa=j;
			bb=i;
			
	
			if (div>fabs((aa)/(bb)-c))
			{//cout<<aa/bb<<' '<<div<<endl;
				div=fabs((aa)/(bb)-c);
				printf("%d/%d\n",j,i);
				//cout<<div<<' '<<fabs(aa/bb-c)<<endl;
			}
		
		}
		//if (n>1)
		printf("%d/%d\n\n",a,b);
	}

	return 0;
}