笔试题小解

        最近碰到一个笔试题，大意是从给定的无序数组中选取几个数字使其和为给定的数字，下面以一个数组长为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！