本文主要是介绍笔试题小解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最近碰到一个笔试题,大意是从给定的无序数组中选取几个数字使其和为给定的数字,下面以一个数组长为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!
这篇关于笔试题小解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!