一、实验题目与设计思路

1、题目：

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

如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到这个传说中的水王吗？

2、设计思路

   首先这个题目有有一个前提就是在总帖数一定的情况下，这些帖子里面有一半以上的帖子都设计到一个ID，这个ID就是水军，为了制止这个水军，就要检测出这个水军，那么我们定义一个数组，数组里面的数字定为水军的ID，在这个数组里面查找出在数组里出现半数以上的这个ID，要求时间复杂度为o(n)，意思就是只能有一层for循环，按照老师上课讲的采用消消乐的方式，两个不一样的就消去，因为水军的帖子数超过半数，那么消到最后剩下的就是水军，然后在输出这个水军的ID。

二、源代码

1 // shuiwang.cpp : Defines the entry point for the console application. 2 // 3  4 #include "stdafx.h" 5 #include "stdio.h" 6  7  8 int main(int argc, char* argv[]) 9 {10     int a[10000];11     int tiezishu; 12     int i,j,k=1;13     int shui;14     printf("请输入帖子总数：");15     scanf("%d",&tiezishu);16     printf("\n");17     for(i=0;i

 

三、运行结果截图

 

四、心得体会

每一个题目的设计实现有很多种方法，有笨的方法，有简单的方法，有最优化的方法，也有复杂度比较大的方法，这次老师要求我们用时间复杂度比较低的方法来实现，但是首先我想到的还是最笨的方法来实现，以前对程序的时间复杂度并没有要求，只要能够实现了题目的要求就好了，程序实现了也没有想过优化，但是这次深刻的体会到了，一个好的程序代码精简但是功能强大。话又说回来，一个好的程序设计的难度也是比较高的，但是我们要这样的锻炼下去，我相信慢慢的我们的能力就会提高很大。