又涉及到遞歸問題，這道題的大致內(nèi)容是這樣的：

（請用遞推方式求解）對于一個2行N列的走道。現(xiàn)在用1*2,2*2的磚去鋪滿。問有多少種不同的方式。下圖是一個2行17列的走道的某種鋪法。

? ? 提示：觀察前n個結(jié)果，可以得到遞推式子；如果N很大，需要高精度計算。

其實這道題，與之前的方格涂色問題很像，說它像不僅因為在思考方式上很像，在最后的代碼上也很想像，聽我一一道來。

題目提示，先觀察前n個結(jié)果得到遞推式。那我們就把前n個結(jié)果列出來。在列的同時，就有一種這樣的感覺——就像是在高中化學(xué)中寫同分異構(gòu)式，“有序思考”。在這里我就不展示我在草稿紙上列舉的了直接說思想。

一、主要思想

和講解方格涂色問題一樣，我先來講一下我的思路：

每次鋪磚時考慮的情況大致類似，所以可以用遞歸求解。根據(jù)最后剩余的列數(shù)，我們將本問題分成兩種情況：

A：最后剩余一列，那么假設(shè)把這列去掉后，其鋪磚情況與n-1時的情況一樣，而加上后，也只有一種情況所以方法數(shù)位pave（n-1）

B：最后剩余兩列，那么把這兩列先去掉后和n-2的情況一樣，加上這兩列后一共有三種情況：1*2豎著放2列，1*2橫著放，2*2直接填滿。因為1*2豎著放和A情況重復(fù)，所以方法數(shù)為pave（n-2）*2

綜上：方法總數(shù)=pave（n-1）+2*pave（n-2）

二、具體實現(xiàn)

思路有了，但是其中的pave（）函數(shù)還沒有，這就需要我們動手來操作了。以下是具體實現(xiàn)的代碼，如果看過我之前那篇博文的同學(xué)可能就會知道，這不是一樣的問題嘛！對的，代碼幾乎一樣。

#include<iostream> using namespace std; long long pave(int n) {long long c[3] = { 0 };//保存不使用2*2磚的方法次數(shù)c[0] = 1;//由數(shù)學(xué)邏輯推出c[1] = 3;//同上c[2] = 5;//同上if (n == 1)return 1;else if (n == 2)return 3;else if (n == 3)return 5;elsereturn pave(n - 1) + 2 * pave(n - 2);//用遞歸求解 } int main() {int n;cout << "請輸入走道的列數(shù)N" << endl;while (cin >> n){if (n == 0){cout << "輸入有誤，請重新輸入！" << endl;continue;}cout << "對應(yīng)的鋪法有:" << endl;cout << pave(n) << endl;cout << "鋪磚已完成" << endl;cout << "請輸入下一走道的列數(shù):（無其他輸入請按EOF結(jié)束）" << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的C语言（CED）对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式（递归求解）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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