题目描述

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

输入

从标准输入读入一个正整数N (N< 1000*1000)

输出

程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！

样例输入

100

样例输出

11

算法1

解法一：穷举整数部分和分母，然后计算分子

解法二：全排列1~9这九个数，然后在分成三段，整数，分子，分母计算值

解法三：在第一种方法的思路上进行了优化

java 代码

解法一：

import java.util.Scanner;

public class 带分数 {

    /**
     * n= a + b/c
     */
    public static void main(String[] args) {

        Scanner scanner=new Scanner(System.in);
        int n=Integer.parseInt(scanner.nextLine());
        long t1=System.currentTimeMillis();
        String[] arr=new String[]{"1","2","3","4","5","6","7","8","9"};

        int t=0;
        int conut=0;
        String string="";
        for (int i = 1; i < n; i++) {
            for (int j = 2; j < 10000; j++) {

                t=(n-i)*j;
                string=""+i+j+t;
                if(string.length()!=9){
                    continue;                   
                }else {
                    boolean fa=false;

                    for (int k = 0; k < arr.length; k++) {
                        int index=string.indexOf(arr[k]);
                        if(index==-1){
                            fa=false;
                            break;
                        }
                        fa=true;
                    }
                    if(fa){
                        conut++;
                    }
                }
            }
        }
    System.out.println(conut);
    long t2=System.currentTimeMillis();
    System.out.println(t2-t1);
    }
}

解法二：

import java.util.Scanner;

public class 带分数 {
    static int n,res;
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();

        long t1=System.currentTimeMillis();
        int[] data={1,2,3,4,5,6,7,8,9};
        getQuanpailie(data,0);
        System.out.println(res);
        long t2=System.currentTimeMillis();
        System.out.println(t2-t1);              //看计算机的耗时
    }

    //计算各部分结果
    private static int getNum(int[] data, int i, int j) {
        int num=0;
        for (int k = i; k < j; k++) {
            num=data[k]+num*10;
        }
        return num;
    }
    private static void getQuanpailie(int[] data, int k) {
        //当1-9每个数字每次计算都出现了，枚举三个变量 整数a，分子b，分母c
        if(k==data.length){
            //将数组分为三部分
            for (int i = 1; i < data.length; i++) {
                for (int j = i+1; j < data.length; j++) {
                    int pre=getNum(data,0,i);
                    int mid=getNum(data,i,j);
                    int fon=getNum(data,j,9);

                    if(mid%fon!=0)
                        continue;
                    if(pre+mid/fon==n)
                        res++;
                }
            }
        }

        for (int j = k; j < data.length; j++) {     //防止重复枚举,所以从K开始枚举，k前面的数已经枚举
           {int t=data[k];data[k]=data[j];data[j]=t;}//试探,打乱原有数组的值,以便按照相同两层for循环顺序枚                                             举不同的数，
            getQuanpailie(data,k+1);
            {int t=data[k];data[k]=data[j];data[j]=t;}//回溯
        }
    }
}

解法三：

/**
 * 优化减少时间复杂度。
 */
import java.util.Arrays;
import java.util.Scanner;

public class PREV_3带分数2 {
    static int[] flag; //若已出现i,则flag[i]为1；
    static int flags; //出现过的数码的个数；
    static int[] backupFlag; //备份flag
    static int backupFlags;//备份flags
    static int[] maxDown = {0,5000,999,500,99,50,9,5,0}; //maxDown[i]表示整数部分left中的数码个数（backupFlags）为i个时，down的最大可能值

    /**
     * 检验整数n的各位数码是否在1～9之间，且至多出现1次
     * @param n
     * @return
     */
    static boolean check(int n){
        while(n>0){
            if(flag[n%10]!=0)
                return false;

            flag[n%10] = 1;
            flags++;
            n /= 10;
        }       

        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int left,right,up,down; //n = left + right ;  right = up/down

        int count = 0;
        for (left = 1; left < n; left++) {
            flag = new int[10];
            flag[0] = 1;  //不能出现0
            flags = 0;

            //如果整数left违规（出现了0或重复数字），则尝试下一个left。
            if(check(left)==false) 
                continue;

            //备份现场：备份flag和flags,为试商做准备
            backupFlag = Arrays.copyOf(flag, flag.length);
            backupFlags = flags;

            right = n - left;
            for(down=1; down<maxDown[backupFlags]; down++){

                //还原现场
                flag = Arrays.copyOf(backupFlag, backupFlag.length);
                flags = backupFlags;

                up = right*down;
                if(!check(up))
                    continue;
                if(!check(down))
                    continue;
                if(flags==9){
                    //System.out.println(left+"+"+up+"/"+down);
                    count++;
                }

            }
        }
        System.out.println(count);
    }
}