迅雷2017笔试题-成都
}
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_v4(set, len, bpHistory, i_set+1, value);
}
right = bpHistory[i_set+1][value];
}
return left + right;
}
int divide_set_v5( int set[], int len, Bin &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 )
int tmp;
if ( !bpHistory.Find( i_set+1, value-set[i_set], tmp ) )
{
tmp = divide_set_v5(set, len, bpHistory, i_set+1, value-set[i_set]);
bpHistory.Insert( i_set+1, value-set[i_set], tmp );
}
left = tmp;
}
if ( value >=0 )
{
// 如果divide_set_v3(set, len, bpHistory, i_set+1, value) 还未计算过
//if ( bpHistory[i_set+1][value] == -1 )
int tmp;
if ( !bpHistory.Find( i_set+1, value, tmp ) )
{
tmp = divide_set_v5(set, len, bpHistory, i_set+1, value);
bpHistory.Insert( i_set+1, value, tmp );
}
right = tmp;
}
return left + right;
}
void cal_num( int n )
{
int* set = new int[n];
int* label = new int[n];
// initialize set and label
www.qz26.com
int sum_value = 0;
for ( int i=0; i<n; ++i )
{
set[i] = i+1;
sum_value += set[i];
}
memset( label, 0, n*sizeof(int) );
// 保证元素总和为偶数
if( sum_value%2 == 0 )
divide_set( set, label, n, 0, sum_value/2 );
delete[] set;
delete[] label;
}
int cal_num_v2( 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 )
rst = divide_set_v2( set, n, 0, sum_value/2 );
delete[] set;
return rst;
}
int cal_num_v3( 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;
// 动态申请二维数组
www.qz26.com
int rows = n+1;
int cols = half_value+1;
int** bpHistory = malloc2d<int>(rows, cols, -1);
bpHistory[0][half_value] = rst = divide_set_v3( set, n, bpHistory, 0, half_value );
//int cnt=0;
//for ( int i=0; i<rows; ++i )