1+1/3+1/5+…+1/99=？

我不太清楚,但我尽量帮你提供资料
(一)分解法
问题二:求正整数N和M之间具有最多真因子的数.本题中的真因子是这
样定义的:如果R数1,我们认为1是1的真因子.
参数范围:1≤N时限:10s.
我们很容易得到下列两个方法:
顺序查找法.....:依次统计规定范围内的各整数的真因子个数,记录
最优解.
由于,分解质因数的算法时间复杂度为平方根级的,因此这个算法的时间
复杂度为O((m-n)*m0.5).
标号法...:枚举不同的因数,标记它们的倍数.
如果不仔细分析,会认为两种方法的算法时间复杂度一样,实际上后者的
时间复杂度是0((m-n)*(1+1/2+1/3…+1/[m0.5])),还不到O((m-n)*[log2m0.5])
{[x]表示[x,x+1)间的整数}.证明如下:
先用数学归纳法证明1+1/2+1/3+1/4+1/5+…+1/(2n-1)≤n.
当n=1时,左边=1,右边=n=1;1≤1,不等式成立.
假设当n=k时,不等式成立,则有
1+1/2+1/3+1/4+1/5+…+1/2k-1≤k
现证明n=k+1时,不等式依然成立,
∵ 1/2k+1/(2k+1)+1/(2k+2)+…+1/(2k+1-1)＜1/2k+1/2k+…+1/2k
=(2k+1-1-2k+1)/2k
=1
∴ 1+1/2+1/3+…+1/2k-1+1/2k+1/(2k+1)+…+1/(2k+1-1)≤k+1
即 1+1/2+1/3+1/4+1/5+…+1/2k+1-1≤k+1
故命题成立.
所以,1+1/2+1/3+1/4+1/5+…+1/n≤[log2n]
方法二之所以在时间复杂度上大有降低,是因为它采用了"空间换时间"
规模化问题的解题策略 长沙市一中●谢婧
的模式,由于在标号的全过程中必须保存当前各整数的真因子个数,因此空间
复杂度是0(m-n),从参数范围可知,实际情况下无法满足这一需求.它仅仅停
留在理论