蓝桥杯-带分数

我会带着你远行 2023-06-23 11:52 45阅读 0赞

--------------------

title: 蓝桥杯-带分数  
date: 2019-12-18 18:15:48  
categories:

*  蓝桥杯  
    tags:
 *  蓝桥杯

--------------------

# 带分数 #

*  算法描述

问题描述

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-9这些排列组合中寻找目标的东西,记录自己路径经国就好
    
        public class prev_1209 {
        	public static int[] a = new  int [10];
        	public static int[] b = new int [10];
        	public static int count1 = 0;
        	public static int n = 105;
        	public static void main(String[] args){
        		dfs(1);
        		System.out.println(count1);
        	}
        	public static void dfs(int t){
        		if(t>9){
        			//计算num1，num2，num3是否有
        			int j,m,k,sum1 = 0,sum2 = 0,sum3 = 0,sum=0;
        			for(k=1;k<=9;k++){
        				sum = sum*10+b[k];
        				if(sum>n) break;
        			}
        			for(int i=1;i<=k;i++){
        				sum1 = sum1*10+b[i];
        				for(j=(i+10)/2+1;j<=9;j++){
        					sum2 = 0;
        					sum3 = 0;
        					for(m=i+1;m<j;m++)
        						sum2 = sum2*10+b[m];
        					for(m=j;m<=9;m++)
        						sum3 = sum3*10+b[m];
        					if(sum2%sum3!=0)
        						continue;
        					else
        						if(sum1+sum2/sum3==n) 
        							count1 = count1+1;
        				}
        			}
        		}else{
        			for(int i=1;i<=9;i++){
        				if(a[i]==0){
        					a[i] = 1;
        					b[t] = i;
        					dfs(t+1);
        					a[i] = 0;
        					b[t] = 0;
        				}
        			}
        		}
        	}
        }