題目：有這樣一個包含9個圓圈的數陣，如下圖所示：

?

外層8個圈，內層一個圈；將1~8這8個數隨機的填寫到該數陣的外層的圓圈中，只剩下中間的一個空圓圈。規定每個數字只能按照數陣中的直線從一個圓圈移動到另一個空的圓圈中。通過若干步驟移動，要求將數陣中的數字移動成下圖所示狀態：

?

【樣例】
輸入：[1]—[2]—[4]
??????????? ? |?? \ ? |? ?/??? |
?????????? ?[8]—[ ]—[3]
???????????? ?|? ?/???|?? \ ?|
?????????? ? [7]--[5]--[6]
輸出：
? 3#——》0#
? 4#——》3#
? 0#——》4#
? 5#——》0#
? 6#——》5#
? 0#——》6#

[1]—[2]—[3]
? |?? \? ?| ? /? ?|
[8]--? [ ]--[4]
?|? ? /???|?? \ ?|
[7]--[6]--[5]?

方法：

?????? 將外圈中的數據看成一個鏈，頭為圖中1位置，尾為圖中8位置，該鏈最初是8個無序的數據，最終排成如圖所示狀態，所以實際上就是一個數列的排序過程。但需要注意的是，這里只能用冒泡排序，因為按照題意，很容易測試出只需3步就可以交換相鄰位置的兩個數比如圖中3,4。第一步，3->空，第二步，4->空，第三步，3->空。

?????? 這里最關鍵是，將圖看成了一個鏈。最終要求就是一個排序后的鏈。所以問題轉化為排序。但是這里的排序實際上人為的苛刻了。苛刻的條件是，在鏈上，只能同時交換相鄰兩個元素。但是我們知道，冒泡排序告訴我們，即時這樣苛刻，排序也是必然可以完成的，因為冒泡排序就是這樣的。之所以說苛刻了。是因為原本按照題意，我們可以交換首尾（圖中1和8位置），但現在我們不允許這樣做。按照題意，我們也可以隨便移動（不僅僅是相鄰），但這里我們也禁止了。

????? 當然，沒有任何跡象表明我們這樣是最少步驟。雖然題意沒有這點要求。

????? 所以最最核心是問題的轉化，將移動問題轉化為苛刻條件下的冒泡排序。

完整的實現代碼如下：

#include "iostream" using namespace std;int m[8];void print() {cout<<"["<<m[0]<<"]-["<<m[1]<<"]-["<<m[2]<<"]"<<endl;cout<<"["<<m[7]<<"]-[ ]-["<<m[3]<<"]"<<endl;cout<<"["<<m[6]<<"]-["<<m[5]<<"]-["<<m[4]<<"]"<<endl; }void f() {int i,j;for(i=0;i<7;i++){for(j=7;j>=1;j--) //倒序遍歷輸入的8個元素{if(m[j]<m[j-1]) //相鄰兩個元素不滿足條件時，交換{int temp=m[j];m[j]=m[j-1];m[j-1]=temp;cout<<"-------------中間步驟-------------"<<endl;print();cout<<"----------------------------------"<<endl<<endl;}}} } int main(void) {for(int i=0;i<8;i++){cin>>m[i];}print();cout<<endl;f();print();cout<<endl;system("pause");return 0; }

運行效果圖如下：

總結

以上是生活随笔為你收集整理的移数字游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

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