个人博客
0%

NYOJ-32-深度优先搜索算法

发表于 分类于

NYOJ-32-深度优先搜索算法

最近两天学习了深度优先算法，并做了一道oj题，这里记录一下。

题目描述：

描述

找出从自然数1、2、… 、n（0<n<10）中任取r(0<r<=n)个数的所有组合。

输入描述

输入n、r。

输出描述

按特定顺序输出所有组合。
特定顺序：每一个组合中的值从大到小排列，组合之间按逆字典序排列。

1
2
3
4
5
6
7
8
9
10
11
12
输入 5 3
输出：
543
542
541
532
531
521
432
431
421
321

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Scanner;

public class NYOJ32 { //组合数，深度优先搜索

    static Scanner in =new Scanner(System.in);
    static int n = in.nextInt(); //读取基础数据
    static int r = in.nextInt(); //读取长度
    static int[] book = new int[n+1];//标记数据是否被使用
    static int[] out = new int[r+1]; //设置输出长度

    public static void main(String[] args) {

        dfs(1);
    }

    public static void dfs(int step) {
        int i = 0;
        if (step > r) {

            for (i=1;i<=r-1;i++){  //判断高位大于低位
                if (out[i]<out[i+1]){
                    return;
                }
            }
            for (i = 1; i <=r; i++) {
                System.out.print(out[i]);
            }
            System.out.println("");
            return;
        }
        for (i = n; i > 0; i--) {  //深度优先算法
            if (book[i] == 0) {
                out[step]=i;
                book[i]=1;
                dfs(step+1);
                book[i]=0;
            }
        }
        return;
    }
}

学到了，理解深度优先搜索的关键在于解决 “当下该如何做” 。至于 “下一步如何做” 则与 “当下该如何做” 是一样的。