软件工程课堂练习--找出“水王”

一、题目要求

现有一个灌水论坛，信息学院的学生都喜欢在上面交流灌水。传说在论坛上有一个“水王”，它不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目已超过了帖子数目的一半。

如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者ID在其中，请设计算法快速找到这个传说中的“水王”。

二、设计思路

程序的设计思路大体就是，首先设2个变量，将第一个数暂时给shuiwang这个变量并且和下一个数比较，如果相同则用一个X变量自加一，不同则减一；如此循环，如果遇到不同时，一直减减减，x变为0，shuiwang又被新的数覆盖，以此类推，找到最终的水王ID。

三、源代码

 1 / 123.cpp : Defines the entry point for the console application.
 2 //
 3 
 4 #include "stdafx.h"
 5 
 6 
 7 int findshuiwang(int arrID[],int num)
 8 {
 9     int shuiwang;
10     int x;
11     for(int i=x=0;i<num;i++)
12     {
13         if(x==0)
14         {
15             shuiwang=arrID[i],x=1;
16         }
17         else
18         {
19             if(shuiwang==arrID[i])
20             {
21                 ++x;
22             }
23             else
24             {
25                 --x;
26             }
27         }
28     }
29     printf("这个“水王”的ID就是：");
30     printf("%d
",shuiwang);
31     return shuiwang;
32 }
33     
34 
35 
36 int main(int argc, char* argv[])
37 {
38     int arry[6]={11110,11110,11110,11110,11112,11112};
39     findshuiwang(arry,6);
40     return 0;
41 }

四、实验截图

五、实验总结

一开始想到的是先排序，然后水王的ID就在1/2处数组的地方，可是如果是这样的话时间复杂度绝不是f(n),所以这种方法OUT...

后来经过老师的提示，采用消消乐的方法，将不同的消去，相同的留下那最后剩下的“水王”可定就在其中。不过在实现时就碰到了问题，是1,2；3,4；..这种数组顺序比较还是1,2；2,3；3,4..这样比较，还要区别开来，不然就会出错