打印经过限定后的数字排列

On October 18, 2010, in 算法, 笔试面试, by sponge

题目:给定6个数字,1,2,2,3,4,5,打印所有的排列

要求:

  1. 所有的4均不会出现在排列的第4个位置
  2. 数字3和数字5不能相邻
  3. 排列不能重复。

实现思想:

采用回朔的方法便利所有可能的排列,其中把不符合题目要求的去除。需要额外注意的是,数字中出现了两个2,如果单纯的遍历,会打印两次2在某个位置的排列,要注意把这个重复给去除。

C语言代码实现如下:

#include<stdlib.h>
#include<stdio.h>
 
int a[6]={1, 2, 2, 3, 4, 5 }; 
int b[6]; //用来存放排列好的序列
int pointer; //回朔指针
int total; //总的排列个数
int range(){
	int i;
	if(pointer == 6){
		printf("total:%d, range: %d %d %d %d %d %d \n", 
		++total, b[0], b[1], b[2], b[3], b[4], b[5]);
	}
	for(i=0; i<6; i++){
		if(a[i] == 0)
			continue;
 
		if(a[1]!=0 && i==2)
			continue; //防止重复使用2
 
		if(pointer>0 && (b[pointer-1]==3 && a[i] == 5 
		   || b[pointer-1]==5 && a[i]==3)) //防止3,5相邻
			continue;
 
		if(pointer == 3 && a[i]==4)
			continue; //防止数字4出现在位置4
 
		b[pointer] = a[i];
		pointer ++;
		a[i] = 0; //使用过的数字给设置成0,防止重复使用
		range();
		pointer --;
		a[i] = b[pointer];		
	}
}
 
int main(){
	range();
	return 0;	
}

这个题目是sohu2011笔试题,题目并不难,关键是细节要考律全面,如要去除因为两个2而导致的重复序列。
我在笔试卷子上写的乱七八糟,而一在电脑上立马就写出来了,果然还是很不擅长笔试阿!

anyShare分享到:
Tagged with:
 

1 Response » to “打印经过限定后的数字排列”

  1. yjf512 says:

    学习了~~顶

Leave a Reply to yjf512

Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).