671
[劍指Offer]3.矩形覆蓋
- 題目描述：
-
我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
- 輸入：
-
輸入可能包含多個測試樣例，對於每個測試案例，
輸入包括一個整數n(1<=n<=70)，其中n為偶數。
- 輸出：
-
對應每個測試案例，
輸出用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有的方法數。
- 樣例輸入：
-
4
- 樣例輸出：
-
5
/*********************************
* 日期：2013-11-15
* 作者：SJF0115
* 題號: 題目1390：矩形覆蓋
* 來源：https://ac.jobdu.com/problem.php?pid=1390
* 結果：AC
* 來源：劍指Offer
* 總結：
**********************************/
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
//F(n) = F(n-1) + F(n-2)
long long Fibonacci(int n){
int i;
long long fibonacciA = 1;
long long fibonacciB = 2;
long long fibonacciC;
if(n == 1){
return fibonacciA;
}
else if(n == 2){
return fibonacciB;
}
for(i = 3;i <= n;i++){
fibonacciC = fibonacciA + fibonacciB;
fibonacciA = fibonacciB;
fibonacciB = fibonacciC;
}
return fibonacciC;
}
int main()
{
int i,n;
while(scanf("%d",&n) != EOF){
printf("%lld\n",Fibonacci(n));
}
return 0;
}
代碼
/*---------------------------------------
* 日期：2015-07-19
* 作者：SJF0115
* 題目: 3.矩形覆蓋
* 網址：https://www.nowcoder.com/books/coding-interviews/72a5a919508a4251859fb2cfb987a0e6?rp=1
* 結果：AC
* 來源：劍指Offer
* 博客：
-----------------------------------------*/
#include <iostream>
using namespace std;
class Solution {
public:
int rectCover(int n){
if(n < 0){
return 0;
}//if
else if(n == 1 || n == 0){
return 1;
}//else
else if(n == 2){
return 2;
}//else
return rectCover(n-1) + rectCover(n-2);
}
};
int main(){
Solution s;
int number = 4;
cout<<s.rectCover(number)<<endl;
return 0;
}
最後更新：2017-04-03 14:54:03