蓝桥杯
将编号为1~10的10本书排放在书架上，要求编号相邻的书不能放在相邻的位置。请计算一共有多少种不同的排列方案。
代码是这样的
package 第三次模拟;
public class Demo3图书排列 {
static int res=0;
public static boolean check(int a[])
{
int l=a.length;
for(int i=0;i<l-1;i++)
{
// 两个相邻的元素，如果它们的数字是相邻的，就是两个元素相减的绝对值 == 1；那么就return false;
if(Math.abs(a-a)==1)
{
return false;
}
}
return true;
}
// static int count=0;
// 将a[]中的a 与 a的值互换
public static void swap(int a[],int x,int y)
{
//位运算转换节省内存，如果x==y的话，无需转换
if(x==y) return;
a^=a;
a^=a;
a^=a;
// int temp =a;
// a=a;
// a=temp;
}
public static void dfs(int a[],int begin,int end)
{
if(begin==end)
{
// 检查相邻的书是否被放在了相邻的位置：以数字来代表书；相邻两个数字的差的绝对值要不等于1
if(check(a))
// 如果相邻的两个数字的差的绝对值不等于1，则找到了一种方案。
res++;
}
for(int i = begin; i <= end; i++)
{
swap(a,begin,i);
dfs(a,begin+1,end);
swap(a,begin,i);
}
}
public static void main(String[] args) {
int a[]={1,2,3,4,5,6,7,8,9,10};
dfs(a,0,a.length-1);
System.out.println(res);
}
}
看不懂这个for循环
for(int i = begin; i <= end; i++)
{
swap(a,begin,i);
dfs(a,begin+1,end);
swap(a,begin,i);
}
第一个 swap(a,begin,i); 有啥意义呢i和begin始终是相同的？？？
后面的dfs(a,begin+1,end); 重新调用这个函数，在下一个swap(a,begin,i);不就执行不到了吗？？？？
救救孩子吧
begin跟i怎么会始终相同呢？i++是干什么的。 这个其实全排列的思想，用的是递归实现的，只不过加了一个相邻数的判断；
三言两语说明白有点困难，我可以给你说个大概意思
整个算法是按照第i（i为1~10）个字母的可取值来断定的
比如，首字母可以为1~10，一共是是个选择
第二个字母就是2~10，一共就是9个选择，
依次类推，其实到这里就可以发现，应该使用递归了
当到最后一个的时候，就是他本身了，此时已经不需要在交换了，因为这个时候已经是一个排好序的数组了
进行相邻数的验证
因为你现在的数组是使用第一个swap交换之后得到的，为了不影响下面数组的交换
所以，你需要把数组还原到交换之前的状态，所以又调用了一次swap函数，让其可以正常进行下一次的交换
交换是在最深层里面逐渐像外层开始的
过程就像我们手动排顺序一样
拿1~3来举例（数太多的话，结果比较多，不好举例子）
第一个字母可选1,2,3一共三种，而第二个数字就是剩下的两种，最后就剩下一种，当只剩下一个的时候，则证明该排序结束
希望能帮到你吧，不懂全排列的话可以去看下博客，然后B站我看了下，也有对应的全排列思路视频讲解。
页:
[1]