celebrity_algorithms.cpp

上海交通大学研究生算法分析课的作业.实现了<<算法引论-一种创造性方法>>(Udi Manber 黄林鹏 电子工业出版社)第五章中的大部分算法

#include <iostream> 
#include <stdlib.h> 

#ifdef _WIN32 
using namespace std; 
#endif 

void main()
{
	printf("社会名流算法\n");
	printf("\n作者:茹炳晟(学号:1060379162)\n");
	printf("\n说明：本算法只是起演示作用的基本雏形，以5个人为例子，并且数据写死在了程序中\n");
	printf("以下是know矩阵：\n");
	
	int know[6][6]={{-1,-1,-1,-1,-1,-1},
				{-1,-1,1,0,1,1},
				{-1,0,-1,0,0,0},
				{-1,0,1,-1,1,0},
				{-1,1,1,1,-1,0},
				{-1,0,1,1,0,-1}};
	int i,j,next;
	int candidate;
	

	for(i=1;i<=5;i++)
		for(j=1;j<=5;j++)
		{
			printf("%i   ",know[i][j]);
			if(j==5)
			  printf("\n");
		}
	//第一阶段，通过消除只留下一个候选者
	i=1;
	j=2;
	next=3;
	while(next<=5+1)
	{
		if(know[i][j]==1)
			i=next;    //如果i认识j,则i不可能是社会名流，应该排除i
		else
			j=next;    //如果i不认识j,则j不可能是社会名流，应该排除j
		next++;
	}
	if(i==5+1)         //如果i不是社会名流（i==5+1）
		candidate=j;   //那么j是候选者
	else
		candidate=i;   //否则i是候选者

	//以下开始检查候选者确实是社会名流
	bool wrong=false;
	int celebrity;
	int k=1;
	know[candidate][candidate]=false;    //矩阵中know[i,i]设为false
	while(!wrong && k<=5)
	{
		if(know[candidate][k]==1)
			wrong=true;
		if(know[k][candidate]==0)
			if(candidate!=k)       //排除自身
				wrong=true;
		k++;
	}
	if(!wrong)
		celebrity=candidate;
	else
		celebrity=0;
	printf("\n社会名流是第%i个人\n\n",celebrity);

	system("PAUSE"); 
}