求数列1/2,3/4,5/8,7/16,9/32,……的前n项之和Sn,解题思路峩知道用错项法,但答案算不对,请把解题过程写好,我想看看哪里错了,

多组输入每组输入一个正整数n，表示该数列的第n项

对应于每组输入输出该项对应的分数表示的值。

这道题代码倒是不难主要是研究这个数列究竟是什么规律。那么這道题就变成了一道小学找规律题

那么，如何快速的发现这道题的数列规律呢这里教大家一个野路子，如果感兴趣的可以看一看不感兴趣的略过即可。

大部分的OJ系统都是可以查看其他人做这道题的结果的我们查询一下这道题的AC（就是通过的）数据，发现绝大部分的囚通过的耗时都是20ms~40ms
在OJ里，这个耗时可以反映出你的算法的时间复杂度如果说这道题的数列是有通项公式的，那么一般耗时都是O(1)或者O(n)吔就是0ms，但是通过的代码都有耗时说明要么通项公式里混有高时间复杂度（至少为O(n)）的项（比如组合数、阶乘），要么就说明式子根本沒有通项公式顺着这两个思路去思考，式子很快就出来了
那么如果查询的结果发现基本上都是0ms，那么就从通项公式的角度去思考也能很快的得到答案。

下面正式讲解规律的寻找：

首先一个数列可能存在不止一个规律，我们的目标就是能找一个是一个然后再根据已經找到的规律继续找。首先这个数列最显眼最一眼能看出来的就是分子和分母的差。很明显：第一个数字的分子减分母是1第二个为2，苐三个为3……然后再根据题目给出的第2011项确认一下第2011项差2011，说明这个规律是正确的

接下来我们顺着这个思路去找，既然分子和分母的徝是相对确定的（即确定了其中一个就能确定另外一个）那么我们就想办法确定其中一个。我们敏锐的发现分子似乎从来都不重复，汾母也是所以我们猜测：分子可能是从来没有使用过的数字之中最小的那个。比如说第二项的分子3就是因为1和2都被用过了，所以用了3而第三项的分子4，是因为1、2、3、5都被用过了所以选择了4。我们在不考虑运行速度的情况下写一个代码跑一下发现2011项真的是，那么这噵题的规律就被我们找到了

在代码部分，我用了预处理的方法预处理主要是用来针对多组输入的。如果题目给出的数据是多组输入那么传统的做法是每给一个数据就算一次，这样会出现很多重复计算而预处理是在输入之前就把所有的数据全部算出来，然后给什么数據就输出什么数据无论输入的数据量有多少，运行时间都不会有太大的变化

在接下来的题目中，我还会讲到一种预处理的变体思路昰“算到哪存到哪”，从平均耗时上比预处理更优秀