历届试题 带分数

问题描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。

还可以表示为：100 = 82 + 3546 / 197。

注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

类似这样的带分数，100 有 11 种表示法。

输入格式

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

输出格式

程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

样例输入1

100

样例输出1

11

样例输入2

105

样例输出2

6

思路一：

全排列列出所有的情况，求出满足条件的个数，不过会超时，这时要剪枝

如何建造好的剪枝条件？
本题说的是，n=a+b/c；那么首先a一定是小于n的，又因为n为整数，所以a和b/c都是整数，这就要求
b/c一定可以整除，所以b%c=0，b/c还要满足可除条件，即b>=c。剪枝的三个条件已经确定
(1).a<n；
(2).b%c=0；
(3).b>=c
再加上n=a+b/c就是四个条件了。只要在1至9的全排列中选取满足这四个条件的全排列就是所求的结果之一。
那么在1至9的全排列（9个数字）中如何确定a，b，c的取值范围呢？
a前面已经说过，而又知道，b一定大于或等于c，则b的取值范围一定在a选择过后去选择剩下的一半或一半以上的数据。举个例子，1至9的其中一个全排列--156987423，若a选择156，则b只能选择剩下的987423中的一半或
一半以上，如987、9874、98742。如果b小于剩下的一半，那么一定不满足除法（如98/7432）。c
的范围则是a和b选择剩下的所有了。这样我们就可以判定，假设num=9，a选择9位中的前n位，那
么b的结尾选择范围为第n+（num-n）/2至num-1位数字（结尾为一半或一半以上，最多时到num-1
，给c留一个数字）；
那么利用深度优先搜索（用来得到一个9位的全排列）和适当的判断（剪枝，找出符合3个条件并
且满足n=a+b/c的全排列）就可以解决。

下面是我写的两个版本的代码

版本一 （超时）

import java.util.Scanner;
import java.util.concurrent.atomic.LongAccumulator;

    public class Main{
        public static int num=0;
        public static int[]array=new int[10];
        static int res;
        static int length=0;
        public static void main(String[] args){ 
            Scanner scanner=new Scanner(System.in);
            String th=scanner.next();
             res=Integer.parseInt(th);
            length=th.length();
            for (int i = 1; i <=array.length-1; i++) {
                array[i]=i;
            }
            long a=System.currentTimeMillis();
            perm(array,1, 9);
            System.out.println(num);
            long b=System.currentTimeMillis();
          // System.out.println(b-a);
            
        }
       public static void Swap(int str[], int a, int b)
        {
           int temp = str[a];
            str[a] = str[b];
            str[b] = temp;
        }
        public static void perm(int array[],int k,int m)
        {
            if(k==m) {
                String string="";
                for (int i = 1; i <=array.length-1; i++) {
                    string+=array[i];
                }
                String a="";
                String b="";
                String c="";
                //int num1=Integer.parseInt(string);
                for (int i = 1; i <string.length()-1; i++) {
                    a=string.substring(0, i);
                    int a1=Integer.parseInt(a);
                    if(a1>res) break;
                    for (int j = i+(9-i)/2; j < string.length(); j++) {
                        
                        b=string.substring(i,j);
                        c=string.substring(j,string.length());
                        
                
                        
                        int a2=Integer.parseInt(b);
                        int a3=Integer.parseInt(c);
                        if(a3>a2) continue;
                        if(a2%a3==0) {
                            if(a1+a2/a3==res) {
                                num++;
                            }
                        }
                    }
                }
            return;
 
            }else {
                for (int i = k; i <=m; i++) {
                    Swap(array, i, k);
                    perm(array,k+1,m);
                    Swap(array, i, k);
                }
            }
            
            
        }
      
 }

版本二（正确）

import java.util.Scanner;
import java.util.concurrent.atomic.LongAccumulator;
    public class Main{
        public static int num=0;
        public static int[]array=new int[10];
        static int res;
        static int length=0;
        public static void main(String[] args){ 
            Scanner scanner=new Scanner(System.in);
            String th=scanner.next();
               long a=System.currentTimeMillis();
             res=Integer.parseInt(th);
            length=th.length();
            for (int i = 1; i <=array.length-1; i++) {
                array[i]=i;
            }
         
            perm(array,1, 9);
            System.out.println(num);
            long b=System.currentTimeMillis();
          //  System.out.println(b-a);//显示运行时间，单位ms
            
        }
       public static void Swap(int str[], int a, int b)
        {
           int temp = str[a];
            str[a] = str[b];
            str[b] = temp;
        }
       public static int sumNUm(int array[],int start,int end)
       {
           int sum=0;
           for (int i = start; i <=end; i++) {
            sum=sum*10+array[i];
            
        }
           return sum;
       }
        public static void perm(int array[],int k,int m)
        {
            if(k==m) {
                for (int i = 1; i <array.length-2; i++) {
                    int a=sumNUm(array, 1, i);
                    if(a>res) break;
                    for (int j = i+(9-i)/2; j <array.length-1; j++) {
                        int b=sumNUm(array, i+1, j);
                        int c=sumNUm(array, j+1, m);
                        if(c>b) continue;
                        if(b%c==0&& b/c+a==res) {
                            //System.out.println(a+"+"+b+"/" + c);
                            num++;
                        }
                    }
                }
                
            }else {
                for (int i = k; i <=m; i++) {
                    Swap(array, i, k);
                    perm(array,k+1,m);
                    Swap(array, i, k);
                }
            }
            
            
        }
      
 }

 两个版本思路完全一样，不同的是版本一的代码把数组变成了字符串，再进行拆分不同数字，结果超时，充分说明了计算机对字符串的处理速度是比较慢的，所以以后在使用字符串时要注意效率和速度。

思路二

可以参考这篇博客https://blog.csdn.net/zhangpengyu321/article/details/8964803

没有用到全排列的一种暴力手段，也不会超时。