蓝桥杯历届试题 PREV-3 带分数

快来打我* 2023-10-06 09:38 11阅读 0赞

历届试题 带分数

时间限制：1.0s 内存限制：256.0MB

问题描述

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

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

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

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

输入格式

从标准输入读入一个正整数N (N<1000\*1000)

输出格式

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

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

样例输入1

100

样例输出1

样例输入2

105

样例输出2

示例代码：

1 import java.io.BufferedReader;
     2 import java.io.IOException;
     3 import java.io.InputStreamReader;
     4 
     5 public class Main {
     6     static boolean[] sign;
     7     static int[] num;
     8     static int N;
     9     static int ans;
    10     
    11     public static void main(String[] args) throws NumberFormatException, IOException {
    12         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    13         N = Integer.parseInt(br.readLine());
    14         
    15         sign = new boolean[N];
    16         num = new int[N];
    17         
    18         dfs(0);                //深度优先搜索
    19         
    20         System.out.println(ans);
    21     }
    22 
    23     private static void dfs(int pos) {
    24         if (pos == 9) {
    25             int plus_pos = 1, div_pos = 9;        // + 和 / 位置    div_pos
    26              
    27             //   N = x + Y / Z
    28             for (plus_pos = 1; plus_pos < 9; plus_pos++) {   //加号的位置应该是从第一个数之后开始到最后一个数之前结束
    29                 int x = 0; 
    30                 for (int i = 1; i <= plus_pos; i++)
    31                     x = x * 10 + num[i];
    32                 if (x >= N)                     //若第一个数大于输入的数，不符合规则，就跳出所有循环
    33                     break;
    34                 for (div_pos = 9; div_pos > plus_pos; div_pos--) {  //除号的位置应该是从最后一个数开始，到加号位置之后结束
    35                     int y = 0, z = 0;
    36                     for (int i = plus_pos + 1; i < div_pos; i++)    // y 在加号后一个位置之后和除号前一个位置
    37                         y = y * 10 + num[i];
    38                     
    39                     for (int i = div_pos; i <= 9; i++)              // z 在除号之后
    40                         z = z * 10 + num[i];
    41                     
    42                     if (z > y )                 //若除数大于被除数，不符合规则，就跳出所有循环
    43                         break;
    44                     if ( (y % z == 0) && ( (x + y / z) == N) ) {  //若 y 能整除 z ，并且 x y z 符合表达式，则结果数+1
    45                         ans++;
    46 //                        System.out.println(N +"="+ x + "+" + y +"/" + z);
    47                     }
    48                 }
    49             }
    50             return;
    51         }
    52         //将 1 - 9 在num数组中的位置进行互换，使每个位置都出现这九个数字
    53         for (int i = 1; i < 10; i++) {
    54             if ( !sign[i] ) {
    55                 sign[i] = true;         //先将按照此顺序的放置的数每个都标记为true
    56                 num[pos + 1] = i;       //将每个数放在数组下标从 1 开始到 9 结束这9个位置
    57                 dfs(pos + 1);             //递归
    58                 sign[i] = false;        //此顺序处理完，将标记置为false，继续交换数组的位置
    59             }
    60         }
    61     }
    62 
    63 }