【思特奇杯·云上蓝桥-算法集训营】第2周

全排列+回溯

代码如下：

import java.util.Scanner;
 
 
public class Main {
 
    static int []arr={1,2,3,4,5,6,7,8,9};
    static int n;
    static int count=0;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        qpl(0);
        System.out.println(count);
 
    }
     
    //全排列
    public static void qpl(int n) {
        if (n==9) {
            scc(arr);
        }
        for (int i = n; i < 9; i++) {
            int zjs=arr[i];
            arr[i]=arr[n];
            arr[n]=zjs;
             
            qpl(n+1);
             
            //回溯
            zjs=arr[i];
            arr[i]=arr[n];
            arr[n]=zjs;
        }
    }
     
    public static void scc(int []arr) {
        for (int i = 1; i <= 7; i++) {
                int jhq=jq(0, i);//+前的数
                if (jhq>=n) {
                    continue;
                }
            for (int j = 1; j < 9-i; j++) {
                int num1=jq(i, j);
                int num2=jq(i+j, 9-i-j);
                if (num1%num2==0&&jhq+num1/num2==n) {
                    count++;
                }
            }
        }
    }
     
    public static int jq(int qd,int cd) {
        int nn=1;
        int num=0;
        for (int i =qd+cd-1; i >=qd; i--) {
            num+=arr[i]*nn;
            nn*=10;
        }
        return num;
    }
}

递归模拟

代码如下：

class Main{
    static int count = 0;
    public static void main(String[] args) {
        int n = 2;
        dfs(2,0,0);
        System.out.println(count);
    }

    public static void dfs(int n,int d,int h){
        if(n==1 && d==5 && h==9){
            count++;
            return;
        }
        if(n<=0 || d>5 || h>9){
            return;
        }
        dfs(n-1,d,h+1);
        dfs(n*2,d+1,h);
    }
}