题目转自:
二笔只有三道题，分值分别为30, 30, 40，题分别如下：1、实现strtol函数，其原型如为int strtol(const char *num_str, char **endptr, int base)，num_str存放待转换的字符串，可以是负数也可以是正数；endptr指向第一个非法字符的地址，如果endptr为NULL则不指向第一个非法字符的地址；base用于指示进制，若base为0，则根据num_str的指示来转换。函数必须检查溢出，如果正数溢出，返回INT_MAX；若负数溢出，返回INT_MIN。2、一亿个数找最大的1000个数，要求效率高占用内存少。函数原型为：find_max_data(int* source_data, int* max_data)，其中source_data是存放一亿个数的数组，max_data用于存放其中最大的1000个数。3、将一个集合拆分成两个不相交的子集，两个子集元素之和相等，如{1, 2, 3, 4, 5, 6, 7}，拆分成：{2, 5, 7}, {1, 3, 4, 6}给出一个集合，求所有符合上面要求的拆分，效率最高分越高，函数原型为int cal_num(int n);第三题：利用回溯剪枝法空间复杂度：O(n) 栈的最大深度也就是n了时间复杂度：接近于O(2^n-1), 因为本质上程序时一个遍历树的过程，如果没有剪枝，那么树是一个满二叉树，结点共2^n-1个，也就要遍历2^n-1次。虽然剪枝，但速度估计仍是 2^n次方级别的。试了下，调用cal_num(104),好久了结果都没有出来。。。不知用上DP算法会不会好点，不过听说回溯法怎么弄效率都跟不上，最好用递推？
在哪听说的？///file divide_set.h:#ifndef __DIVIDE_SET_H__#define __DIVIDE_SET_H__// 计算集合set的所有满足下列条件的子集合：子集合元素之和等于value
// 子集合的元素对应的label置1void divide_set( int set[], int label[], int len, int i_set, int value );// 对集合{1,2,...n}划分
void cal_num( int n );#endif
///file divide_set.cpp:#include "stdafx.h"#include "divide_set.h"#include <iostream>
using namespace std;
// 查找集合set中，满足元素之和等于value的子集合，结果存于label里
void divide_set( int set[], int label[], int len, int i_set, int value ){ // 输出结果 if ( value == 0 ) { cout<<"{ "; for ( int i=0; i<len; ++i ) { if ( label[i] ) { cout<<set[i]<<" "; } } cout<<"} "; cout<<" , { "; for ( int i=0; i<len; ++i ) { if ( 0 == label[i] ) { cout<<set[i]<<" "; } } cout<<"} "; cout<<endl; return; }if ( i_set >= len || value <0)
{ return; }// 取第i_set个元素
label[i_set] = 1; divide_set( set, label, len, i_set+1, value-set[i_set] ); // 不取第i_set个元素 label[i_set] = 0; divide_set( set, label, len, i_set+1, value );}void cal_num( int n )
{ int* set = new int[n]; int* label = new int[n];// initialize set and label
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;}// 使用了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)
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 ) { bpHistory[i_set+1][value-set[i_set]] = divide_set_v4(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_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
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;// 动态申请二维数组
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 ) //{ // for ( int j=0; j<cols; ++j ) // { // if ( bpHistory[i][j] != -1 ) // ++cnt; // } //} //cout<<"空间利用率："<<(float)cnt/(float)(rows*cols)<<endl;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]; }// 保证元素总和为偶数
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();
//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;//cout<<endl;
//fps.BeginFrame(); //cout<<cal_num_v5(n)<<endl; //cout<<"elapse time : "<<fps.GetElapseTime()<<"秒"<<endl;cout<<endl;
fps.BeginFrame(); cout<<getSetsNum1(n)<<endl; cout<<"elapse time : "<<fps.GetElapseTime()<<"秒"<<endl; }