哈理工軟體學院第三屆ACM程式設計決賽-高年級組 D---Tu Hao's Problem

https://www.nowcoder.com/acm/contest/21/D

題意：遞推

每一步隻能邁1或2個階梯，要求是先邁左腳，然後左右交替，最後一步是邁右腳，也就是說一共要走偶數步。那麼，上完N（0<=N<=39）級台階，計算方法總數。

Time Limit Exceeded

#include<stdio.h>
int fun(int n,int flag)
{
	if(n==1)//若剩餘一階台階
	{
		if(flag==1)//若最後一步是右腳 則方法數+1
		{
			return 1;
		}
		else//若是左腳 則方法數+0
		{
			return 0;
		}
	}
	else if(n==2)//若剩餘兩階台階，都可以保證最後一步邁右腳 方法數+1
	{
		return 1;
	}
	return (fun(n-1,!flag)+fun(n-2,!flag));//輪流左右交替
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        //fun(台階數量n,左腳為0[右腳為1])
        printf("%d\n",fun(n,0));//先邁左腳
    }
	return 0;
}           

思路：由于N的範圍比較小，可通過枚舉的方式解決逾時問題。

可以通過上述程式事先計算按照要求上完N（0<=N<=39）級台階的方法總數，存入數組中。

AC代碼

#include<stdio.h>
int main()
{
    int t,n;
    int result[40]={0,0,1,2,2,4,7,10,17,28,44,72,117,188,305,494,798,1292,2091,3382,5473,8856,14328,23184,37513,60696,98209,158906,257114,416020,673135,1089154,1762289,2851444,4613732,7465176,12078909,19544084,31622993,51167078};
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",result[n]);
    }
	return 0;
}