蓝桥杯2013年第四届真题-带分数 （Java代码）

解题思路:全排列+枚举+剪枝

注意事项:

参考代码:

import java.util.Scanner;

public class Main{
	public static int count = 0;
	public static int tempN;

	public static void perm(int[] arr, int begin, int end) {
		// 设置递归的出口,即当需要全排列的范围只有一个元素，则全排结束，此数组为全排列
		if (begin == end) {
//			StringBuffer buffer = new StringBuffer();
//			for (int i = 0; i <= end; i++) {
//				buffer.append(arr[i]);
//				// System.out.print(arr[i] + " ");
//			}
			// System.out.println(buffer);
			for (int i = 0; i <= 6; i++) {
				int num1 = toInt(arr, 0, i+1);
				//剪枝
				if (num1 >= tempN)
					continue;

				for (int j = i + 1; j <= 7; j++) {
//						for (int j2 = j+1; j2 < arr.length; j2++) {

					int num2 = toInt(arr, i+1, j+1);
					int num3 = toInt(arr, j+1, arr.length);
					//System.out.println(num1+" "+num2+" "+num3);
					if (num2%num3==0 &&  (num1 + num2 / num3) == tempN) {
						// map.put(num1+" "+num2+" "+num3, 1);
						
						// System.out.println("==="+buffer);
						count++;
					}
//						}
				}
			}

			// System.out.println();
			return;
		} else {
			// for循环将begin~end中的每一个数放到begin位置中去，并实现全排列
			for (int j = begin; j <= end; j++) {
				swap(arr, begin, j); // for循环将begin~end中的每一个数放到begin位置中去
				perm(arr, begin + 1, end); // 假设begin位置确定，那么对begin+1~end中的数组进行全排列
				swap(arr, begin, j); // 换过去后再将数组还原
			}
		}
	}
	
	public static int toInt(int[] arr,int beginIndex,int endIndex) {
		int res = 0;
		for (int i = beginIndex; i < endIndex; i++) {
			res = res*10+arr[i];
		}
		return res;
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);		
		int N = in.nextInt();
		tempN = N;
		int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		
		perm(arr, 0, arr.length - 1);
		System.out.println(count);
	}
}