计科院20级刘磊

用户名：1579364808

访问量：4389

签　名：

写代码困了，就喝杯Java咖啡提提神

等　　级
排　　名	2497
经　　验	2278
参赛次数	6
文章发表	16
年　　龄	19
在职情况	学生
学　　校	怀化学院
专　　业	计算机科学与技术

　　自我简介：

计算机科学与技术专业的一名小码农

TA的其他文章

回溯法解决全排列
浏览：323

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

1440: 蓝桥杯2013年第四届真题-带分数--dfs(回溯法)--全排列

　　作者: 计科院20级刘磊　　　　发表时间：2021-10-05 19:30:02 浏览：455　|　评论：0　

原题链接：蓝桥杯2013年第四届真题-带分数

### 解题思路:
全排列+确定加号和除号位置
### 剪枝:
加号位置确定时剪枝:整数部分不可能大于n
除号确定时剪枝:分子位数一定不会小于分母
### 注意事项:
判断时注意分子一定得整除分母,这是容易忽略的

```java
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> path = new ArrayList<>();
    static boolean[] book = new boolean[10];
    static int res = 0;

public static void main(String[] args) {

Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        dfs(n);
        System.out.println(res);
    }

public static void dfs(int n) {
        if (path.size() == 9) {
            //整数部分
            int integerPart = 0;
            //枚举加号位置
            for (int i = 0; i < 7; i++) {
                //计算整数部分
                  integerPart = getNum(0, i);
                if (integerPart >= n) break;
                //枚举除号的位置
                for (int j = (i + 1 + 8) / 2; j < 8; j++) {
                    int child = 0;
                    int mother = 0;
                    //计算分子
                    child=getNum(i+1,j);
                    //计算分母
                    mother = getNum(j+1,8);
                    int temp =integerPart + child / mother;
                    if (child%mother==0&&n == temp) res++;
                }
            }
            return;
        }
        for (int i = 1; i <= 9; i++) {
            if (book[i] == false) {
                path.add(i);
                book[i] = true;
                dfs(n);
                path.remove(path.size() - 1);
                book[i] = false;
            }
        }
    }

public static int getNum(int start, int end) {
        int num = 0;
        for (int i = start; i <= end; i++) {
            num = num * 10 + path.get(i);
        }
        return num;
    }
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

校门外的树（C语言代码）

弟弟的作业（C语言代码）

蛇行矩阵（C++代码）（预生成结果以节省每次生成的时间）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

1440: 蓝桥杯2013年第四届真题-带分数--dfs(回溯法)--全排列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

模拟计算器（C语言代码）

弟弟的作业（C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

WU-输出正反三角形（C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

蚂蚁感冒（C语言代码）

局部变量作函数返回值的问题

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

校门外的树 （C语言代码）

弟弟的作业 （C语言代码）

蛇行矩阵 （C++代码）（预生成结果以节省每次生成的时间）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

1440: 蓝桥杯2013年第四届真题-带分数--dfs(回溯法)--全排列

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

模拟计算器 （C语言代码）

弟弟的作业 （C++代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

WU-输出正反三角形 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

蚂蚁感冒 （C语言代码）

局部变量作函数返回值的问题

校门外的树（C语言代码）

弟弟的作业（C语言代码）

蛇行矩阵（C++代码）（预生成结果以节省每次生成的时间）

　　评论区

模拟计算器（C语言代码）

弟弟的作业（C++代码）

WU-输出正反三角形（C++代码）

蚂蚁感冒（C语言代码）