題目轉自:
http://blog.163.com/ecy_fu/blog/static/444512620098228849190/
二筆只有三道題，分值分別為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算法會不會好點，不過聽說回溯法怎么弄效率都跟不上，最好用遞推？
在哪聽說的？
http://topic.csdn.net/u/20090922/11/ebc26b48-6581-40c3-afe0-a95ca2d700d5.html
/**//////////////////////////////////////////////////////////////////
//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 <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;
}
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/zdl1016/archive/2009/10/04/4632688.aspx