【每日蓝桥】17、一三年省赛Java组真题“带分数”

你好呀，我是灰小猿，一个超会写bug的程序猿！

欢迎大家关注我的专栏“每日蓝桥”，该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题，解析其中存在的算法思想、数据结构等内容，帮助大家学习到更多的知识和技术！

标题：带分数

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

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

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

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

题目要求：

从标准输入读入一个正整数N（N<1000*1000）

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

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

例如：

用户输入：

100

程序输出：

11

再例如：

用户输入：

105

程序输出：

6

 

资源约定：

峰值内存消耗（含虚拟机）< 64M

CPU消耗 < 3000ms

请严格按要求输出，不要画蛇添足的打印类似“请您输入...”的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意：不要使用package语句，不要使用jdk1.6及以上的版本特性

注意：主类的名称必须是Main 否则按无效代码处理。

解题思路：

求解本题的关键就在于对本题目的理解，和使用递归加回溯实现数组的全排列，我们可以把这道题看成是对1~9这九个数的全排列，然后对于每一种可能性，将该可能性的数组分割成三份，也就是形成上题中的三个数，然后将符合要求的分割一一枚举出来即可。

答案源码：

   

    

     

      

     
     

      

       package 一三年省赛真题;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       import java.util.Scanner;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       public 
       class Year2013_Bt9 {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       static 
       int N;
      
     
    

     

      

     
     

      
	
       static 
       int answer;
      
     
    

     

      

     
     

      
	
       public static void main(String[] args) {
      
     
    

     

      

     
     

      

       		Scanner scanner = 
       new Scanner(System.in);
      
     
    

     

      

     
     

      

       		N = scanner.nextInt();
      
     
    

     

      

     
     

      
		
       int[] arr = {
       1,
       2,
       3,
       4,
       5,
       6,
       7,
       8,
       9};
      
     
    

     

      

     
     

      

       // int[] arr = {1,2,3};
      
     
    

     

      

     
     

      

       		f(arr,
       0);
      
     
    

     

      

     
     

      

       		System.out.println(answer);
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       //排列组合，确定第K位
      
     
    

     

      

     
     

      
	
       private static void f(int[] arr, int k) {
      
     
    

     

      

     
     

      
		
       if (k == arr.length) {
      
     
    

     

      

     
     

      

       			check(arr);
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
      
     
    

     

      

     
     

      
		
       for (
       int i = k; i < arr.length; i++) {
      
     
    

     

      

     
     

      
			
       int t = arr[k];
      
     
    

     

      

     
     

      

       			arr[k] = arr[i];
      
     
    

     

      

     
     

      

       			arr[i] = t;
      
     
    

     

      

     
     

      
			
      
     
    

     

      

     
     

      

       			f(arr, k+
       1);
      
     
    

     

      

     
     

      
			
      
     
    

     

      

     
     

      

       			t = arr[k];
      
     
    

     

      

     
     

      

       			arr[k] = arr[i];
      
     
    

     

      

     
     

      

       			arr[i] = t;
      
     
    

     

      

     
     

      

       		}	
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
	
      
     
    

     

      

     
     

      
	
       /**
      
     
    

     

      

     
     

      

        * 检查组合后的数组是否符合可以组成带分数
      
     
    

     

      

     
     

      

        * */
      
     
    

     

      

     
     

      
	
       private static void check(int[] arr) {
      
     
    

     

      

     
     

      
		
       for (
       int i = 
       1; i <= 
       7; i++) {
      
     
    

     

      

     
     

      
			
       int num1 = toInt(arr, 
       0, i);	
       //获得第一个数字
      
     
    

     

      

     
     

      
			
       if (num1>=N) {
      
     
    

     

      

     
     

      
				
       break;
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      
			
       /**
      
     
    

     

      

     
     

      

        * 从之后的数组中选取出组成第二个数的元素,
      
     
    

     

      

     
     

      

        * 起始元素的下标是i
      
     
    

     

      

     
     

      

        * 取出的元素个数是j
      
     
    

     

      

     
     

      

        */
      
     
    

     

      

     
     

      
			
       for (
       int j = 
       1; j <= 
       9-i-
       1; j++) {
      
     
    

     

      

     
     

      
				
       int num2 = toInt(arr, i, j);
      
     
    

     

      

     
     

      
				
       int num3 = toInt(arr, i+j, 
       9-i-j);
      
     
    

     

      

     
     

      
				
       //当符合题目中的带分数要求，且最后的除数是正好除尽时，种数加1
      
     
    

     

      

     
     

      
				
       if ((num1 + num2 / num3)==N&&num2%num3==
       0) {
      
     
    

     

      

     
     

      

       					answer++;
      
     
    

     

      

     
     

      

       				}
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       /**
      
     
    

     

      

     
     

      

        * 将数组元素组合成一个整数
      
     
    

     

      

     
     

      

        * @param arr 待组合的数组
      
     
    

     

      

     
     

      

        * @param pos 起始下标
      
     
    

     

      

     
     

      

        * @param len 组合的位数
      
     
    

     

      

     
     

      

        * @return 组合结果
      
     
    

     

      

     
     

      

        * */
      
     
    

     

      

     
     

      
	
       private static int toInt(int[] arr,int pos,int len) {
      
     
    

     

      

     
     

      
		
       int ans = 
       0;
      
     
    

     

      

     
     

      
		
       int t = 
       1;
      
     
    

     

      

     
     

      
		
       for (
       int i = pos+len-
       1; i >=pos; i--) {
      
     
    

     

      

     
     

      

       			ans+=arr[i]*t;
      
     
    

     

      

     
     

      

       			t*=
       10;
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
       return ans;
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
	
      
     
    

     

      

     
     

      

       }
      
     
   

 

输出样例：

其中有不足或者改进的地方，还希望小伙伴留言提出，一起学习！

感兴趣的小伙伴可以关注专栏！

灰小猿陪你一起进步！