分数相加的OJ问题,为什么总提示Time Limit Exceed.找不到问题所在

C++语言 码拜 4年前 (2016-09-20) 475次浏览
#include <iostream>
using namespace std;
int main()
{
int a[100],b[100],c[100],d[100],e[100],f[100];
int n;
cin>>n;
for (int i=0;i<n;i++)
{
cin>>a[i]>>b[i]>>c[i]>>d[i];
e[i]=a[i]*d[i]+b[i]*c[i];
f[i]=b[i]*d[i];
for (int j=f[i];j>=1;j–)
{
if (e[i]%j==0 && f[i]%j==0)
{
e[i]=e[i]/j;
f[i]=f[i]/j;
}
}
}
for (int i=0;i<n;i++)
{
cout<<e[i]<<” “<<f[i]<<endl;
}
}
比较简单的分数相加问题,在VS2010上已经运行通过了,并且答案正确,但是网上提交答案就是Time Limit Exceed
望高人指点!
解决方案

10

你这数大了就很慢了,数有多大就有多少次循环。
可以用辗转相除法

30

引用:
Quote: 引用:

你这数大了就很慢了,数有多大就有多少次循环。
可以用辗转相除法

就是先求出最大公约数?

#include<iostream>
using namespace std;
 
int find(int a, int b) //求最大公 约数 
{
	while(a != b)
	{
		if(a > b) a = a -b;
		else if(a < b) b = b -a;
	}

	return a;
}
int main()
{
	int n; cin >> n;
	int a, b, c, d;
	int e, f;
	int temp;
	for(int i = 0; i < n; i++)
	{
		cin >> a >> b >> c >> d;
		e = b * d;
		f = a * d + b * c;
		temp = find(e,f);
		e = e/temp;
		f = f/temp;
		cout << f << " " << e << endl;
	}
	return 0;
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明分数相加的OJ问题,为什么总提示Time Limit Exceed.找不到问题所在
喜欢 (0)
[1034331897@qq.com]
分享 (0)