试题_(带分数)03

2019-11-08 00:52:23

字体：大中小

来源：转载

供稿：网友

问题描述 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

import java.util.Scanner; public class ys_09 { public static void main(String[] args) { //将等式定义为：N=A+B/C Scanner scanner=new Scanner(System.in); N=scanner.nextInt(); long start=System.currentTimeMillis(); int[] s=new int[]{1,2,3,4,5,6,7,8,9}; NLength=(N+"").length(); allRange(s, 0, s.length-1); long end=System.currentTimeMillis(); System.out.PRintln("耗时:"+(end-start)+" ms"); System.out.println("总数为:"+kinds+" 种"); } public static int N; public static int NLength;//N数字的长度 public static int kinds; public static void process(int[] s){ String str=""; for(int i=0;i<9;i++) str+=s[i]; int A,B,C,NMA,BC,BMCL,BLastNumber; //A的位数 for(int i=1;i<=NLength;i++){ /* //方法1 A=Integer.valueOf(str.substring(0, i)); NMA=N-A;//N减去A的值 if(NMA<=0)return; BC=9-i;//B和C还有多少为可用 BMCL=(NMA+"").length();//B/C的长度 //确定的B的结束为止 for(int j=i+BC/2;j<=8;j++){//可以优化这里 B=Integer.valueOf(str.substring(i,j)); C=Integer.valueOf(str.substring(j,9)); if(B%C==0&&B/C==NMA){ kinds++; System.out.println(N+"="+A+"+"+B+"/"+C); } } */ //方法2 A=Integer.valueOf(str.substring(0, i)); NMA=N-A; if(NMA<=0)return; BC=9-i;//B和C总共多少位 BLastNumber=(NMA*s[8])%10;//B最后的数字 //j为B最后一个数字的位置 //B最少占有B和C全部数字的一半，否则B/C不可能为整数 for(int j=i+BC/2-1;j<=7;j++){ //找到符合的位置 if(s[j]==BLastNumber){ B=Integer.valueOf(str.substring(i,j+1)); C=Integer.valueOf(str.substring(j+1,9)); if(B%C==0&&B/C==NMA){ kinds++; System.out.println(N+"="+A+"+"+B+"/"+C); } //符合要求的位置只可能出现一次 break; } } } } public static void swap(int[] s,int a,int b){ if(a==b)return; int tmp=s[a]; s[a]=s[b]; s[b]=tmp; } //全排列 public static void allRange(int[] s,int k,int m){ if(k==m){ process(s); return; } else{ for(int i=k;i<=m;i++){ swap(s,k,i); allRange(s, k+1, m); swap(s,k,i); } } } } import java.util.Scanner;public class ys_09 { public static void main(String[] args) { //将等式定义为：N=A+B/C Scanner scanner=new Scanner(System.in); N=scanner.nextInt(); long start=System.currentTimeMillis(); int[] s=new int[]{1,2,3,4,5,6,7,8,9}; NLength=(N+"").length(); allRange(s, 0, s.length-1); long end=System.currentTimeMillis(); System.out.println("耗时:"+(end-start)+" ms"); System.out.println("总数为:"+kinds+" 种"); } public static int N; public static int NLength;//N数字的长度 public static int kinds; public static void process(int[] s){ String str=""; for(int i=0;i<9;i++) str+=s[i]; int A,B,C,NMA,BC,BMCL,BLastNumber; //A的位数 for(int i=1;i<=NLength;i++){ /* //方法1 A=Integer.valueOf(str.substring(0, i)); NMA=N-A;//N减去A的值 if(NMA<=0)return; BC=9-i;//B和C还有多少为可用 BMCL=(NMA+"").length();//B/C的长度 //确定的B的结束为止 for(int j=i+BC/2;j<=8;j++){//可以优化这里 B=Integer.valueOf(str.substring(i,j)); C=Integer.valueOf(str.substring(j,9)); if(B%C==0&&B/C==NMA){ kinds++; System.out.println(N+"="+A+"+"+B+"/"+C); } } */ //方法2 A=Integer.valueOf(str.substring(0, i)); NMA=N-A; if(NMA<=0)return; BC=9-i;//B和C总共多少位 BLastNumber=(NMA*s[8])%10;//B最后的数字 //j为B最后一个数字的位置 //B最少占有B和C全部数字的一半，否则B/C不可能为整数 for(int j=i+BC/2-1;j<=7;j++){ //找到符合的位置 if(s[j]==BLastNumber){ B=Integer.valueOf(str.substring(i,j+1)); C=Integer.valueOf(str.substring(j+1,9)); if(B%C==0&&B/C==NMA){ kinds++; System.out.println(N+"="+A+"+"+B+"/"+C); } //符合要求的位置只可能出现一次 break; } } } } public static void swap(int[] s,int a,int b){ if(a==b)return; int tmp=s[a]; s[a]=s[b]; s[b]=tmp; } //全排列 public static void allRange(int[] s,int k,int m){ if(k==m){ process(s); return; } else{ for(int i=k;i<=m;i++){ swap(s,k,i); allRange(s, k+1, m); swap(s,k,i); } } }}

上一篇：LeetCode : Fizz Buzz

下一篇：17-02-07