摊还分析

        在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价，从而说明一个操作的平均代价是很低的，即使序列中某一单一操作的代价很高，不涉及改了，但可以保证最坏情况下每个操作的平均时间。

摊还分析中主要的三种方法：1、聚合分析  2、核算法（即记账法） 3、势能法

1、聚合分析：证明对所有的n，一个n个操作的序列最坏情况下花费的总时间为T(n),因此，在最坏情况下，每个操作的平均代价，或称为摊还代价为T(n)/n，这点不同于以下两种方法，以下两种方法，不同的操作有不同的代价。

2、核算法：对不同的操作赋予不同的费用，赋予某些操作的费用可能多于其实际代价，这个费用称为他的摊还代价，当一个操作的摊还代价超出其实际代价时，将差额存进数组结构中的特定对象，存入的差额称为信用，对于后续操中摊还代价小于实际代价的情况，信用可以用来支付差额，因此，可将一个操作的摊还代价分解为其实际代价和信用。不同的操作可能有不同的瘫痪代价。如果用ci表示第i个操作的真实代价，用^ci代表其摊还代价，则对任意n个操作序列，要求:

                    

数据结构中存储的信用恰好等于总摊还代价与总实际代价的差额。数据结构所关联的信用必须一直为非负值。

3、势能法：并不将预付代价表示为数据结构中特定对象的信用，而是表示为“势能”，或"势"，将势能释放用来支付未来操作的代价，势能与整个数据机构而不是特定对象相关联。

势函数Φ将每个数据结构Di映射到一个实数Φ（Di），次值即为关联到数据结构Di的势。对一个初始数据结构D0执行n个操作。对每个i = 1, 2, ,.....,n，令ci为第i个操作的实际代价，令Di为在数据结构Di-1上执行第i个操作得到的结果数据结构。第i个操作的摊还代价^ci用势函数Φ定义为：

^ci  = ci + Φ(Di) - Φ（Di-1） 

每个操作的摊还代价等于其实际代价加上次操作引起的势能变化。n个操作的总的平摊代价为：

定义一个Φ势函数，使得Φ（Dn）>= Φ(D0), 则总的平摊代价就是总的实际代价的一个上界。对所有的i，有Φ（Di）>= Φ(D0)，可以保证预先支付，Φ(D0)一般为0

如果第i个操作的势差Φ(Di) - Φ（Di-1） > 0 则平摊代价^ci表示对第i个操作多收了非，同时数据结构的势也增加了，如果< 0，则表示平摊代价的不足收费，可以通过减少势来支付该操作的实际代价。不同的势函数，可能产生不同的平摊代价。但他们都是实际代价的上届。


下面给一个是势能法摊还分析的例子：
题目：针对一个k位二进制计数器问题，我们用一个位数组A[0..k-1]作为计数器，计数器采用小端表示法。为了准确分析该计数器的计数效率，我们采取“势能法”摊还分析。定义计数器在进行某次递增（加1）操作后的势为该次操作后计数器中1的个数。例如，k=2,A=[0 0]时，执行一次递增操作，A变为A‘=[0 1]，这次操作的势是A’中1的个数，即为1。本问题要求你求出从某个给定的计数器状态（即计数器的初始值I）之后连续N个递增操作的摊还代价。

输入：
多组测试数据。
每组测试数据共两行：
第一行两个正整数，分别为二进制计数器的位数K和初始时计数器的值I(0
第二行一个正整数，为题目要求你求出的递增操作的个数N（0

输出：
每组测试数据输出N行，第i行输出初始状态后第i个操作的摊还代价（1<=i<=N）。

样例输入：
3 0
2

样例输出：
2 
2

分析： 摊还代价=ci+F(Di)-F(Di-1),其中F(Di)是当前的势，F(Di-1)是之前的势。势能法定义势为i次操作后计数器中1的个数。代价ci是ti或ti+1，
因为除了复位ti位，还至多置位1位。

代码：
#include
#include
#include
using namespace std;
int a[50]= {0};
int k,l;
int increment()
{
    int i=0;
    int c=0;//c是递增1次的代价ci。
    while(i     {
        a[i]=0;
        c++;//也就是相当于有多少个数字进行了改变
        i++;
    }
    if(i     {
        a[i]=1;
        c++;
    }
    return c;
}
int main()
{
    while(cin>>k>>l)
    {
        memset(a,0,sizeof(a));
        int i=0;
//初始计数器是l，因此需要把计数器初始化为l的2进制表示。
        while(l)
        {
            a[i]=l%2;
            l/=2;
            i++;
        }
        int n;
        cin>>n;
        int pre=0,d=0;
        for(int j=0; j             if(a[j]) pre++;//pre是上一步的势?(Di-1)
        for(int i=1; i<=n; i++)
        {
            int c=increment();
            d=0;
            for(int j=0; j                 if(a[j]) d++;// d是这一步的势?(Di)
            cout<             pre=d;//pre更新
        }
    }
}