蓝桥杯

丸子酱ovo

将编号为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[i]-a[i+1])==1)  
            {  
                return false;  
            }  
        }  
        return true;  
    }  
//    static int count=0;
//    将a[]中的a[x] 与   a[y]  的值互换
    public static void swap(int a[],int x,int y)  
    {  
            //位运算转换节省内存，如果x==y的话，无需转换
            if(x==y) return;
           
            a[x]^=a[y];  
            a[y]^=a[x];  
            a[x]^=a[y];
//        int temp =a[x];  
//        a[x]=a[y];  
//        a[y]=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);  不就执行不到了吗？？？？


救救孩子吧

yumson

begin跟i怎么会始终相同呢？i++是干什么的。

连帅帅

这个其实全排列的思想，用的是递归实现的，只不过加了一个相邻数的判断；
三言两语说明白有点困难，我可以给你说个大概意思
整个算法是按照第i（i为1~10）个字母的可取值来断定的
比如，首字母可以为1~10，一共是是个选择
第二个字母就是2~10，一共就是9个选择，
依次类推，其实到这里就可以发现，应该使用递归了
当到最后一个的时候，就是他本身了，此时已经不需要在交换了，因为这个时候已经是一个排好序的数组了
进行相邻数的验证
因为你现在的数组是使用第一个swap交换之后得到的，为了不影响下面数组的交换
所以，你需要把数组还原到交换之前的状态，所以又调用了一次swap函数，让其可以正常进行下一次的交换
交换是在最深层里面逐渐像外层开始的
过程就像我们手动排顺序一样
拿1~3来举例（数太多的话，结果比较多，不好举例子）
第一个字母可选1,2,3一共三种，而第二个数字就是剩下的两种，最后就剩下一种，当只剩下一个的时候，则证明该排序结束
希望能帮到你吧，不懂全排列的话可以去看下博客，然后B站我看了下，也有对应的全排列思路视频讲解。