1196：踩方格

時間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 8958 ??? 通過數(shù): 5926

【題目描述】

有一個方格矩陣，矩陣邊界在無窮遠(yuǎn)處。我們做如下假設(shè)：

a、每走一步時，只能從當(dāng)前方格移動一格，走到某個相鄰的方格上；

b、走過的格子立即塌陷無法再走第二次；

c、只能向北、東、西三個方向走；

請問：如果允許在方格矩陣上走n步，共有多少種不同的方案。2種走法只要有一步不一樣，即被認(rèn)為是不同的方案。

【輸入】

允許在方格上行走的步數(shù)n(n≤20)。

【輸出】

計算出的方案數(shù)量。

【輸入樣例】

2

【輸出樣例】

7

【分析】

? ? ? ? n=1時，可以向三個方向（從0→1，即北、西、東），步數(shù)為3，如下圖：

? ? ? ? n=2時，從藍(lán)色矩形框向外擴(kuò)展，不能走回頭路，即不能走回到0，如下圖所示：

? ? ? ? 所以n=2時，步數(shù)為7，同理，n=3時，步數(shù)為17，n=4時，步數(shù)為41。

【參考代碼】

#include <stdio.h> #define N 25 int a[N]; int main() {int i,n;scanf("%d",&n);a[1]=3; //邊界 a[2]=7;for(i=3;i<=n;i++)a[i]=2*a[i-1]+a[i-2]; //遞推公式 printf("%d\n",a[n]);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1196

?

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1196：踩方格）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。