珠璣妙算這個游戲大家都不陌生，規則就不多說了，直接進主題：
需要破譯的密碼由四位組成，每位可以是0~9中的任意數字，eg. (1544,4301,0918,...）
此演算法可在20步內猜測出結果，
演算法大致步驟分為兩步：
第一步：求出這串密碼是由哪四個數字組成，從0000迭代到9999就行，第一步最多需要十次猜測，
第二步：將由第一步得出的四個數字全排列，把全排列結果存在一個集合里，然后依次回傳集合里的猜測并通過猜測結果做簡單的劃分，對集合進行進一步的消除從而減少猜測次數，
劃分規則如下：
當結果猜中數為0時：因為0位猜中，所以四個位的數字都是錯的，從而我們可以直接消除集合里所有與此猜測有相同位的元素，舉例：假設猜測為“1234”并且猜中數為0，我們就可以把集合里所有第一位為1，第二位為2，第三位為3，第四位為4 的元素全部消除掉，
當結果猜中數為2時：這種情況稍微復雜點，具體操作如下：把該猜測和之前猜中數為2的猜測做比對，若二者中有且僅有一位數字同位，那么該數字在密碼中就屬于該位，舉例：假設“1234”的猜中數為2，“4132”猜中數也為2，通過比對這兩串數字得知它們的第三位是相同的，都為3，所以可以得知真正密碼的第三位就是3，然后回到我們的集合把第三位不為3的元素全部消除，
當結果猜中數為1，3，4時，不予任何操作，
整體演算法如上所述，我的演算法是以一個函式的形式運行的：string mastermindAI(int rr, int rw)
這個函式每次被呼叫都會回傳一個猜測（string)，然后主程式將會以引數形式將猜測結果傳給函式（rr為真猜中數量，rw為偽猜中數量），第一次被呼叫時rr和rw為0，
珠璣妙算的主程式會在下一篇博客中，
學習編程一年一來的第一篇博客，不足之處請賜教，
程式：
string mastermindAI(int rr,int rw){
static const int SIZE=10000;//How many guesses to save
static string gHistory[SIZE];//guess history
static int rHistory[SIZE];//result history
static int hisCount=0;// history counter
static string sGuess="0000"; //Size the guest string
static int guessNum=0;
static char bit[4];
static int bitSize=4;
static int bitNum=0;
static vector<string> guessBase;
static bool once=true;
static bool beforeSecondStep=false;
//第一步：迭代回傳0-9，求出四位數字
if(bitNum<4)
{
if(rr>0)
{
for(int i=0;i<rr;i++)
{
bit[bitNum]=sGuess[1];
bitNum++;
}
}
if(bitNum<4)
{
for(int i=0;i<4;i++)
{
sGuess[i]=guessNum+'0';
}
}
}
//當四位數字都找到時，進入第二步：
if(bitNum>=4)
{
vector<string>::iterator it;
if(once) //進入第二步后，首先把四位數字全排列，所有排列組合將被存入名為guessbase的容器中
{ //由此到156行為全排列演算法
for(int i=0;i<4;i++)
{
for(int j=i+1;j<4;j++)
{
if(bit[i]==bit[j])
{
bitSize--;
}
}
}
for(int i=0;i<4;i++)
{
for(int j=0;j<3;j++)
{
if(bit[j]>bit[j+1])
{
char temp;
temp=bit[j];
bit[j]=bit[j+1];
bit[j+1]=temp;
}
}
}
string stemp=bit;
guessBase.push_back(stemp);
for(int i=3;i>0;i--) //permutation the bit[]
{
if(bit[i-1]<bit[i])
{
char minIdx=i;
for(int j=i;j<4;j++)
{
if(bit[j]>bit[i-1])
{
if(bit[j]<=bit[minIdx])
{
minIdx=j;
}
}
}
char temp;
temp=bit[minIdx];
bit[minIdx]=bit[i-1];
bit[i-1]=temp;
for(int j=i,k=3;j<k;j++,k--)
{
temp=bit[j];
bit[j]=bit[k];
bit[k]=temp;
}
stemp=bit;
guessBase.push_back(stemp);
i=4;
}
}
once=false;
}
//全排列結束，回傳guessbase容器里的第一個元素，然后擦除
if(beforeSecondStep==false)
{
sGuess=guessBase[0];
it=guessBase.begin();
it=guessBase.erase(it);
beforeSecondStep=true;
}
else //下面進入到劃分環節
{
gHistory[hisCount]=sGuess;
rHistory[hisCount]=rr;
hisCount++;
switch(rr) //當真猜中數為0和2時進行劃分，其他猜中數不劃分
{
case 0:
for(it=guessBase.begin();it!=guessBase.end();)
{
string temp=*it;
if(temp[0]==sGuess[0]||temp[1]==sGuess[1]||temp[2]==sGuess[2]||temp[3]==sGuess[3])
{
it=guessBase.erase(it);
}
else
{
it++;
}
}
break;
case 2:
if(bitSize==4||bitSize==3)
{
for(int i=0;i<hisCount;i++)
{
int rNum=0;
int idx=0;
if(rHistory[i]==2)
{
for(int j=0;j<4;j++)
{
if(gHistory[i][j]==sGuess[j])
{
rNum++;
idx=j;
}
}
if(rNum==1)
{
for(it=guessBase.begin();it!=guessBase.end();)
{
string temp=*it;
if(temp[idx]!=sGuess[idx])
{
it=guessBase.erase(it);
}
else
{
it++;
}
}
}
}
}
}
break;
default:
break;
}
sGuess=guessBase[0];
it=guessBase.begin();
it=guessBase.erase(it);
}
}
guessNum++;
//Return the result
return sGuess;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/287238.html
標籤：其他