未完成的搜索

A.第一版

这个小程序是最初的版本。

1。 程序基本说明：这是我试图用程序去解决“5个海盗”的问题。

2。 程序思路：我最初的想法是每个海盗都有各自的最高策略和最低策略，即尽可能获得有自己分配的权利，并通过，这是high strategy;

或者最低限度不死，这是low strategy;每个人的策略一定有一些预想的结果，即当每个海盗采取什么样的对待其他海盗的态度时候，他们

各自的策略才能实现。例如，这是从我的程序文件输出的一个结果：

This is no. 0 pirate 
This is result count No.:3
Pirate\Against  No.0	       No.1	        No.2	       No.3	     No.4	
Pirate No.0	  Agree	
Pirate No.1	  Agree	Agree	
Pirate No.2	  Agree	Against	Agree	
Pirate No.3	  Against	Against	Against	Agree	
Pirate No.4	  Against	Against	Against	Against	Agree	

每个海盗的策略只有和别人的策略不相抵触，才能实现自己的策略，如果，她发现自己的最高策略，当别人也采取最高策略时候无法实现，就要转向

退而求其次的保命策略。想法就是这样，并且我认为原来的问题牵涉到宝石的数量是太复杂了，因此，只想在程序中初步实现定性分析。可是，很

不幸的，我发现问题的复杂程度远远超过我的想象，并且，经过两天两夜的奋战，最初的答案还被推翻了，真是令人沮丧。

。 主要函数介绍：

	A. 

4。 不足之处：

#include <iostream>
#include <fstream>
//#include <iomanip>

using namespace std;

const PirateNum = 5;
const ResultNum = 1024;
const AgreementNum = 20;

struct Strategy
{
	int *pWishes;
	int size;
};

bool SurvivalList[PirateNum] = {false};

Strategy PirateStrategy[PirateNum];

int resultCount =0;
int agreeCount =0;

int BestWishCount[PirateNum] = {0};
int BestWish[PirateNum][ResultNum]= {0};  //high strategy

int LastWishCount[PirateNum] = {0};
int LastWish[PirateNum][ResultNum]= {0}; //low strategy

int PirateCounter[PirateNum] = {0};  //record the number of winning situations

int MatrixValue[PirateNum][ResultNum] = {0};

int FinalAgreement[AgreementNum] = {0};

enum Pirate 
{
	First, Second, Third, Fourth, Fifth
};

enum Status
{
	Agree=1, Dead =0, Disagree = -1
};

char* StatusStr[] = {"Agree", "Dead", "Against"};

Status StatusBoard[PirateNum][PirateNum]={Dead};

Status ResultMatrix[ResultNum][PirateNum][PirateNum] = {Dead};

void initialize();

void findTotalResult();  //return total number of result 

void displayResult(int displayNum);
	

void copyResult(int index);

void calculateResult();

int matrixValue(Status result[PirateNum][PirateNum]);

void displayMatrixValue();

void findWishes();

void doWeAgree();

void analysisResult();

bool commonWishes(int wishIndex);

void getAllStrategy();

void showSurvival();

int status2Index(Status status);

void outputResult(int counter, ofstream& f);

void strategy(int pirateIndex, bool useHigh);

int main()
{
	initialize();
	findTotalResult();
	calculateResult();

	cout<<"total result number is:"<<resultCount<<endl;
	displayMatrixValue();
	getAllStrategy();
	analysisResult();
	

/*
	for (int i=0; i< PirateStrategy[4].size; i++)
	{
		displayResult(PirateStrategy[4].pWishes[i]);
	}
	/*
	for (int pirate=0; pirate< PirateNum; pirate++)
	{
		cout<<"\nThis is pirate no. "<<pirate<<" who has "<<BestWishCount[pirate]<<" wishes:"<<endl; 
		for (int number=0; number< BestWishCount[pirate]; number++)
		{
			displayResult(BestWish[pirate][number]);
		}
	}
	*/
//	showSurvival();

	return 0;
}

void strategy(int pirate, bool useHigh)
{
	if (useHigh)
	{
		PirateStrategy[pirate].pWishes = BestWish[pirate];
		PirateStrategy[pirate].size = BestWishCount[pirate];
	}
	else
	{
		PirateStrategy[pirate].pWishes = LastWish[pirate];
		PirateStrategy[pirate].size = LastWishCount[pirate];
	}
}

void showSurvival()
{
	cout<<"\nThe following is those who survived:\n";
	for (int count=0; count< PirateNum; count++)
	{
		cout<<"No."<<count<<'\t';
	}
	cout<<endl;
	for (count=0; count<PirateNum; count++)
	{
		cout<<SurvivalList[count]<<'\t';
	}
}

void getAllStrategy()
{
	findWishes();
	doWeAgree();
}

void addWishes(int source, int dest)
{
	bool found=false;
	for (int counter=0; counter< LastWishCount[source]; counter++)
	{
		found = false;
		for (int i=0; i<LastWishCount[dest]; i++)
		{
			if (LastWish[source][counter]==LastWish[dest][i])
			{
				found= true;
				break;
			}
		}
		if (!found)
		{
			LastWish[dest][LastWishCount[dest]] = LastWish[source][counter];
			LastWishCount[dest]++;
		}
	}
}

void doWeAgree()
{
	void addWishes(int source, int dest);

	for (int pirate=0; pirate < PirateNum; pirate++)
	{
		for (int agree=0; agree< pirate; agree++) //for those whose index is small than mine I will agree
		{
			addWishes(agree, pirate);
		}
	}
}

void findWishes()
{
	int wishIndex =0;
	for (int pirate=0; pirate< PirateNum; pirate++)
	{
		for (int number = 0; number<PirateCounter[pirate]; number++)
		{
			wishIndex = MatrixValue[pirate][number];
			BestWish[pirate][BestWishCount[pirate]]= wishIndex;//this is a stupid copy
			BestWishCount[pirate]++;
		//	if (pirate==0)
			{
				LastWish[pirate][LastWishCount[pirate]]= wishIndex;//this is a stupid copy
				LastWishCount[pirate]++;
			}
		}
	}
}

bool canSurvive(int pirateIndex)
{	

	for (int number = 0; number<PirateStrategy[pirateIndex].size; number++)
	{
		if (commonWishes(PirateStrategy[pirateIndex].pWishes[number]))
		{
			return true;
		}
	}	
	return false;
}

void checkSurvival()
{
	bool canSurvive(int pirateIndex);

	for (int pirate =0; pirate< PirateNum; pirate++)
	{
		if (canSurvive(pirate))
		{
			SurvivalList[pirate] = true;
		}
	}
}

void analysisResult()
{	
	void checkSurvival();
	

	int pirateIndex =4;
	ofstream f;
	f.open("c:\\pirate.txt");

//	for (int pirateIndex=0; pirateIndex< PirateNum; pirateIndex++)
	{
		strategy(pirateIndex, false);

		for (int pirate=0; pirate< PirateNum; pirate++)
		{
			SurvivalList[pirate] = false;
			if (pirate!=pirateIndex)
			{
				strategy(pirate, true);
			}			
		}
		cout<<"\nNo."<<pirateIndex<<" is... \n";
		checkSurvival();
		showSurvival();
	}

	for (int i=0; i<5; i++)
	{
		f<<"\nThis is no. "<<i<<" pirate "<<'\n';
		for (int j=0; j<PirateStrategy[i].size; j++)
		{
		//	outputResult(PirateStrategy[i].pWishes[j], f);
			f<<PirateStrategy[i].pWishes[j]<<'\t';
		}	
		f<<"\nThere are total "<<j<<" records\n\n\n";
	}

}

bool againstWish(int wishIndex, int pirate)
{
	for (int number=0; number<PirateStrategy[pirate].size; number++)
	{
		if (wishIndex==PirateStrategy[pirate].pWishes[number])
		{
			return false;		
		}
	}
	return true;
}

bool commonWishes(int wishIndex)
{
	bool againstWish(int wishIndex, int pirate);

	for (int pirate=0; pirate< PirateNum; pirate++)
	{
		if (againstWish(wishIndex, pirate))
		{
			return false;		
		}
	}
	return true;
}

void displayMatrixValue()
{
	cout<<"Pirate\\Number"<<'\t';
	for (int pirate =0 ; pirate< PirateNum; pirate++)
	{
		cout<<"No."<<pirate<<'\t';
	}
	cout<<endl;
	cout<<"Number he wins"<<'\t';
	for (pirate=0; pirate<PirateNum; pirate++)
	{
		cout<<PirateCounter[pirate]<<'\t';
	}
	cout<<endl;
}

int matrixValue(Status result[PirateNum][PirateNum])
{
	int total, pirate=0, against =0;

	while (against< PirateNum)
	{		
		pirate = 0;  //as the pirate before is already dead, 
				//and you can calculate, but no effect
		total = 0;
		while (pirate<PirateNum)
		{
			total+= result[pirate][against];
			pirate++;
		}
		if (total>0)
		{
			return against;
		}
		against++;	
	}
	return against;
}

void calculateResult()
{
	int pirate=0;
	for (int index=0; index< resultCount; index++)
	{
		pirate = matrixValue(ResultMatrix[index]);//index of win situation
		MatrixValue[pirate][PirateCounter[pirate]] = index; //record his win situation index
		PirateCounter[pirate] ++;  //his win number increase
	}
	

}
				

void initialize()
{
	for (int pirate = 0; pirate<PirateNum; pirate++)//pirate goes on
	{
		for (int against =0; against< pirate; against++)//what is his opinion or status against others		    
		{
			StatusBoard[pirate][against] = Disagree; 
		}
		StatusBoard[pirate][pirate] = Agree;//everybody agree himselves
	}
	copyResult(0);
	resultCount++;
	

}

int status2Index(Status status)
{
	switch(status)
	{
	case Agree:
		return 0;
	case Dead:
		return 1;
	case Disagree:
		return 2;
	}
}

void outputResult(int counter, ofstream& f)
{
	f<<"This is result count No.:"<<counter<<'\n';
	f<<"Pirate\\Against"<<'\t';
	for (int i=0; i<PirateNum; i++)
	{
		f<<"No."<<i<<'\t';
	}
	f<<'\n';
	for (int pirate=0; pirate< PirateNum; pirate++)
	{
		f<<"Pirate No."<<pirate<<'\t';
		for (int against=0; against<=pirate; against++)
		{
			f<<StatusStr[status2Index(ResultMatrix[counter][pirate][against])]
				<<'\t';
		}
		f<<'\n';
	}
	f<<'\n';
}

void displayResult(int counter)
{
	

	cout<<"This is result count No.:"<<counter<<endl;
	cout<<"Pirate\\Against"<<'\t';
	for (int i=0; i<PirateNum; i++)
	{
		cout<<"No."<<i<<'\t';
	}
	cout<<endl;
	for (int pirate=0; pirate< PirateNum; pirate++)
	{
		cout<<"Pirate No."<<pirate<<'\t';
		for (int against=0; against<=pirate; against++)
		{
			cout<<StatusStr[status2Index(ResultMatrix[counter][pirate][against])]
				<<'\t';
		}
		cout<<endl;
	}	
}

void increase(Status& status)
{
	switch(status)
	{
	case Disagree:
		status = Dead;
		break;
	case Dead:
		status = Agree;
		break;
	case Agree:
		status = Disagree;
		break;
	}
}

void flip(Status& status)
{
	if (status==Disagree)
	{
		status = Agree;
	}
	else
	{
		if (status == Agree)
		{
			status = Disagree;
		}
	}
}

bool findResult()
{
	void increase(Status& status);
	void flip(Status& status);

	int pirate =0, against =0;

	while (pirate<PirateNum)
	{
		against = 0;
		while (against< pirate)
		{
			flip(StatusBoard[pirate][against]);
			if (StatusBoard[pirate][against] == Agree)
			{
				return true;
			}
			against++;
		}
		pirate++;
	}
	return false;
}

void copyResult(int index)
{
	for (int row = 0; row < PirateNum; row++)
	{
		for (int col = 0; col <= row; col++)
		{
			ResultMatrix[index][row][col] = StatusBoard[row][col];			
		}
	}
}

void findTotalResult()
{
	bool findResult();

	while (findResult())
	{		
		copyResult(resultCount);
		resultCount++;
	}
}