最近碰到一个笔试题,大意是从给定的无序数组中选取几个数字使其和为给定的数字,下面以一个数组长为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!
相关推荐
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 java笔试题 ...
嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集嵌入式软件笔试题合集...
大连华信去年的笔试题,可以给各位即将工作的同学一些参考
用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题用友笔试题
c笔试题c笔试题c笔试题c笔试题c笔试题c笔试题
C#笔试题大全C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.C#笔试题大全.,让你...
c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总c++笔试题汇总
java 笔试题 j2ee笔试题 java笔试题 j2ee 笔试题
赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融笔试题.jpg赛融...
JAVA笔试题,面试题JAVA笔试题,面试题JAVA笔试题,面试题JAVA笔试题,面试题JAVA笔试题,面试题
中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 v中兴笔试题 中兴笔试题 ...中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题 中兴笔试题
C++ 笔试题汇总 C++ 笔试题汇总 C++ 笔试题汇总 C++ 笔试题汇总
软件公司笔试题软件公司笔试题软件公司笔试题
c++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rarc++笔试题汇总.rar
JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题汇总JSD面试笔试题...
百度笔试题 百度 笔试题 百度 笔试题
2021紫光笔试题IC校招笔试题