P1035 级数求和 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • Loner_Knowledge
    修改:时间复杂度应为$O(e^{n-\gamma})$。(在这里$n$是问题规模,不是题目要求输出的正整数$n$)
  • 郭锴亿
    啊啊啊啊啊啊啊啊啊啊啊啊阿啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
  • Loner_Knowledge
    修改:数论做法的时间复杂度为exp函数的时间复杂度,所以数论做法的时间复杂度应为$T_{exp}(n-\gamma)$。
  • ronnie
    简洁
  • MRsoymilk
    在新手村就使出了小白看不懂的大招,杀鸡焉用牛刀?
  • Loner_Knowledge
    回复楼上:做法一只用了循环啊,难不成这还看不懂。
  • Loner_Knowledge
    回复楼上上:另外建议您去看看A+B的题解,那里才真正可怕。
  • PC_DOS
    貌似有说法exp函数是用泰勒展开的
  • Jr_极影兔
    gamma是极限意义应该是说gamma是无限的,不能拿一个有限的数来减,比如你可以试算一下4-π等于几
  • sylvia2018
    为什么不能用float呢?
作者: Loner_Knowledge 更新时间: 2017-12-14 09:35  在Ta的博客查看    134  

在算模拟做法(做法1)的时间复杂度时,我想到了一种新的数论做法(做法2),检查了一遍题解发现没有这种做法,于是我写了这篇题解。


1.模拟

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

代码:

#include<cstdio>
int main() {
    int k,n=0;
    scanf("%d",&k);
    for(double Sn=0;Sn<=k;++n,Sn+=1.0/n);
    printf("%d",n);
    return 0;
}

空间复杂度$O(1)$

时间复杂度$O(e^{k-\gamma})$(求法见做法2)

(如果那个$\gamma$可以约去的话,应该是$O(e^k)$,但并不知道可不可以约去)

2.数论(调和级数)

关于调和级数的姿势,点这里

已知$Sn=1+1/2+1/3+...+1/n=\sum_{k=1}^{n}\frac{1}{k}$。

明显地,$Sn$为第$n$个调和数。

欧拉推导过求调和级数有限多项和的表达式为$\sum_{k=1}^{n}\frac{1}{k}=\ln(n+1)+\gamma$,我们拿过来用即可。($\gamma$等于0.5772156649)

我们需要满足$Sn>k$,即满足$\ln(n+1)+\gamma>k$,化简得$n>e^{k-\gamma}-1$。

我们只需求满足上式的最小的$n$,所以$n=e^{k-\gamma}+0.5$(四舍五入),即模拟做法的时间复杂度为$O(e^{k-\gamma})$。

关于$\gamma$(欧拉-马歇罗尼常数)的姿势,点这里

代码:

#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 0;
}

空间复杂度$O(1)$

时间复杂度$O(???)$

(因为不知道math.h头文件中的exp函数的时间复杂度,所以不知道时间复杂度)

未解决的问题

1.时间复杂度$O(e^{k-\gamma})$中的$\gamma$可不可以约去?

2.math.h头文件中的exp函数的时间复杂度为多少?

3.有dalao说$\gamma$是极限意义下的,不能直接$k-\gamma$是什么意思?


最后,

欢迎各位留言吐槽

欢迎dalao答疑。

欢迎神犇纠错。

评论

  • 滑蒻稽
    好!
  • 滑蒻稽
    66666666666666
  • Forever_coding
    啊666。蒟蒻求问第12行为什么要用1.0呀?我用的1,结果超时了
  • 三颗奶糖
    回复上楼:因为精度不同,由于i变量是整形,用1除后结果是0
  • suziyun
    同问为什么要用1.0,不太懂数据结构,整形是什么意思,这里的i不是int吗?
  • lhaoyuan_renjie
    回复楼上:int就是整形,1除以整形当然还是一个整形,但是s是double型,当然就不对啦~~
  • DARKSTALKING
    int类型不会出现浮点数,而浮点数的计算过程中不能使用整形,否则会出错
  • 18949691400加油!
    666
  • 祝硕鹏
    long double行不行,一定要用double么
  • 渣渣呵呵
    还TLE呀!
作者: 狒狒dePascal 更新时间: 2017-01-16 19:37  在Ta的博客查看    36  

开始非常重要

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int k,i=0;
    double s=0.0000;//请注意精度
    cin>>k;
    do
    {
        i++;
        s=s+ (1.0/i);//请注意除法两边数据类型(不能使是int,不然等于div运算)
    } while (s<=k);
    printf("%d",i);
    return 0;
}

评论

  • XZRY520
    原来的做法用while循环会死吗? 非要用for循环那么多次??!!
  • 我很辣ji看头像
    楼上干嘛不直接for(;;)?? 要速度用双层vector调啊
  • OverWatch_huihui
    为什么要用double,不是整数吗???
  • lhaoyuan_renjie
    for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)for(;;)....
  • henry09
    最后一个程序中的for(double i=1;i<=1000000;++i)可以改写成while(1)
作者: 夜雨声烦hst 更新时间: 2017-12-15 20:52  在Ta的博客查看    13  

这道题我们可以用递归来做,避免时间的浪费,当递归找到那个数值之后,直接cout出来。#include<iostream>

#include<cstdio>
using namespace std;
double search(double,double);
double n,t=1;
double print(double);
int main()
{
    cin>>n;
    search(n,0);//搜索模块。
}
double search(double x,double sum)//下面就是调用的深搜模块。
{
        sum=sum+1/t;
        t++;
        if(sum>n) print(t);//调到输出的子程序
        else return search(x,sum);//深搜
    }
double print(double q)
{
    cout<<q-1;
    return 0;
}

下面是原来的做法

#include<iostream>
#include<cstdio>
using namespace std;
double sum=0;
int main()
{
    double n;
    cin>>n;
    for(double i=1;i<=1000000;++i)//要小心范围,小了是不可以的。
    {
        sum=sum+1/i;
        if(sum>=n)
        {
            cout<<i;
            return 0;
        }
    }
}

恩,各位大佬求别嘲笑! 珂朵莉太可爱啦!

评论

  • 郭锴亿
    6666666666666666666
  • yyyer
    wa
  • 杏花疏影里
    可以用while
  • 鲍雪冰
    666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
作者: 合451518 更新时间: 2016-12-03 10:13  在Ta的博客查看    13  

思路:不停算s,直到s>n.

注意:

1)s必须定义为小数类型

2)for i:=1 to 10000000 是因为当n=15 时算出来是1825421(剧透),所以循环i太小可能不出结果

3)算出i之后必须exit或break,否则循环一直运行...

var
 s:extended;
 n,i:longint;
begin
 read(n);
 s:=0.0;
 for i:=1 to 10000000 do begin
  s:=s+1/i;
  if s>n then begin write(i);exit;end;
 end;
end.

评论

  • 还没有评论
作者: 陳家慧子 更新时间: 2018-12-28 20:42  在Ta的博客查看    3  

不知道有没有用C的题解……反正我是看了三页都没有……

最暴力的方法,提供给和我一样的新手。

作为一个常年病假的数学专业学生,这题于我最大的难点是我要愿意写sn要用double,不然精度不够……

调和级数的方法我再研究。

#include<stdio.h>
int
main(){
    int k,n;
    double sn=0.0;
    scanf("%d",&k);
    for(n=1;;n++){
     sn+=1.0/n;
     if(sn>k*1.0)
      break;
    }
    printf("%d",n);
    return 0;
}