题目:用1、2、2、3、4、5这六个数字,用c写一个main函数,打印出所有不同的排列
上次碰到一个面试 题目好像是这样的题目:用1、2、2、3、4、5这六个数字,用C写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:”4″不能在第三位,”3″与”5″不能相连.我没写出..希望大家帮我看一下 到底怎么该怎么写?
#include <stdio.h> static int path[6]; static int data[6]={1,2,2,3,4,5}; int count; bool IsSafe(int pos,int index) { if( pos == 2 && data[index] == 4) return false; if(pos > 0 && path[pos-1] == 3 && data[index] == 5) return false; if(pos > 0 && path[pos-1] == 5 && data[index] == 3) return false; for( int i = 0; i < pos; i++) if( path[i] == index) return false; return true; } void print() { count++; for( int i = 0; i != 6; ++i) printf("%d",data[path[i]]); printf("\t"); } void trial(int pos) { if (pos >= 6) print(); else for(int i=0; i<6;i++) { if(IsSafe(pos,i)) { path[pos]=i; trial(pos+1); } } } int main() { trial(0); printf("\ntotal counts:%d\n",count); return 0; }
#include<stdio.h> void dfs(bool foot[],int mem[],int depth,int n) { int i; if(n == depth) { for(i = 0;i<n-1;i++) printf("%d ",mem[i]); printf("%d\n",mem[i]); return ; } for(i = 0;i<n;i++) { if(!foot[i]) { if(4 == i+1 && 2 == depth || mem[depth-1] == 3 && 5 == i+1 || mem[depth-1] == 5 && 3 == i+1) continue; foot[i] = true; mem[depth] = i+1; dfs(foot,mem,depth+1,n); foot[i] = false; } } } int main() { int i,j,n; scanf("%d",&n); while(n--) { bool foot[8] = {0}; int mem[8] = {0}; int s; scanf("%d",&s); dfs(foot,mem,0,s); } return 0; }