蓝桥杯——车牌(dfs全排列问题)
一.题目
分析题目:要求6个位置,每个位置放一个数,不能连续三位相同,这些为约束条件也就是减枝函数的内容,最常规的dfs排列问题,只要减枝写对没什么问题
代码:
public static int sum = 0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s = "0123456789ABCDEF";
char[] ch = s.toCharArray();
char[] res = new char[6];
dfs(res,ch,0);
System.out.println(sum);
scan.close();
}
public static void dfs(char[] res,char[] ch ,int index)
{
if(index==6)
{
sum++;
return;
}
if(index<3) for(int i = 0;i<16;i++)
{
res[index] = ch[i];
if(cheak(res,index))
dfs(res,ch,index+1);
}
else for(int i = 0;i<10;i++)
{
res[index] = ch[i];
if(cheak(res,index))
dfs(res,ch,index+1);
}
}
public static boolean cheak(char[] res,int index)//核心
{
if(index<=2)
return true;
for(int i = 0;i<index-1;i++)
{
if(res[i] == res[i+1]&& res[i+1]==res[i+2])
return false;
}
return true;
}
一开始错误:
1.把题目中后三位只能是0-9忘记了 导致组合情况出错 粗心问题