#UVa:900-Brick Wall Patterns

灆洢 2012-01-19 16:13:58

這題的規律其實就是費氏數列。

令牆壁的長度為n,n若等於1,就是1塊;n若等於2,就是2塊;n若大於2,則n長度的牆壁可由n-1長度的牆壁加一塊垂直的方塊以及由n-2長度的牆壁加兩塊平行的方塊而得到。

C++(0.008)

/*******************************************************/
/* UVa 900 Brick Wall Patterns                         */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/01/19                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int main(){
  int dp[55] = {0,1,2};
  int n;
  for( int i = 3 ; i <= 50 ; i++ )
    dp[i] = dp[i-1]+dp[i-2];
  while( scanf( "%d", &n ) != EOF && n )
    printf( "%d\n", dp[n] );
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料