问题描述：名人问题
一个名人就是指这样一个人：所有其他人都认识他，并且他不认识任何其他人。现在有一个N个人的集合，以及他们之间的认识关系。求一个算法找出其中的名人（如果有的话）或者判断出没有名人（如果没有的话）。
1.构造输入数据数组，名人所在的Index可控。
public static int[,] initCelebrityData(int size, int celebrateIndex)
{
int[,] arrray = new int[size, size];
Random rnd = new Random(DateTime.Now.Millisecond);
for (int i = ; i < size; i++)
{
int tmpColumn = rnd.Next(, size - );
for (int j = ; j < size; j++)
{
if (j == tmpColumn)
{
arrray[i, j] = ;//每一行至少有一个元素为1，每个人至少认识一个人
}
else
{
arrray[i, j] = rnd.Next() % ;
}
}
}
//构造一个名流
for (int i = ; i < size; i++)
{
arrray[celebrateIndex, i] = ; //Celebrity know nobody.
arrray[i, celebrateIndex] = ;//Everybody knows the Celebrity.
}
return arrray;
}
2.求解名人，分两步，第一步排除所有非名人，第二步判断剩下的候选者是否为名人。
public static bool FindCelebrity(int[,] knowArray, ref int celebrityIndex)
{
if (knowArray == null) throw new ArgumentNullException("knowArray");
if (knowArray.GetUpperBound() != knowArray.GetUpperBound()) throw new Exception("A square matrix is required.");
int i = ;//candidate
for (int j = ; j <= knowArray.GetUpperBound(); j++)
{
if (knowArray[i, j] == )//i know j
i = j;
}
bool result = true; for (int j = ; j <= knowArray.GetUpperBound(); j++)
{
if (i == j) continue;
if (knowArray[i, j] == || knowArray[j, i] == )//i know j
{
result = false;
break;
}
} if (result)
{ celebrityIndex = i; }
else
{ celebrityIndex = -; }
return result;
}
}
运行结果：
下载源码。
作者：Andy Zeng
欢迎任何形式的转载，但请务必注明出处。