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