P1035 调和级数

两种解法如下：

1.模拟

这种做法的思路是枚举n从1开始，直到Sn>k结束，只需要一个循环即可实现。

代码：

 #include<cstdio>

 int main() {

     int k,n=;

     scanf("%d",&k);

     for(double Sn=;Sn<=k;++n,Sn+=1.0/n);

     printf("%d",n);

     return ;

 }

空间复杂度O(1)

时间复杂度 O(e^k−γ)（求法见做法2）

（如果那个γ可以约去的话，应该是O(e^k)，但并不知道可不可以约去）

代码：

 #include<cstdio>

 #include<cmath>

 const double gamma=0.5772156649;

 int main() {

     int k,n;

     scanf("%d",&k);

     n=exp(k-gamma)+0.5;

     printf("%d",n);

     return ;

 }

空间复杂度O(1)

（因为不知道math.h头文件中的exp函数的时间复杂度，所以不知道时间复杂度）

巴特西

P1035 调和级数

最新文章

热门文章