历届试题带分数

Bertha 。 2022-03-06 17:42 282阅读 0赞

### 问题描述 ###

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 Main {
    	static int[] arr = {1,2,3,4,5,6,7,8,9};
    	static int N;
    	static int ans;
    	public static void arrange (int[] arr, int k) {
    		if(k==9) {
    			check(arr);
    		}
    		for (int i=k; i<arr.length; i++) {
    			int t = arr[k];
    			arr[k] = arr[i];
    			arr[i] = t;
    			arrange(arr, k+1);
    			t = arr[k];
    			arr[k] = arr[i];
    			arr[i] = t;
    		}
    	}
    
    	private static int check(int[] arr) {
    		for(int i=1; i<8; i++) {
    			int num1 = toInt(arr, 0, i);
    			if(num1>N)	continue;
    			for(int j=1; j<9-i; j++) {
    				int num2 = toInt(arr, i, j);
    				int num3 = toInt(arr, i+j, 9-i-j);
    				if(num2%num3==0&&N==num1+num2/num3) {
    					ans++;
    				}
    			}
    		}
    		return ans;
    	}
    
    	private static int toInt(int[] arr, int start, int len) {
    		int t=1;
    		int sum=0;
    		for(int i=start+len-1; i>=start; i--) {
    			sum += arr[i]*t;
    			t *= 10;
    		}
    		return sum;
    	}
    
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		while(input.hasNext()) {
    			N = input.nextInt();
    			ans = 0;
    			arrange(arr, 0);
    			System.out.println(ans);
    		}
    		input.close();
    	}
    }