首页 > 其他 > 详细

深度搜索优先(全排列)

时间:2018-07-15 23:43:12      阅读:283      评论:0      收藏:0      [点我收藏+]
 
package Mypackage;
import java.util.Scanner;
public class 全排列{
    static int a[]=new int[10];
    static int book[]=new int[10];
    static int n=0;
    static void dfs(int step)//step表示出现在第几个盒子里面前
    {
        int i;
        if(step==n+1)//如果站在第n+1个盒子面前,则表示前n个盒子已经放好扑克牌、
        {
            for(i=1;i<n;i++) 
            System.out.println(""+a[i]);
            System.out.println();//System.out.print();
            return;//返回之前的一步(最近一次调用dfs方法的地方)
        }
    //此时葬在第step个盒子面前,应该放哪张牌呢?
    //按照1、2、3……n的顺序一一尝试
    for(i=1;i<n;i++) {
        //判断扑克牌i是否在手上
        if(book[i]==0)//book[i]=0表示i号扑克牌在手上
        {//开始尝试使用扑克牌i是否在手上
            a[step]=i;//将i号扑克牌放入到第step个盒子中
            book[i]=1;//将book[i]设为1,表示i号扑克牌已经不再手上
            //第step个盒子已经放好扑克牌,接下来需要走到下一个盒子面前
            dfs(step+1);//这里通过函数的递归调用来实现(自己调用自己)
            book[i]=0;//这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试
        }    
                     }//先执行什么?//二分搜索也是类似的答案,一步执行一步
    return;
    }                
    public  static void main(String args[]) {
        Scanner ms=new Scanner(System.in);
    /*    System.out.println("输入一个整数:");*/
        int n=ms.nextInt();
        dfs(1);
        getchar();getchar();
        
        
    }
    private static void getchar() {
        // TODO Auto-generated method stub
        
    }
    }

题目:输入一个数n:输出1~n的全排列

package Mypackage;
import java.util.Scanner;
public class 全排列{
    static int a[]=new int[10];
    static int book[]=new int[10];
    static int n=0;
    static void dfs(int step)//step表示出现在第几个盒子里面前
    {
        int i;
        if(step==n+1)//如果站在第n+1个盒子面前,则表示前n个盒子已经放好扑克牌、
        {
            for(i=1;i<n;i++) 
            System.out.println(""+a[i]);
            System.out.println();//System.out.print();
            return;//返回之前的一步(最近一次调用dfs方法的地方)
        }
    //此时葬在第step个盒子面前,应该放哪张牌呢?
    //按照1、2、3……n的顺序一一尝试
    for(i=1;i<n;i++) {
        //判断扑克牌i是否在手上
        if(book[i]==0)//book[i]=0表示i号扑克牌在手上
        {//开始尝试使用扑克牌i是否在手上
            a[step]=i;//将i号扑克牌放入到第step个盒子中
            book[i]=1;//将book[i]设为1,表示i号扑克牌已经不再手上
            //第step个盒子已经放好扑克牌,接下来需要走到下一个盒子面前
            dfs(step+1);//这里通过函数的递归调用来实现(自己调用自己)
            book[i]=0;//这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试
        }    
                     }//先执行什么?//二分搜索也是类似的答案,一步执行一步
    return;
    }                
    public  static void main(String args[]) {
        Scanner ms=new Scanner(System.in);
    /*    System.out.println("输入一个整数:");*/
        int n=ms.nextInt();
        dfs(1);
        getchar();getchar();
        
        
    }
 

 

package Mypackage;
import java.util.Scanner;
public class 全排列{
    static int a[]=new int[10];
    static int book[]=new int[10];
    static int n=0;
    static void dfs(int step)//step表示出现在第几个盒子里面前
    {
        int i;
        if(step==n+1)//如果站在第n+1个盒子面前,则表示前n个盒子已经放好扑克牌、
        {
            for(i=1;i<n;i++) 
            System.out.println(""+a[i]);
            System.out.println();//System.out.print();
            return;//返回之前的一步(最近一次调用dfs方法的地方)
        }
    //此时葬在第step个盒子面前,应该放哪张牌呢?
    //按照1、2、3……n的顺序一一尝试
    for(i=1;i<n;i++) {
        //判断扑克牌i是否在手上
        if(book[i]==0)//book[i]=0表示i号扑克牌在手上
        {//开始尝试使用扑克牌i是否在手上
            a[step]=i;//将i号扑克牌放入到第step个盒子中
            book[i]=1;//将book[i]设为1,表示i号扑克牌已经不再手上
            //第step个盒子已经放好扑克牌,接下来需要走到下一个盒子面前
            dfs(step+1);//这里通过函数的递归调用来实现(自己调用自己)
            book[i]=0;//这是非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试
        }    
                     }//先执行什么?//二分搜索也是类似的答案,一步执行一步
    return;
    }                
    public  static void main(String args[]) {
        Scanner ms=new Scanner(System.in);
    /*    System.out.println("输入一个整数:");*/
        int n=ms.nextInt();
        dfs(1);
        getchar();getchar();
        
        
    }
    private static void getchar() {
        // TODO Auto-generated method stub
        
    }
    }

 只有输入没有输出是怎么回事,请求大家的解答

深度搜索优先(全排列)

原文:https://www.cnblogs.com/majiasheng/p/9315600.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!