欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

阿里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;
}

 

相关标签: 颜色排列