蓝桥杯笔记关于递归

类型一

全排列，比如现在有字符串”abc”，它还可以有”acb”, “bac”, “bca”, “cab”, “cba”等排列方式. 通过全排列的方式可以得到全部符合条件的结果, 然后再从可能的结果中选出符合要求的结果.大部分情况需要考虑回溯.

例题: 带分数

100 可以表示为带分数的形式：100 = 3 + 69258 / 714
还可以表示为：100 = 82 + 3546 / 197
注意特征带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。

题目要求：
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
例如：
用户输入：
100
程序输出：
11
再例如：
用户输入：
105
程序输出：
6

观察题目发现：

1.每个数字只能出现一次（没有0）

2.每一次排列后，都需要进行回溯，归位每个数字原来的位置（1,2,3,4,5,6,7,8,9,）

参考了一下这个：全排列问题理解

自己撸的代码：

import java.util.Scanner;

public class _带分数 {
    public static int[] arr={1,2,3,4,5,6,7,8,9};
    public static int res = 0;//结果个数
    public static int n;
    public static void process(int index){
        if(index == arr.length){
            check();
            return;
        }
        for(int i=index;i<arr.length;i++){
            swap(i,index);
            process(index+1);
            swap(i,index);
        }
    }

    private static void check() {
        for(int i = 0; i < arr.length - 3; i++){
            for(int j = i + 1; j < arr.length - 2; j++){
                int jiaShu = getNum(0, i);//带分数种的加数
                int fenZi = getNum(i + 1, j);//分子
                int fenMu = getNum(j + 1, arr.length - 1);//分母
                if(fenZi % fenMu == 0 && jiaShu + fenZi / fenMu == n){//分子要能整除分母(也可以用float保存3种数, 就不用判断整除)
                    res++;
                }
            }
        }
    }

    private static int getNum(int i, int i1) {
        int num=0;
        int system = 1;//用于算10的次方的基数, 如果用系统Math.pow()算10次方的话会慢很多.
        for(int n=i1;n>=i;n--){
            num+=system*arr[i1--];
            system*=10;
        }
        return num;
    }

    public static void swap(int i, int index) {
        int t=arr[i];
        arr[i]=arr[index];
        arr[index]=t;
    }

    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        n=s.nextInt();
        process(0);
        System.out.println(res);
    }
}