1.模拟
这种做法的思路是枚举nn从1开始,直到Sn>kSn>k结束,只需要一个循环即可实现。
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int main() { double sn=0,k,t; int n; scanf("%lf", &k); for (n = 1; sn <k; n++) { t = (1.0) / n; sn =sn+t; } printf("%d", n); return 0; }
空间复杂度O(1)O(1)
时间复杂度O(e^{k-\gamma})O(ek−γ)(求法见做法2)
(如果那个\gammaγ可以约去的话,应该是O(e^k)O(ek),但并不知道可不可以约去)
2.数论(调和级数)
代码:
#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; }