分治算法 黑白棋子的移動

• • • • 題目：
      • 解析：

題目：

有2n個棋子（n≥4）排成一行，開始位置為白子全部在左邊，黑子全部在右邊，如下圖為n=5的情形：
○○○○○●●●●●
移動棋子的規(guī)則是：每次必須同時移動相鄰的兩個棋子，顏色不限，可以左移也可以右移到空位上去，但不能調(diào)換兩個棋子的左右位置。每次移動必須跳過若干個棋子（不能平移），要求最后能移成黑白相間的一行棋子。如n=5時，成為：
○●○●○●○●○●
任務：編程打印出移動過程。

解析：

同志們可能看不出來

這道題為什么是分治

下面我來解釋一下：

我們先從n=4開始試試看，初始時：

○○○○●●●● —— {—表示空位}

第1步：○○○——●●●○●
第2步：○○○●○●●——●
第3步：○——●○●●○○●
第4步：○●○●○●——○●
第5步：○●○●○●○●——

如果n=5呢？我們繼續(xù)嘗試，希望看出一些規(guī)律，初始時：

○○○○○●●●●●

第1步：○○○○——●●●●○●
第2步：○○○○●●●●——○●

這樣，n=5的問題又分解成了n=4的情況，

下面只要再做一下n=4的5個步驟就行了。

同理，

n=6的情況又可以分解成n=5的情況，

所以，

對于一個規(guī)模為n的問題，

我們很容易地就把他分治成了規(guī)模為n-1的相同類型子問題。

數(shù)據(jù)結(jié)構如下：數(shù)組c[1…max]用來作為棋子移動的場所，

初始時，

c[1]~c[n]存放白子（用字符o表示），

c[n+1]~c[2n]存放黑子（用字符*表示），

c[2n+1]~c[2n+2]為空位置（用字符—表示） 。

最后結(jié)果在c[3]~c[2n+2]中。

所以

同志們可發(fā)現(xiàn)了

這道題

其實就是典型的

遞歸思想

只要記下n=4的話就可以了

下面附上代碼：

#include<bits/stdc++.h> #include<iostream> #include<cstdlib> #include<cstdio> using namespace std; int main() {freopen("hb.in","r",stdin);freopen("hb.out","w",stdout);char a[1000];int n,sum=0,temp,d;cin>>n;d=n;for(int i=1; i<=n; i++)a[i]='o';for(int i=n+1; i<=n*2; i++)a[i]='*';a[n*2+1]=a[n*2+2]='-';cout<<"step "<<sum<<":";for(int i=1; i<=d*2+2; i++)cout<<a[i];cout<<endl;sum++;while(n>=4){if(n==4){temp=a[4];a[4]=a[9];a[9]=temp;temp=a[5];a[5]=a[10];a[10]=temp;cout<<"step "<<sum<<":";for(int i=1; i<=d*2+2; i++)cout<<a[i];cout<<endl;sum++;temp=a[4];a[4]=a[8];a[8]=temp;temp=a[5];a[5]=a[9];a[9]=temp;cout<<"step "<<sum<<":";for(int i=1; i<=d*2+2; i++)cout<<a[i];cout<<endl;sum++;temp=a[2];a[2]=a[8];a[8]=temp;temp=a[3];a[3]=a[9];a[9]=temp;cout<<"step "<<sum<<":";for(int i=1; i<=d*2+2; i++)cout<<a[i];cout<<endl;sum++;temp=a[2];a[2]=a[7];a[7]=temp;temp=a[3];a[3]=a[8];a[8]=temp;cout<<"step "<<sum<<":";for(int i=1; i<=d*2+2; i++)cout<<a[i];cout<<endl;sum++;temp=a[1];a[1]=a[7];a[7]=temp;temp=a[2];a[2]=a[8];a[8]=temp;cout<<"step "<<sum<<":";for(int i=1; i<=d*2+2; i++)cout<<a[i];cout<<endl;break;}else{temp=a[n];a[n]=a[n*2+1];a[n*2+1]=temp;temp=a[n+1];a[n+1]=a[n*2+2];a[n*2+2]=temp;cout<<"step "<<sum<<":";for(int i=1; i<=d*2+2; i++)cout<<a[i];cout<<endl;sum++;temp=a[n];a[n]=a[n*2-1];a[n*2-1]=temp;temp=a[n+1];a[n+1]=a[n*2];a[n*2]=temp;cout<<"step "<<sum<<":";for(int i=1; i<=d*2+2; i++)cout<<a[i];cout<<endl;sum++;n--;}}fclose(stdin);fclose(stdout);return 0; }

拜拜！

總結(jié)

以上是生活随笔為你收集整理的分治算法 黑白棋子的移动的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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