寻找水王

题目 

三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？

设计思路：

分析：

该“水王”法非数目超过帖子数目的一半，所以，当帖子数目为单数或双数时，“水王”发帖数减去其他帖数至少为1或2。进一步可理解为当把“水王”的帖子与其他不同的帖子一一消去后，最终至少剩下“水王”的1或2张帖。又因为当都不是“水王”的不同帖子一一相消后，只会使“水王”的帖子剩下的更多，所以最终可总结为，只要把不同的帖子一一消去，最终肯定剩下“水王”帖子。

数学建模：

设置一个变量“he”，设定帖子列表的第一项的ID为默认ID，对表中的各项进行遍历，当其各项与默认ID相同时，“he+1”。当与上一项不同时，“he-1"用变量“id”记录"he"为正时的默认ID，当"和”为负时，更新默认ID为帖子列表中对应项的下一项。最终的“id”即为所求。

源代码：

#include<iostream>

using namespace std;

void main()

{  

int array[1000];

int num,he,id;

cout<<"请输入ID的个数：";  

cin>>num;  

cout<<"请输入ID序列：";  

for(int i=0;i<num;i++)   

cin>>array[i];  

he=0;  

id=array[0];  

for(int i=0;i<num-1;i++) //i<num-1避免了array[num-1]与array[num]判断是否相等的步骤出现，从而避免错误发生  

{  

if(id==array[i+1])  //当被判断ID与默认水王ID相同时的情况    

he+=1;   

else                //当被判断ID与默认水王ID不同的情况    

he-=1;   

if(he==-1)          ////通过和的值，将相同数量的水王的ID记录和非水王的ID记录消除，或将相同的非水王的ID记录消除   

{    

i+=1;    

he=0;    

id=array[i+1];   

}  

}  

cout<<"水王的ID是"<<id<<endl;

}

实验结果截图：

实验总结：

      变成时注意要注意数组的边界。同时学会了一种新的变成思路。