试题

admin管理员组

文章数量:1122853

试题

问题描述
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/CScanner 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++){/*//方法1A=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);}}*///方法2A=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);}}}
}

本文标签： 试题