我无语了 - -5555555555555555555555555555555
为什么 可以用int - -

 

来晚了,5555,如下是我的代码，不过时间复杂度为O(N^2),效率比较低,但是还是帖出来:
#include <iostream>
#include <vector>
#include <time.h>
#include <math.h>
#include <algorithm>
using namespace std;
/*
整数分划可能不少人都做过了，把一个正整数拆分为若干个正整数的和，问有多少种不同的拆法。比如对正整数4，
4=1+1+1+1
4=2+1+1
4=2+2
4=3+1
4=4
共有5种。现在问，如果拆成2的幂的和，有多少种不同的拆法
比如对正整数4，
4=1+1+1+1
4=2+1+1
4=2+2
4=4
共有4种。
请给出对任意正整数n(0<n<2000000)，拆分为2的幂之和的拆分方法数。输出这个数字模1000000的值。

接口定义：

namespace ID // 你的名字
{
  int bp(int n); // 求解函数，测试过程可能多次调用
  void init(); // 初始化，测试开始时调用一次
  void release(); // 清理，测试结束时调用一次
}

注意，测试过程形如：

t1 = time();
ID::init();
for (i = 0; i < testCase; i++)
  ans[i] = ID::bp(data[i]);
ID::release();
t2 = time();
check(ans);

也就是说init,release的时间也算到统计时间内。
*/
namespace Skybtone // 你的名字
{
    vector<int> data;
    vector<int> ans;
    int bp(int n); // 求解函数，测试过程可能多次调用
    void init(); // 初始化，测试开始时调用一次
    void release(); // 清理，测试结束时调用一次
    inline    void Jiaozheng(int &sum)//数字模1000000的值
    {
        sum%=1000000;
    }
    int    getn(int n,int i)
    {
        int j,k;
        switch(i)
        {
        case 0: return 1;
        case 1: return n/2;
        default:
            {
                int t=n/pow(2,i),sum=0;
                for(k=1;k<=t;++k)
                {
                    for(j=0;j<i;++j)
                    {
                        sum+=(getn(n-k*pow(2,i),j)%1000000);
                    }
                }
                return sum;
            }
        }
    }
    
}

int main()
{
    using Skybtone::data;
    using Skybtone::ans;
    srand(time(NULL)); 
    int    testCase=1000;
    int    tmp=0;
    cout<<"数字\t:\t表示个数"<<endl;
    for(int    i=1;i<=testCase;++i)
    {
//        data.push_back(rand()%500);//2000000
        data.push_back(i);//2000000
        if(data[i-1]==EOF)return 0;
        cout<<data[i-1]<<"\t:\t";
        ans.push_back(Skybtone::bp(data[i-1]));
        cout<<ans[i-1]<<endl;
    }
    Skybtone::release();
    return 0;
}

int Skybtone::bp(int n)
{
    if(n<1)return EOF;
    using Skybtone::getn;
    using Skybtone::Jiaozheng;
    int i=0;
    while(pow(2,i)<n)++i;
    int sum=0;
    for(int j=0;j<=i;++j)
    {
        sum+=getn(n,j);
        Jiaozheng  (sum);
    }
    return sum;
}
void Skybtone::init()
{
}
void Skybtone::release()
{
    using Skybtone::data;
    using Skybtone::ans;
    data.clear();
    ans.clear();
}

好吧，我猪头了，循环应该从1开始……

太厉害了

这就奇怪了.后一种还有除法运算啊.
我想可能有这些原因:
1.下标的数据类型要是int类型,而第一种用了long,可能需要某种转换把它变成int类型的,但很多地方比如VC中,int和long是同样长度的.
2.f数组和t数组在内存中不同的地方,两者的速度不会相差太大,而且第二种有除法运算,足以抵消这个差别.把n/2改成n>>1就更好了.
3.最大的可能就是楼主所说的,但两个程序的相关如此小,如果在程序的相同地方开始调用,那么两者因为切换cache而产生效率问题的可能性是一样的.所以多测几次会出现一会这个快一会那么快的现象.
4.还有其它意想不到的情况.
5.外在原因:楼主的测试可能有点问题,这个可能性不大,但也是一种可能性.

好，好啊