课堂练习——找水王

一，设计题目

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

二，设计思路

1）对所有ID进行排序，再扫描已经排好序的ID，查找发帖最多的水王ID

2）再思路1的基础上，仔细分析题目，根据水王发帖数目超过帖子数目一半可知道这个ID序列最中间的ID一定就是水王的ID

3）每次删除两个不同的ID（不管是否包含水王的ID），那么，在剩下的ID列表中，水王ID出现的次数仍然超过总数的一半。可以通过不断重复这个过程，把ID列表中的ID总数降低，从而得到水王ID，该思路对比前两种方便之处在于不用进行排序。

三，设计代码

#include<iostream.h>
int main(){
    int a[10];
    int ans=a[0];
    int count=1;
    cout<<"请输入各ID"<<endl;
    cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]>>a[7]>>a[8]>>a[9];
    for(int i=1;i<10;i++)
    {
        if(a[i]==ans)
            count++;
        else
            count--;
        if(count==0)
        {
            ans=a[i];
            count=1;
        }
    }
    cout<<"水王ID为"<<ans<<endl;
    return 0;
}

四，实验截图

五，实验体会

许多看起来一眼就能找到简单方法的题目往往存在优化的空间，所以通过这次与上次电梯调度的实验体会到了，分析题目的重要性，学会寻找简便方法。而且事物都具有普遍性所以我认为这类题目10个足以说明问题。