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


#define bitNum 100000  //隨機數的位數
#define boxNum 5  //盒子位數
#define cishu 100  //比較的次數

int getRandom(int a)  //隨機獲取從1到a的數，調用該函數前必須置種
{
	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[1024] = {false};  // boxNum 的 boxNum 次方(即1024)個模式串數字對應的對勾框，當第一次找到對應 boxNum 位數字時，前面打勾，即為true

bool allTick()  //當tick[]全打上對勾時返回true，否則返回false
{
	for (int i = 0; i < 1024; i++)
	{
		if (!tick[i])
			return false;
	}
	return true;
}

int Child(int seed)  //比較一次的子程序
{
	int allNum[1024] = {0};  //用以存放模式串
	int ptr = 0;
	for (int i1 = 1; i1 <= 4; i1++)  //窮舉所有的 boxNum 位數作為模式串存入 allNum[] 中
	{
		for (int i2 = 1; i2 <= 4; i2++)
		{
			for (int i3 = 1; i3 <= 4; i3++)
			{
				for (int i4 = 1; i4 <= 4; i4++)
				{
					for (int i5 = 1; i5 <= 4; i5++)
					{
						allNum[ptr] = i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5;
						ptr++;
					}
				}
			}
		}
	}
	int randomNum[bitNum] = {0};  //初始化
	srand(seed);  //隨機種子
	for (int i = 0; i < bitNum; i++)
	{
		randomNum[i] = getRandom(4);
	}
	/*
	cout<<"隨機得到的主串如下："<<endl;
	for (i = 0; i < bitNum; i++)  //顯示所創建的 bitNum 位隨機數
	{
		cout<<randomNum[i];
	}
	cout<<endl;
	*/
	
	//cout<<"Loading...Pleast wait..."<<endl<<endl;

	int box[boxNum] = {0};  //每次用 boxNum 位去取得子串，此稱box
	int checkTimes = 0;  //為優化算法，僅在取得了 boxNum 的 boxNum 次方(即1024)個數后才開始每次檢測所有的 tick[] 是否為 true
	int times = 0;  //統計次數，即為題目所求
	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++)  //顯示每次盒子獲得的數字
		{
			cout<<box[k];
		}
		cout<<endl;*/
		int tmpNum = box[0] * 10000 + box[1] * 1000 + box[2] * 100 + box[3] * 10 + box[4];  // tmpNum 用來與 allNum 比較，當第一次相等時則在前面打勾(tick[]為true)
		for (int i = 0; i < 1024; i++)
		{
			if (allNum[i] == tmpNum)
			{
				tick[i] = true;
			}
		}
		times++;

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

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