test.cpp

有一串10000位数的主串由1、2、3、4四位数随机获得

#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;
}