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

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

題目標題：第39級臺階

小明剛剛看完電影《第39級臺階》，離開電影院的時候，他數了數禮堂前的臺階數，恰好是39級，站在臺階前，他突然又想到一個問題：

如果我每一步只能邁上一個或兩個臺階，先邁左腳，然后左右交替，最后一步是邁右腳，也就是說一共要走偶數步，那么上完39級臺階，有多少種不同的上法呢？

請你利用計算機的優勢，幫助小明尋找答案，

要求提交的是一個整數

注意：不要提交解答程序，或其他的輔助說明文字

解題思路：

本題采用遞回的方法求解，其思想是和斐波那契數列是一樣的，只不過是斐波那契數列的逆向運用，

我們每一步都有兩種走法，即走一個臺階或兩個臺階，這樣我們剩下的臺階數就減少1個或者減少2個，同時我們的步數增加1，

所以我們只需要判斷剩下的臺階數是不是0，如果剩下的臺階數是0，則說明已經上到頂層，這個時候再判斷步數是否為偶數步即可，如果符合要求，記錄方法數的變數加1.

答案原始碼：

package 一三年省賽真題;

public class Year2013_t4 {

	public static void main(String[] args) {
		f(39,0);
		System.out.println("方法有：" + answers);
	}
	
	static int answers = 0;		//定義符合要求的方法個數
	
	/**
	 * @param n 剩余的臺階數
	 * @param step 已經走過的步數
	 * */
	public static void f(int n,int step) {
		if (n<0) {
			return;
		}
		//如果剩余的臺階數為0說明已經走完，并且步數為偶數時，符合要求，
		if (n==0&&step%2==0) {
			answers++;	//方法加1
			return;
		}
		f(n-1, step+1);	//下一步是一個臺階
		f(n-2, step+1);	//下一步是兩個臺階
	}

}