问题描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
1 import java.util.Scanner; 2 import java.util.concurrent.atomic.LongAccumulator; 3 4 public class Main{ 5 public static int num=0; 6 public static int[]array=new int[10]; 7 static int res; 8 static int length=0; 9 public static void main(String[] args){ 10 Scanner scanner=new Scanner(System.in); 11 String th=scanner.next(); 12 res=Integer.parseInt(th); 13 length=th.length(); 14 for (int i = 1; i <=array.length-1; i++) { 15 array[i]=i; 16 } 17 long a=System.currentTimeMillis(); 18 perm(array,1, 9); 19 System.out.println(num); 20 long b=System.currentTimeMillis(); 21 // System.out.println(b-a); 22 23 } 24 public static void Swap(int str[], int a, int b) 25 { 26 int temp = str[a]; 27 str[a] = str[b]; 28 str[b] = temp; 29 } 30 public static void perm(int array[],int k,int m) 31 { 32 if(k==m) { 33 String string=""; 34 for (int i = 1; i <=array.length-1; i++) { 35 string+=array[i]; 36 } 37 String a=""; 38 String b=""; 39 String c=""; 40 //int num1=Integer.parseInt(string); 41 for (int i = 1; i <string.length()-1; i++) { 42 a=string.substring(0, i); 43 int a1=Integer.parseInt(a); 44 if(a1>res) break; 45 for (int j = i+(9-i)/2; j < string.length(); j++) { 46 47 b=string.substring(i,j); 48 c=string.substring(j,string.length()); 49 50 51 52 int a2=Integer.parseInt(b); 53 int a3=Integer.parseInt(c); 54 if(a3>a2) continue; 55 if(a2%a3==0) { 56 if(a1+a2/a3==res) { 57 num++; 58 } 59 } 60 } 61 } 62 return; 63 64 }else { 65 for (int i = k; i <=m; i++) { 66 Swap(array, i, k); 67 perm(array,k+1,m); 68 Swap(array, i, k); 69 } 70 } 71 72 73 } 74 75 }
版本二（正确）
1 import java.util.Scanner; 2 import java.util.concurrent.atomic.LongAccumulator; 3 public class Main{ 4 public static int num=0; 5 public static int[]array=new int[10]; 6 static int res; 7 static int length=0; 8 public static void main(String[] args){ 9 Scanner scanner=new Scanner(System.in); 10 String th=scanner.next(); 11 long a=System.currentTimeMillis(); 12 res=Integer.parseInt(th); 13 length=th.length(); 14 for (int i = 1; i <=array.length-1; i++) { 15 array[i]=i; 16 } 17 18 perm(array,1, 9); 19 System.out.println(num); 20 long b=System.currentTimeMillis(); 21 // System.out.println(b-a);//显示运行时间，单位ms 22 23 } 24 public static void Swap(int str[], int a, int b) 25 { 26 int temp = str[a]; 27 str[a] = str[b]; 28 str[b] = temp; 29 } 30 public static int sumNUm(int array[],int start,int end) 31 { 32 int sum=0; 33 for (int i = start; i <=end; i++) { 34 sum=sum*10+array[i]; 35 36 } 37 return sum; 38 } 39 public static void perm(int array[],int k,int m) 40 { 41 if(k==m) { 42 for (int i = 1; i <array.length-2; i++) { 43 int a=sumNUm(array, 1, i); 44 if(a>res) break; 45 for (int j = i+(9-i)/2; j <array.length-1; j++) { 46 int b=sumNUm(array, i+1, j); 47 int c=sumNUm(array, j+1, m); 48 if(c>b) continue; 49 if(b%c==0&& b/c+a==res) { 50 //System.out.println(a+"+"+b+"/" + c); 51 num++; 52 } 53 } 54 } 55 56 }else { 57 for (int i = k; i <=m; i++) { 58 Swap(array, i, k); 59 perm(array,k+1,m); 60 Swap(array, i, k); 61 } 62 } 63 64 65 } 66 67 }
两个版本思路完全一样，不同的是版本一的代码把数组变成了字符串，再进行拆分不同数字，结果超时，充分说明了计算机对字符串的处理速度是比较慢的，所以以后在使用字符串时要注意效率和速度。
思路二
可以参考这篇博客https://blog.csdn.net/zhangpengyu321/article/details/8964803
没有用到全排列的一种暴力手段，也不会超时。
原文：https://www.cnblogs.com/henuliulei/p/10431319.html