迅雷2017笔试题-成都

 delete[] set;
 delete[] label;
}

// 使用了BP算法、递推算法的结果

//头文件
// 计算集合set的所有满足下列条件的子集合：子集合元素之和等于value
// 子集合的元素对应的label置1,并输出划分的集合
void divide_set( int set[], int label[], int len, int i_set, int value );

// 仅计算满足要求的集合的划分数，不输出具体的划分方式
int divide_set_v2( int set[], int len, int i_set, int value );

int divide_set_v3( int set[], int len, int** bpHistory, int i_set, int value );

int divide_set_v4( int set[], int len, std::vector< std::vector<int> > &bpHistory, int i_set, int value );

class Bin;
int divide_set_v5( int set[], int len, Bin &bpHistory, int i_set, int value );

// 对集合{1,2,...n}划分 - 输出划分的具体形式
void cal_num( int n );

// 仅计算划分数
int cal_num_v2( int n );

// BP算法 仅计算划分数 原始二维数组记录BP数据
int cal_num_v3( int n );

// BP算法 仅计算划分数 vector二维数组记录BP数据
int cal_num_v4( int n );

// BP算法 仅计算划分数 用桶记录BP数据
int cal_num_v5( int n );

// 递推法 仅计算划分数 （比我的BP算法速度快10倍）
long getSetsNum1(int n);

void test_cal_num();

//CPP文件

int divide_set_v2( int set[], int len, int i_set, int value )
{
 if ( 0 == value )
  return 1;

 if ( i_set >= len || value <0) www.qz26.com
  return 0;

 int rst = divide_set_v2(set, len, i_set+1, value-set[i_set]) + divide_set_v2(set, len, i_set+1, value);
 //cout<<"( "<<i_set<<" "<<value<<" )"<<rst<<endl;
 return rst;
}

int divide_set_v3( int set[], int len, int** bpHistory, int i_set, int value )
{
 if ( 0 == value )
  return 1;

 if ( i_set >= len || value <0)
  return 0;

 int left = 0;
 int right = 0;
 if ( (value-set[i_set]) >=0 )
 {
  // 如果divide_set_v3(set, len, bpHistory, i_set+1, value-set[i_set]) 还未计算过
  if ( bpHistory[i_set+1][value-set[i_set]] == -1 )
  {
   bpHistory[i_set+1][value-set[i_set]] = divide_set_v3(set, len, bpHistory, i_set+1, value-set[i_set]);
  }
  left = bpHistory[i_set+1][value-set[i_set]];

 }

 if ( value >=0 )
 {
  // 如果divide_set_v3(set, len, bpHistory, i_set+1, value) 还未计算过
  if ( bpHistory[i_set+1][value] == -1  )
  {
   bpHistory[i_set+1][value] = divide_set_v3(set, len, bpHistory, i_set+1, value);
  }
  right = bpHistory[i_set+1][value];
 }

 return left + right;

}

int divide_set_v4( int set[], int len, std::vector< std::vector<int> > &bpHistory, int i_set, int value )
{
 if ( 0 == value )
  return 1;

 if ( i_set >= len || value <0)
  return 0;

 
 int left = 0;
 int right = 0;
 if ( (value-set[i_set]) >=0 )
 {
  // 如果divide_set_v3(set, len, bpHistory, i_set+1, value-set[i_set]) 还未计算过
  if ( bpHistory[i_set+1][value-set[i_set]] == -1 ) www.qz26.com
  {
   bpHistory[i_set+1][value-set[i_set]] = divide_set_v4(set, len, bpHistory, i_set+1, value-set[i_set]);

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