相信大家在高中數學課上都做過類似于涂色的排列組合問題，那么這個問題如何用程序語言——C語言解決呢？

一、總體思路（如果你只是需要代碼，請直接看代碼部分）

你應該重視思路，用C語言將之前數學課上的思路重現一下就好了！這些問題都可以歸類到遞歸問題，因為每次涂色的時候考慮的情況大致類似，下面提供一種思考方式：為方便起見，假設我已獲得了求解這道問題的函數solve（），只要輸入n是多少就能得到結果。

我們先不管第一格到第三格怎么涂色，我們先考慮倒數第2格，也就是第n-1格怎么涂色？

根據題意，

A、如果這個方格的顏色和第一個方格的顏色不同，那么第n個方格就只有1種選擇（因為首尾兩格也不同色），所以之前n-1個方格的涂色方法為solve（n-1），此時n個方格的涂色方法總數為solve（n-1）*1；（將第n個方格和之前的方格分成兩部分）

B、如果這個方格的顏色和第一個方格的顏色相同，那么第n個方格就有2種選擇，所以之前n-1個方格的涂色方法為solve（n-2）（為什么是n-2呢？是因為前提是?——“n-1的方格顏色已與第1個方格的顏色一致，第1個是什么顏色，第n-1方格就是什么顏色”，所以n-1方格的顏色不需要考慮，所以函數里傳的參數是n-2）。所以，在本情況下，n個方格的涂色方法總數為2*solve（n-2）。

上述的A、B是思考方式上的分類，說白了就是初中數學（中考最后一題）中要掌握的分類討論思想---“要想解對題，此題的所有情況都要列出”，而不是我們C語言中，不是if就是else的互斥情況。

綜上，解決涂色問題的表達式是：方法總數=solve（n-1）*1+2*solve（n-2）；說到這，你也許就覺得懂了，但是你忘了，我們的這個函數是假設出來的，還沒有實現呢！別著急，請看第二部分，實現過程。

二、實現過程（“如果你不思考的Copy，你將永遠是layman！”）

我們可以發現，當n<=3時，上述的思路行不通，所以可以先用遞推式來模擬一下簡單的涂色，n=1、n=2、n=3的情況。

發現：A:n=1時，涂色方法總數=3；//根據高中數學的排列組合得來的，下同

? ? ? ? ? ?B:n=2時，涂色方法總數=6（3*2）

? ? ? ? ? ? ? ?n=3時，涂色方法總數=6（3*2*1）

? ? ? ? ? ?C:n>=4時，涂色方法總數=solve（n-1）*1+2*solve（n-2）

根據上述A、B、C三種情況，我們寫下如下的代碼：這里用long是為了范圍更大，因為要大數輸出！

#include <iostream>
#include <cmath>
using namespace std;
long long solve(int n) //用long long定義，整形范圍更大。
{long long a[3]= {0};a[0]=3;//根據之前高中數學所學內容得出當n=1時，方法數為3；a[1]=6;//與上同理a[2]=6;//與上同理if(n==1)return 3;else if(n==2||n==3)return 6;elsereturn solve(n-1)*1+2*solve(n-2);
}
int main()
{int n;cout << "請輸入方格的個數：" << endl;while (cin >> n){//輸入方格數if (n == 0){cout << "輸入有誤！請重新輸入方個個數：" << endl;continue;}cout << "對應的涂色方法為：" << endl;cout << solve(n) << endl;cout << "涂色已完成" << endl;cout << "請輸入下一方格的個數：（無其它輸入請用EOF結束程序）" << endl;}return 0;
}