[剣指Offer]3.長方形のオーバーライド
タイトルの説明:
2*1の小さな矩形で横になったり、縦になったりして、より大きな矩形を覆うことができます.すみません、n個の2*1の小さい矩形で重ならずに1個の2*nの大きい矩形を覆って、全部で何種類の方法がありますか?
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は、nが偶数である整数n(1<=n<=70)を含む.
出力:
各テストケースに対応し、
出力はn個の2*1の小さな矩形で1個の2*nの大きな矩形を重ならずに覆い、合計である方法数である.
サンプル入力:
サンプル出力:
コード#コード#
2*1の小さな矩形で横になったり、縦になったりして、より大きな矩形を覆うことができます.すみません、n個の2*1の小さい矩形で重ならずに1個の2*nの大きい矩形を覆って、全部で何種類の方法がありますか?
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は、nが偶数である整数n(1<=n<=70)を含む.
出力:
各テストケースに対応し、
出力はn個の2*1の小さな矩形で1個の2*nの大きな矩形を重ならずに覆い、合計である方法数である.
サンプル入力:
4
サンプル出力:
5
/*********************************
* :2013-11-15
* :SJF0115
* : 1390:
* :http://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
",Fibonacci(n));
}
return 0;
}
コード#コード#
/*---------------------------------------
* :2015-07-19
* :SJF0115
* : 3.
* :http://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;
}