#include <iostream>
using namespace std;
#include <time.h>


#define bitNum 10000  //隨機(jī)數(shù)的位數(shù)
#define boxNum 3  //盒子位數(shù)
#define cishu 100  //比較的次數(shù)

int getRandom(int a)  //隨機(jī)獲取從1到a的數(shù)，調(diào)用該函數(shù)前必須置種
{
	return rand() % a + 1;
}

//int getMi(int a, int b)  //求 a 的 b 次冪
//{
//	int result = a;
//	for (int i = 1; i < b; i++)
//	{
//		result *= a;
//	}
//	return result;
//}

bool tick[64] = {false};  // boxNum 的 boxNum 次方(即64)個(gè)模式串?dāng)?shù)字對(duì)應(yīng)的對(duì)勾框，當(dāng)?shù)谝淮握业綄?duì)應(yīng) boxNum 位數(shù)字時(shí)，前面打勾，即為true

bool allTick()  //當(dāng)tick[]全打上對(duì)勾時(shí)返回true，否則返回false
{
	for (int i = 0; i < 64; i++)
	{
		if (!tick[i])
			return false;
	}
	return true;
}

int Child(int seed)  //主函數(shù)
{
	int allNum[64] = {0};  //用以存放模式串
	int ptr = 0;
	for (int i1 = 1; i1 <= 4; i1++)  //窮舉所有的 boxNum 位數(shù)作為模式串存入 allNum[] 中
	{
		for (int i2 = 1; i2 <= 4; i2++)
		{
			for (int i3 = 1; i3 <= 4; i3++)
			{
				allNum[ptr] = i1 * 100 + i2 * 10 + i3;
				ptr++;
			}
		}
	}
	int randomNum[bitNum] = {0};  //初始化
	srand(seed);  //隨機(jī)種子
	for (int i = 0; i < bitNum; i++)
	{
		randomNum[i] = getRandom(4);
	}
	/*
	cout<<"隨機(jī)得到的主串如下："<<endl;
	for (i = 0; i < bitNum; i++)  //顯示所創(chuàng)建的 bitNum 位隨機(jī)數(shù)
	{
		cout<<randomNum[i];
	}
	cout<<endl;
	*/
	
	//cout<<"Loading...Pleast wait..."<<endl<<endl;

	int box[boxNum] = {0};  //每次用 boxNum 位去取得子串，此稱(chēng)box
	int checkTimes = 0;  //為優(yōu)化算法，僅在取得了 boxNum 的 boxNum 次方(即64)個(gè)數(shù)后才開(kāi)始每次檢測(cè)所有的 tick[] 是否為 true
	int times = 0;  //統(tǒng)計(jì)次數(shù)，即為題目所求
	for (i = 0; i <= bitNum - boxNum; i++)  //模式串不超出主串
	{
		for (int j = 0; j < boxNum; j++)  // box 獲取子串
		{
			box[j] = randomNum[i+j];
		}
		/*for (int k = 0; k < boxNum; k++)  //顯示每次盒子獲得的數(shù)字
		{
			cout<<box[k];
		}
		cout<<endl;*/
		int tmpNum = box[0] * 100 + box[1] * 10 + box[2];  // tmpNum 用來(lái)與 allNum 比較，當(dāng)?shù)谝淮蜗嗟葧r(shí)則在前面打勾(tick[]為true)
		for (int i = 0; i < 64; i++)
		{
			if (allNum[i] == tmpNum)
			{
				tick[i] = true;
			}
		}
		times++;

		if (checkTimes >= 63)
		{
			for (int i = 0; i < 64; i++)
			{
				if (allTick())  //當(dāng)所有的 tick[] 都打上勾時(shí)，則全部找完，輸出總次數(shù)
				{
					//cout<<"已找完，總次數(shù)為： "<<times<<endl;
					//return 0;
					return times;
				}
			}
		}
		checkTimes++;
	}
	cout<<"未找完，總次數(shù)為： "<<times<<endl;
	return 0;
}

int main()
{
	cout<<"   *** 三位模式匹配 ***"<<endl<<"=========================="<<endl;
	int result[cishu] = {0};  //要比較cishu次，存放每次的結(jié)果
	for (int i = 0; i < cishu; i++)
	{
		cout<<"正在進(jìn)行第"<<i+1<<"次比較，共比較"<<cishu<<"次。\r";
		for (int j = 0; j < 64; j++)
			tick[j] = false;
		int randomseed = 0;
		srand((unsigned)time(NULL));
		randomseed = (int)(rand() * i * 10000);  //作隨機(jī)種子
		result[i] = Child(randomseed);
	}
	cout<<endl<<endl;
	for (i = 0; i < cishu; i++)
		cout<<"第"<<i+1<<"次結(jié)果："<<result[i]<<endl;
	int sum = 0;
	for (i = 0; i < cishu; i++)
		sum = sum + result[i];
	sum = sum * 1.0 / cishu;
	cout<<"平均比較次數(shù)為："<<sum<<endl;
	return 0;
}