<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
问题描述:有2×n的一个长方形棋盘,用一些1×2的骨牌铺满方格. 
例如:n=3时,在2×3的棋盘上用1×2的骨牌覆盖,共有3种铺法。 
问题求解:编写一个程序,试对给出的任意一个n(n&gt;0),输出铺法总数.
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
输入包括多组数据，每组数据占一行，且只有一个整数n (0&lt;=n&lt;=42),表示2*n的棋盘,当n=0时表示输入结束。
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
输出一行结果，为一个整数，表示棋盘完美覆盖方案数。
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
8 
0
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
34
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
显然,这道题可以使用某种神奇的数学规律来求解 
先找下规律
<table>
<thead>
<tr>
<th style="text-align:center">n</th>
<th style="text-align:center">1</th>
<th style="text-align:center">2</th>
<th style="text-align:center">3</th>
<th style="text-align:center">4</th>
<th style="text-align:center">5</th>
<th style="text-align:center">6</th>
<th style="text-align:center">7</th>
<th style="text-align:center">8</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">num</td>
<td style="text-align:center">1</td>
<td style="text-align:center">2</td>
<td style="text-align:center">3</td>
<td style="text-align:center">5</td>
<td style="text-align:center">8</td>
<td style="text-align:center">13</td>
<td style="text-align:center">21</td>
<td style="text-align:center">34</td>
</tr>
</tbody>
</table>
就是斐波那契数列 
<code>f[n] = f[n-1] + f[n-2]</code>
理解下原理 
最后的方块只有两种情况:
<ul>
<li>竖着放一列</li>
<li>横着两个放两列</li>
</ul>
分别对应
<ul>
<li>最后两列一个竖着放,考虑前面 <code>n-1</code> 列的情况( <code>f[n-1]</code> )</li>
<li>最后两列全部竖着放,考虑前面 <code>n-2</code> 列的情况( <code>f[n-2]</code> )</li>
</ul>
因此,将两种情况加起来就是答案
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
using namespace std;
 
const int maxn = 45;
int f[maxn] = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
void F(int i=2) {
 if(i == maxn)
 return;
 f[i] = f[i - 1] + f[i - 2];
 F(i + 1);
};
 
bool Do() {
 int n;
 scanf(&#34;%d&#34;,&amp;n);
 if(n == 0)
 return false;
 
 printf(&#34;%d\n&#34;,f[n]);
 
 return true;
}
 
int main() {
 while(Do());
 return 0;
}
</pre>

AOJ 785.棋盘完美覆盖