笔试题小解

        最近碰到一个笔试题，大意是从给定的无序数组中选取几个数字使其和为给定的数字，下面以一个数组长为10的整型数组为例，选出其中四个数字之和为10。

        算法使用C++编写，因为来的比较快，Java表达算法不是很给力感觉，代码如下

#include<iostream>
#define total 4   //所需要选取出来的个数 
#define arrayLength 10  //数组长度 
using namespace std;
void showResult(int a[]);
int a[arrayLength]={0,1,1,2,9,8,2,4,6,5};
int result[total]={-1,-1,-1,-1};
void  fun(int sum,int beginLoc,int needSelectNum)
{
if(sum<0)return;
if(beginLoc>=arrayLength) return;
if(needSelectNum==1){
for(int i=beginLoc;i<arrayLength;i++){
if(sum==a[i]){
result[total-needSelectNum]=i;
showResult(result);
}
}
return;
}
result[total-needSelectNum] =beginLoc;
fun(sum-a[beginLoc],beginLoc+1,needSelectNum-1);//选 
fun(sum,beginLoc+1,needSelectNum);	//不选 
}
void showResult(int result[]){
for(int i=0;i<total;++i){
cout<<result[i]<<"  ";
}
cout<<endl;
}
int main()
{
//初始值为10 
int sum=10;
result[0]=0;
fun(sum-a[0],1,4-1);
fun(sum,1,4);
}

    result用来保存最终的四个数的在数组中的位置

    结果如下：

0  1  2  5
0  1  7  9
0  2  7  9
0  3  6  8
1  2  3  8
1  2  6  8
1  3  6  9
2  3  6  9

    简单的递归，也只是为了得出结果而已，没有考虑时间复杂度优化，over。

     如果是不定个数的和，如求上述中任意和为10的数字序列，代码如下：

#include<iostream>
#define total 4   //所需要选取出来的个数 
#define arrayLength 10  //数组长度 
using namespace std;
int result[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int a[arrayLength]={0,1,1,2,9,8,2,4,6,5};
void showResult(int current_loc){
for(int i=0;i<current_loc;i++){
cout<<result[i]<<" ";
}
cout<<endl;
} 
void fun( int sum,int begin_loc,int current_loc){
if(sum<0)return ;
if(begin_loc>=arrayLength)return ;
if(sum==0){
showResult(current_loc);	
return  ;
}
result[current_loc] =begin_loc;
fun(sum-a[begin_loc],begin_loc+1,current_loc+1);    //选
fun(sum,begin_loc+1,current_loc);//不选 
} 
int main(){
int sum=10;
int current_loc=0;
result[current_loc]=0;
fun(10-a[current_loc],1,current_loc+1);
fun(10,1,current_loc);
return 0;
}

   结果如下：

0 1 2 3 6 7
0 1 2 3 8
0 1 2 5
0 1 2 6 8
0 1 4
0 2 4
0 3 5
0 3 6 8
0 5 6
0 7 8
1 2 3 6 7
1 2 3 8
1 2 5
1 2 6 8
1 4
2 4
3 5
3 6 8
5 6
7 8

    其实两者的思维很一样，递归结构也是差不多，over again！