阿里2018笔试题 之 三种颜色排列
程序员文章站
2022-07-13 15:38:30
...
题目:
晚会上(具体是不是晚会不太记得了...)所有人要站成一排。有三种颜色的衣服,要求相邻的人穿不同颜色的衣服。输入每种颜色衣服的数量,问总共有多少种排列方式。
例:
输入:1 1 1
输出:6
题目分析:
可以采用递归的做法。假设已经排好了n个人,则第n+1个人的衣服可从另外两种颜色中选。
递归终止的条件是:所有的衣服已经用完或者没有可以选的衣服。
代码:
#include <iostream>
#include <vector>
using namespace std;
int arrange(vector<int>& cloth, int last, int len);
int total; // 衣服总数
void main()
{
vector<int> cloth(3); // 三种颜色的衣服数量
for (int i = 0; i < 3; i++)
{
cin >> cloth[i];
total += cloth[i];
}
int cnt = arrange(cloth, -1, 0);
cout << cnt << endl;
cin.get();
}
//
// cloth: 三种颜色剩余衣服数量
// last: 前一个颜色
// len: 当前已经排列了几个
//
int arrange(vector<int>& cloth, int last, int len)
{
if (len == total) // 全部排列完
return 1;
int cnt = 0;
for (int i = 0; i < 3; i++) // 检查每种颜色
{
if (i != last && cloth[i] > 0) // 与前一个不同颜色,且有剩余衣服
{
cloth[i]--;
cnt += arrange(cloth, i, len + 1); // 排列下一个
cloth[i]++;
}
}
return cnt;
}
推荐阅读