迅雷2015成都笔试题

　　二笔只有三道题，分值分别为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置1

　　void 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

　　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

　　{

　　if ( label[i] )

　　{

　　cout<