Question

一道c++编程题目 我的程序超时了 请高手帮忙修改一下谢谢

这是我的程序
#include <iostream>

using namespace std;
double q(int n){
int a,c;
double i,b;
for(a=1,b=0;a<=n;a++){
b=b+1.0/a;
}
i=1.0/b;
return i;
}

int main()
{
int a,b,c,d,e;
double sum;
cin>>a>>b;
for(c=1,sum=0;sum<=a;c++){
sum=sum+q(c);
}
for(d=1,sum=0;sum<=b;d++){
sum=sum+q(d);
}

if(c==d-1)cout<<c<<endl;
else cout<<c-1<<" "<<d-2<<endl;

return 0;
}

结果是超时的了 时间特别长 大概要等一秒多彩能出来结果 这是为什么啊 为什么这么慢 请个位高手帮忙修改一下 谢谢了！！！

Answer 1

你的程序重复计算了很多，可以优化一下：

#include <iostream>
using namespace std;
 
int main()
{
	int a, b;
	cin >> a >> b;
 
	int n = 0;
	double s = 0, sum = 0;
	while(sum <= a){
		s += 1.0/++n;
		sum += 1.0/s;
	}
	int L = n;
 
	while(sum < b){
		s += 1.0/++n;
		sum += 1.0/s;
	}
	int H = n-1;
	
	if(H == L)
		cout << H << endl;
	else
		cout << L << " " << H << endl;
	return 0;
}

Answer 2

#include<iostream>
void main()
{ double a,b,s,k;
int n1,n2;
cin>>a>>b;
s=1; n1=1; k=1;
while ( s<=a ) { n1++; k+=1.0/n1; s+=1/k; }
n2=n1;
while ( s<b ) { n2++; k+=1.0/n2; s+=1/k; }
n2--;
if ( n1!=n2 ) cout<<n1<<' '<<n2<<endl;
else cout<<n1<<endl;
}
分子可以用累加的办法计算，算完a<s后接着算s<b，不用都从头算

Answer 3

1、速度问题。
以例子为例，计算左边大于2010的时候，q()做b值累加计算了（1+18611）*18611/2=173193966次；计算右边小于2011的时候，q()做b值累加计算了（1+18622）*18622/2=173398753次。都上亿次运算了，速度肯定不会快的。
2、算法问题。
貌似没有好的办法吧？涉及到调和级数这个东东，估计不好弄。有一个近似的算法，一来公式不好记，二来考计算机又不是考数学，所以你这样写应该就行了。

追问

可是 这是题目啊