[数据结构与算法]2013-java-A-省赛-8-带分数

2013-java-A-省赛-8-带分数

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

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

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

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

题目要求：
　　从标准输入读入一个正整数N (N<1000*1000)
　　程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
　　注意：不要求输出每个表示，只统计有多少表示法！

例如：
　　用户输入：
　　100
　　程序输出：
　　11
　　再例如：
　　用户输入：
　　105
　　程序输出：
　　6

资源约定：
　　峰值内存消耗 < 64M
　　CPU消耗 < 3000ms

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

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

注意: main函数需要返回0
　　注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
　　注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。
代码

第一次剪枝的边界错了，导致有一个样例没过

import java.util.Scanner;

public class Main {
	static int ans= 0;
	static int n;
	static char[] a= {'1','2','3','4','5','6','7','8','9'};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt();
		calc(0);
		System.out.println(ans);
	}
	private static void calc(int k) {
		if(k==a.length) {
			if(yes()) {
				ans++;
			}
			return;
		}
		for (int i = k; i < a.length; i++) {
			char t=a[k];a[k]=a[i];a[i]=t;
			calc(k+1);
			t=a[k];a[k]=a[i];a[i]=t;
		}
	}
	private static boolean yes() {
		int x,y,z;
		for (int i = 0; i < 7; i++) {
			x=Integer.parseInt(String.valueOf(a, 0, i+1));
			if(x>=n)continue;
			for (int j = (a.length-i-1)/2+i; j < 8; j++) {
				y=Integer.parseInt(String.valueOf(a, i+1, j-i));
				z=Integer.parseInt(String.valueOf(a, j+1, a.length-j-1));
				if(y<z || y%z!=0) continue;
				if((x+y/z)==n)return true;
			}
		}
		return false;
	}
}