265
【试练】某公司面试试题
该公司笔试题就1个，要求在10分钟内作完。
题目如下：用1、2、2、3、4、5这六个数字，写一个main函数，打印出所有不同的排列，
如：512234、412325等，要求："4"不能在第三位，"3"与"5"不能相连。请问这题怎么做呢？
以前学过全排列的实现方法，但是记不太清，因为数据比较少，我用递归解决了；
答案组合很多，就不一一贴出了
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int num,flag;
}a[6];
int db[10];
double number=0;
void Fun(int n,int sum,int before)
{
int i;
if((n==5&&before==3)||(n==5&&before==3))
return;
if(sum==6)
{
db[sum]=n;
if(db[3]==4)
return;
for(i=1;i<=6;i++)
printf("%d",db[i]);
puts("");
number++;
return;
}
db[sum]=n;
for(i=1;i<=6;i++)
{
if(a[i].flag==0)
{
a[i].flag=1;
Fun(a[i].num,sum+1,n);
a[i].flag=0;
}
}
return;
}
int main()
{
int i;
a[1].num=1;
a[2].num=2;
a[3].num=2;
a[4].num=3;
a[5].num=4;
a[6].num=5;
for(i=1;i<=6;i++)
a[i].flag=0;
for(i=1;i<=6;i++)
{
a[i].flag=1;
Fun(a[i].num,1,-1);
a[i].flag=0;
}
printf("一共有%.0lf种组合符合要求",number);
return 0;
}
最后一共有498种组合符合要求。
5个数一共有6*5*4*3*2*1=720种情况，看样子不符合情况的有720-498=222种
纯全排序代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int num,flag;
}a[6];
int db[10];
double number=0;
void Fun(int n,int sum,int before)
{
int i;
if(sum==6)
{
db[sum]=n;
for(i=1;i<=6;i++)
printf("%d",db[i]);
printf("\n");
number++;
return;
}
db[sum]=n;
for(i=1;i<=6;i++)
{
if(a[i].flag==0)
{
a[i].flag=1;
Fun(a[i].num,sum+1,n);
a[i].flag=0;
}
}
return;
}
int main()
{
int i;
a[1].num=1;
a[2].num=2;
a[3].num=3;
a[4].num=4;
a[5].num=5;
a[6].num=6;
for(i=1;i<=6;i++)
a[i].flag=0;
for(i=1;i<=6;i++)
{
a[i].flag=1;
Fun(a[i].num,1,-1);
a[i].flag=0;
}
printf("一共有%.0lf种组合符合要求",number);
return 0;
}
1,2,3,4全排列测试结果：
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
一共有24种组合符合要求
最后更新：2017-04-03 12:56:20