你好呀，我是灰小猿，一個超會寫bug的程式猿！

歡迎大家關注我的專欄“每日藍橋”，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，決議其中存在的演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！

標題：帶分數

100可以表示為帶分數的形式：100=3 + 69258 / 714

還可以表示為；100 = 82 + 3546 / 197

注意特征：帶分數中，數字1~9分別出現且只出現1次（不包含0）

類似這樣的帶分數，100有11種表示法

題目要求：

從標準輸入讀入一個正整數N（N<1000*1000）

程式輸出該數字用數碼1~9不重復不遺漏的組成帶分數表示的全部種數，

注意：不要求輸出每個表示，只統計有多少表示法，

例如：

用戶輸入：

100

程式輸出：

11

再例如：

用戶輸入：

105

程式輸出：

6

資源約定：

峰值記憶體消耗（含虛擬機）< 64M

CPU消耗 < 3000ms

請嚴格按要求輸出，不要畫蛇添足的列印類似“請您輸入...”的多余內容，

所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼，

注意：不要使用package陳述句，不要使用jdk1.6及以上的版本特性

注意：主類的名稱必須是Main 否則按無效代碼處理，

解題思路：

求解本題的關鍵就在于對本題目的理解，和使用遞回加回溯實作陣列的全排列，我們可以把這道題看成是對1~9這九個數的全排列，然后對于每一種可能性，將該可能性的陣列分割成三份，也就是形成上題中的三個數，然后將符合要求的分割一一列舉出來即可，

答案原始碼：

package 一三年省賽真題;

import java.util.Scanner;

public class Year2013_Bt9 {

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

	//排列組合，確定第K位
	private static void f(int[] arr, int k) {
		if (k == arr.length) {
			check(arr);
		}
		
		for (int i = k; i < arr.length; i++) {
			int t = arr[k];
			arr[k] = arr[i];
			arr[i] = t;
			
			f(arr, k+1);
			
			t = arr[k];
			arr[k] = arr[i];
			arr[i] = t;
		}	
	}
	
	/**
	 * 檢查組合后的陣列是否符合可以組成帶分數
	 * */
	private static void check(int[] arr) {
		for (int i = 1; i <= 7; i++) {
			int num1 = toInt(arr, 0, i);	//獲得第一個數字
			if (num1>=N) {
				break;
			}
			/**
			 * 從之后的陣列中選取出組成第二個數的元素,
			 * 起始元素的下標是i
			 * 取出的元素個數是j
			*/
			for (int j = 1; j <= 9-i-1; j++) {
				int num2 = toInt(arr, i, j);
				int num3 = toInt(arr, i+j, 9-i-j);
				//當符合題目中的帶分數要求，且最后的除數是正好除盡時，種數加1
				if ((num1 + num2 / num3)==N&&num2%num3==0) {
					answer++;
				}
			}
		}
		
	}

	/**
	 * 將陣列元素組合成一個整數
	 * @param arr 待組合的陣列
	 * @param pos 起始下標
	 * @param len 組合的位數
	 * @return 組合結果
	 * */
	private static int toInt(int[] arr,int pos,int len) {
		int ans = 0;
		int t = 1;
		for (int i = pos+len-1; i >=pos; i--) {
			ans+=arr[i]*t;
			t*=10;
		}
		return ans;
	}
	
}