题目描述
100 可以表示为带分数的形式:100=3+69258/714
还可以表示为:100=82+3546/197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)
解题思路
简单的dfs全排列,加上两层暴力枚举
怕时间超过 要有一个简单的剪枝
时间复杂度
大概 时间过得了 我的过了
java代码
import java.util.Scanner;
/**
*
*/
public class Main {
static int N;
static int ans;
/**
* @param args
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int[] arr = {1,2,3,4,5,6,7,8,9};
f(arr, 0);
System.out.println(ans);
}
/**
* @param arr
* @param k
* 全排列
*/
private static void f(int[] arr, int k) {
if (k == 9) {
check(arr);
return ;
}
int temp;
for (int i = k; i < arr.length; i++) {
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
f(arr, k+1);
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
}
/**
* @param arr
* 插入+ 和 /号的
*/
private static void check(int[] arr) {
for (int i = 1; i <= 7; i++) {
int num = toInt(arr,0,i);
if (num >= N)continue;
for (int j = 1; j <= 8-i; j++) {
int num1 = toInt(arr, i, j);
int num2 = toInt(arr, j + i, 9-i-j);
if (num1 % num2 == 0 && num + num1/num2 == N) {
ans++;
}
}
}
}
/**
* @param arr
* @param pos 当前位置
* @param len 数符长度
* @return final num
*/
private static int toInt(int[] arr, int pos, int len) {
int rs = 0;
int t = 1;
for (int i = pos+len-1; i >= pos; i--) {
rs += arr[i] * t;
t *= 10;
}
return rs;
}
}