昨天有个同学去面试了，回来讨论关于面试的题，因为是提前批次的，所以有点难，有点绕，自己写总结了一下：
1.此题是有关24点游戏,(整体的实现在)，其中用到了递归，比较重要的知识点是排列组合，针对此题，简单说就是4（n）个元素，按不同的排列组合方式，有4！（n! 也就是A(n,n)）种方式。都说迭代的人，递归的是神，先利用递归进行实现：（自己觉得代码很简单明了）
#include#include #include using namespace std;void print(vector &arr) //只是简单打印每次输出的结果{ for (const auto c : arr) cout << c << " "; cout << endl;}void perm(size_t t, vector &arr, int &cnt) //核心算法，进行排列组合,t从0开始,cnt计算有多少排列方式{ if (t >= arr.size()) { print(arr); cnt++; return; } for (size_t i = t; i < arr.size(); i++) { if (i != t ) swap(arr[i], arr[t]); perm(t + 1,arr,cnt); //表示对剩下的元素进行排列组合，perm{b,c,d}/ perm{a,c,d}/ perm{b,a,d}/ perm{b,c,a} if (i != t) swap(arr[i], arr[t]); //表示交换之后再交换回来，要在原有的基础上（a,b,c,d）进行交换 }} int main() //测试{ static int cnt=0; vector arr{ "a", "b" , "c", "d"}; perm(0,arr,cnt); cout << "共有" << cnt <<"种排列组合方法！"<< endl; return 0;}
这里详细讲解下有关递归方法实现原理：n个元素的排列组合表示为perm{x1,x2,x3....,xn}，当有4个元素（a, b, c, d）时，则表示为perm{a, b, c, d}，按递归的方法则perm{a,b,c,d}=a.perm{b,c,d}+b.perm{a,c,d}+c.perm{b,a,d}+d.perm{b,c,a}, 这里加号表示并集的意思，对于为什么是c.perm{b,a,d}而不是c.perm{a,b,d},从代码中swap()函数可以得到它是交换了a和c,同理d.perm{b,c,a}也是交换了a和d。
代码中有两个swap()函数，是因为总是在原有的组合上（a,b,c,d）进行排列交换，具体的过程为：第一轮：开始i=t=0，不交换，也就是a.perm{b,c,d}(递归对b,c,d进行排列组合)，执行完后，不交换；第二轮：交换a和b（swap(arr[1],arr[0])），所以为b. perm{a,c,d}(执行递归)，之后再交换回来(swap(arr[1],arr[0]))则恢复a,b,c,d；第三轮：交换a和c(swap(arr[2],arr[0])，是在a,b,c,d的基础上进行交换（第三轮已经恢复回来了）)，所以为c.perm{b,a,d}(执行递归)，之后再交换回来（swap(arr[2],arr[0])）为a.b.c.d；第四轮：交换a和d (swap(arr[3],arr[0])，也是在a,b,c,d的基础上进行的交换)，为d.perm{b,c,a}(执行递归)，之后再交换回来（swap(arr[3],arr[0])），依然为a,b,c,d，因此执行完整个代码，输入的vector<string> arr依然是保持不变的（为a,b,c,d）。
perm{a,b,c,d}=a.perm{b,c,d}+b.perm{a,c,d}+c.perm{b,a,d}+d.perm{b,c,a}
=a.b.perm{c,d}+a.c.perm{b,d}+a.d.perm{c,b}+b.a.perm{c,d}+b.c.perm{a,d}+b.d.perm{c,a}+c.b.perm{a,d}+c.a.perm{b,d}+c.d.perm{a,b}+d.b.perm{c,a}+d.c.perm{b,a}+d.a.perm{c,b}
= a.b.c.d+a.b.d.c+a.c.b.d+a.c.d.b+a.d.c.b+a.d.b.c+
b.a.c.d+b.a.d.c+b.c.a.d+b.c.d.a+b.d.c.a+b.d.a.c+
c.b.a.d+c.b.d.a+c.a.b.d+c.a.d.b+c.d.a.b+c.d.b.a+
d.b.c.a+d.b.a.c+d.c.b.a+d.c.a.b+d.a.c.b+d.a.b.c
验证后和代码运行结果一致的。。
2 .简单迭代实现，穷举法，虽然迭代看起来逻辑简单，但是时间复杂度很高，当待排列的数目发生变化时，这种方法要改变程序for循环的层数。（程序没有一般性）
#includeusing namespace std;/*这里用迭代实现的排列组合，因为有四个数，所以有四层迭代，也就是说每个位置的数都可以为1，2，3，4 ，但是4个位置同时不能有相等的数出现*//*缺点是当待排列组合的数越来越多，则时间复杂度会很高为n^4*/void perm(int arr[],int &cnt) //这里有四层循环{ for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if (j == i) //i不能等于j continue; for (int k = 0; k < 4; k++) { if (k == i || k == j) //k不能等于i,也不能等j continue; for (int l = 0; l < 4; l++) { if (l==i||l==j||l==k) continue; cout << arr[i] << ' ' << arr[j] << ' ' << arr[k] << ' ' << arr[l] << endl; cnt++; } } } } }int main(){ int arr[4] = { 1, 2, 3, 4 }; static int cnt = 0; perm(arr,cnt); cout << "共有" << cnt << "种方法！" << endl; return 0;}
3.对第二种迭代方法进行优化，循环变为三层，循环的次数正好等于排列组合的方法数。（也是待排序的数目发生变化时要改变程序，程序也没有一般性）
#includeusing namespace std;/*这里用迭代实现的排列组合，对上面的迭代方法进行优化，能减少时间复杂度*//*但是仍然是当待排列组合的数越来越多，则时间复杂度会变高（为排列组合的方法数，这里为4!=24）*/void perm(int arr[], int &cnt) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 4; k++) //当求余4时，结果都是在0，1，2，3之间，刚好为数组的下标 { cout << arr[k % 4] << ' ' << arr[(k + j % 3 + 1) % 4] << ' '; cout << arr[(k + (j + i % 2 + 1) % 3 + 1) % 4] << ' '; cout << arr[(k + (j + (i + 1) % 2 + 1) % 3 + 1) % 4] << endl; //arr[j%3]+" "+arr[(j+i%2+1)%3]+" "+arr[(j+(i+1)%2+1)%3] 3个数的情况 cnt++; } } }}int main(){ int arr[4] = { 0, 1, 2, 3 }; static int cnt = 0; perm(arr, cnt); cout << "共有" << cnt << "种排列组合方法！" << endl; return 0;}
4，当从一个数组中取m个数字，有多少种取法，利用穷举法，这里假设从一个数组中取3个数字。（此处为C（8,3），与上面不同的是取出来的数字不讲究顺序，也就是C（n,m）,从n个元素中取m个元素有多少种取法（m<=n））,程序没有一般性。
#include#include using namespace std;/*穷举法*/void combination(const vector & arr, int &cnt) //这里是三层循环，是从数组中取三个数，要是取4个数，程序就改成4层循环{ for (size_t i = 0; i < arr.size() - 2; i++) //直接改为i