迅雷2017笔试题-成都

  free2d( bpHistory, rows, cols );
 }

 delete[] set;

 return rst;
}

int cal_num_v4( int n )
{
 int rst = 0;

 int* set = new int[n];

 // initialize set
 int sum_value = 0;
 for ( int i=0; i<n; ++i )
 {
  set[i] = i+1;
  sum_value += set[i];
 }

 // 保证元素总和为偶数

 if( sum_value%2 == 0 )
 {
  int half_value = sum_value>>1;

  vector<vector<int>> bpHistory( n+1, vector<int>(half_value+1, -1) );

  bpHistory[0][half_value] = rst = divide_set_v4( set, n, bpHistory, 0, half_value );
 }

 delete[] set;

 return rst;
}

int cal_num_v5( int n )
{
 int rst = 0;

 int* set = new int[n];

 // initialize set
 int sum_value = 0;
 for ( int i=0; i<n; ++i )
 {
  set[i] = i+1;
  sum_value += set[i];
 }

 // 保证元素总和为偶数 www.qz26.com

 if( sum_value%2 == 0 )
 {
  int half_value = sum_value>>1;

  int rows = n+1;
  int cols = half_value + 1;
  Bin bin(rows, cols);

  rst = divide_set_v5( set, n, bin, 0, half_value );
 }

 delete[] set;

 return rst;
}

long getSetsNum1(int n)
{
 //check total sum
 long sum = 0;
 for (int i = 1; i <= n; ++i) sum += i;
 if ((sum & 1) == 1) return 0;

 sum >>= 1;

 //inital array
 long N = ((n * (n + 1)) >> 1) + 2;
 long* dp = new long[N];
 for (long i = 1; i < N; ++i) dp[i] = 0;

 //递推 BigO(N^3)
 dp[0] = 1;
 long max = 0;
 for (long i = 1; i <= n; ++i)
 {
  for (long j = max < sum ? max : sum; j >= 0; --j)
   dp[j + i] += dp[j];
  max += i;
 }
 
 //long rst = dp[sum];
 //delete[] dp;
 //return rst;
 return dp[sum] >> 1;
}

void test_cal_num()
{
 FPSController fps;

 int n=104;//99;//31;//99;//104;//24;//7;//23;

 //fps.BeginFrame(); www.qz26.com
 //cal_num(n);
 //cout<<g_iCnt<<endl;
 //cout<<"elapse time : "<<fps.GetElapseTime()<<"秒"<<endl;

 //cout<<endl;
 //fps.BeginFrame();
 //cout<<cal_num_v2(n)<<endl;
 //cout<<"elapse time : "<<fps.GetElapseTime()<<"秒"<<endl;

 cout<<endl;
 fps.BeginFrame();
 cout<<cal_num_v3(n)<<endl;
 cout<<"elapse time : "<<fps.GetElapseTime()<<"秒"<<endl;

 cout<<endl;
 fps.BeginFrame();
 cout<<cal_num_v4(n)<<endl;
 cout<<"elapse time : "<<fps.GetElapseTime()<<"秒"<<endl;

上一页  [1] [2] [3] [4] [5]  下一页