本人有幸参加在清华大学举办的2013年百度校园招聘笔试专场,我报的研发工程师,可惜笔试后就没信了,自己感觉做得也不是很好,但我这个人爱琢磨,不会的问题会留在心里想,其中就一道题,我记得比较清楚,现在我和大家一起来分享:
一 问题描述:
现在百度的设计部门要设计一个三位的密码,给出0到9,a到z,A到Z这些字符,从这些字符里选取3个作为密码,请设计算法输出所有可能的密码。
二 解题思路:
其实这是一道组合递归求解的问题,我们现在先举一个引例:给出012345,求这6位数的3位组合,那么应该是如下:
000 001 002 ... 005
010 011 012 ... 015
... ........ .............
550 551 552 .... 555
一共的组合数是6*6*6=216种
好的,也就是说每一位是0到5中的任意一个数
那么如果是01...9abc...zABC...Z,方法是一样的,一共是32*32*32=238328种
那么怎么实现?递归可以实现,具体是在循环中嵌入递归
三 代码:
/* This is a free Program, You can modify or redistribute it under the terms of GNU *Description:2013年校园招聘--百度一道笔试题三位密码组合问题递归求解 *Language: C++ *Development Environment: VC6.0 *Author: Wangzhicheng *E-mail: 2363702560@qq.com *Date: 2012/12/15 */ #include <iostream> #include <string> #include <cstdlib> #include <cmath> using namespace std; /* *Solution类封装了使用了递归的组合算法 *str:指向当前用户输入的字符串 *password:指向密码字符串 *selectM:选取几个数来组合 */ class Solution { private: char *str; char *password; int selectM; /* *递归实现组合 *selectCur:指向password中当前被操作的字符 */ void Combine(int selectCur) { if(selectCur>=selectM) { //一种新的组合产生 cout<<"第"<<++cnt<<"种组合是:"<<password<<endl; } else { int i; for(i=0;str[i];i++) { password[selectCur]=str[i]; Combine(selectCur+1); } } } public: int cnt; //用于计算组合数 Solution(const char *string,int selectM) { int n=strlen(string); str=new char[n+1]; if(!str) exit(1); strncpy(str,string,n+1); this->selectM=selectM; password=new char[selectM+1]; if(!password) exit(1); password[selectM+1]='\0'; cnt=0; } void Combine() { Combine(0); }
~Soution() {
delete password;
delete str;
}
}; void main() { int N=3; //3为密码 int M=26; //26个字母 int P=10; //10个数字 int i; string s; for(i=0;i<P;i++) s+=i+'0'; for(i=0;i<M;i++) s+=i+'a'; for(i=0;i<M;i++) s+=i+'A'; cout<<s<<endl; int cnt=pow((2*M+P),3); //总共的组合数 cout<<"该"<<N<<"位密码应该有"<<cnt<<"种组合"<<endl; Solution solution(s.c_str(),N); solution.Combine(); if(solution.cnt==cnt) cout<<"输出组合数正确!"<<endl; else cout<<"输出组合数不正确!"<<endl; }
四:测试