?問題：現有 n 塊“多米諾骨牌” s1, s2, · · · , sn 水平放成一排，每塊骨 牌 si 包含左右兩個部分，每個部分賦予一個非負整數值，骨牌可做 180 度旋轉，使得原來在左邊的值變到右邊，而原來 在右邊的值移到左邊，假設不論 si 如何旋轉，L[i] 總是存儲 si 左邊的值，R[i] 總是存儲 si 右邊的值，status[i] 用于存儲 si 的狀態：當 L[i] ≤ R[i] 時記為 0，否 則記為 1，試采用分治法設計算法

? ? 求 =R[i]·L[i+ 1] 的最大值，以及當取 得最大值時每個骨牌的狀態。

?

條件分析： 1：每塊骨牌有左右兩部分都為非負整數值 2：左右部分的值可調換 3：調換后，存儲狀態status改變 4：前一骨牌的右部分乘以后一骨牌的左部分（第一個的左部分和最后一個的右部分不參與計算） 4：用分治法,即將大問題轉換為小問題 關鍵代碼： Status Recursion(int n ,Data L)//遞歸操作 {if (n == 0)return ERROR;Recursion(n-1, L);int _left = Sum.Left;//記錄第1個骨牌到第n個骨牌的左部分為止的最大值if (L[n].left * L[n - 1].left+Sum.Right < L[n].left * L[n - 1].right+Sum.Left)//記錄從第1個骨牌到第n+1個骨牌的左部分為止的最大值{Sum.Left+= L[n].left * L[n - 1].right;}else{Sum.Left = L[n].left * L[n - 1].left+ Sum.Right;if (L[n-1].status[0])//由于第n個骨牌調換了位置，所以狀態要改變{L[n-1].status[0] = 0;}else{L[n-1].status[0] = 1;}}if (L[n].right * L[n - 1].left+Sum.Right < L[n].right * L[n - 1].right+ _left)//記錄從第1個骨牌到第n+1個骨牌的右部分為止的最大值{Sum.Right = L[n].right * L[n - 1].right+ _left;}else{Sum.Right = L[n].right * L[n - 1].left + Sum.Right;if (L[n-1].status[1])//由于第n個骨牌調換了位置，所以狀態要改變{L[n-1].status[1] = 0;}else{L[n-1].status[1] = 1;}}return OK; }

總體實現：

函數定義

#include<iostream> #define OK 1; #define ERROR 0; const int LENGTH =6;//骨牌的數目 typedef int Status; typedef struct _data {int left;//骨牌左邊值int right;//骨牌右邊值int status[2];//骨牌的狀態 }Data[LENGTH]; typedef struct _Sum {int Left;int Right; }_Sum; static _Sum Sum = {0,0}; static int Num = LENGTH; void Init(Data & L)//初始化骨牌 {int i;for (i = 0; i < LENGTH; i++){scanf_s("%d", &L[i].left);scanf_s("%d", &L[i].right);if (L[i].left <= L[i].right)//初始時將骨牌狀態確定{L[i].status[0] = 0;L[i].status[1] = 0;}else{L[i].status[0] = 1;L[i].status[1] = 1;}} }Status Recursion(int n ,Data L)//遞歸操作 {if (n == 0)return ERROR;Recursion(n-1, L);int _left = Sum.Left;//記錄第1個骨牌到第n個骨牌的左部分為止的最大值if (L[n].left * L[n - 1].left+Sum.Right < L[n].left * L[n - 1].right+Sum.Left)//記錄從第1個骨牌到第n+1個骨牌的左部分為止的最大值{Sum.Left+= L[n].left * L[n - 1].right;}else{Sum.Left = L[n].left * L[n - 1].left+ Sum.Right;if (L[n-1].status[0])//由于第n個骨牌調換了位置，所以狀態要改變{L[n-1].status[0] = 0;}else{L[n-1].status[0] = 1;}}if (L[n].right * L[n - 1].left+Sum.Right < L[n].right * L[n - 1].right+ _left)//記錄從第1個骨牌到第n+1個骨牌的右部分為止的最大值{Sum.Right = L[n].right * L[n - 1].right+ _left;}else{Sum.Right = L[n].right * L[n - 1].left + Sum.Right;if (L[n-1].status[1])//由于第n個骨牌調換了位置，所以狀態要改變{L[n-1].status[1] = 0;}else{L[n-1].status[1] = 1;}}return OK; }

主函數：

int main() { int i;Data _data;Init(_data);//初始化Recursion(Num-1, _data);//遞歸操作if (Sum.Left > Sum.Right){printf("%d ", Sum.Left);for (i = 0; i < Num; i++){printf("%d ", _data[i].status[0]);}}else//最后一個骨牌調換位置，狀態改變{printf("%d ", Sum.Right);if (_data[Num-1].status[1]){_data[Num - 1].status[1] = 0;}else{_data[Num - 1].status[1] = 1;}for (i = 0; i < Num; i++){printf("%d ", _data[i].status[1]);}}return 0; }

總結

以上是生活随笔為你收集整理的C/C++ 用递归（分治法）解决多米诺骨牌问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。