个人项目——找水王续

寻找论坛里的水王（续）

一、程序要求

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

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

随着论坛的发展，管理员发现水王没有了，但是统计结果表明，有三个发帖很多的ID。据统计他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？

二、程序设计思想

题目给出：发帖数目都超过了帖子总数目N的1/4，把回帖列表简单化——一个数组里，存着若干数，其中三个数的数目均超过数组中所有数的数目的1/4。若每次删除四个不同的ID（不管是否包含发帖数目超过总数1/4的ID），那么，在剩下的ID列表中，原先发帖比例大于1/4的ID所占比例仍然大于1/4，可以通过不断重复这个过程，把ID列表中的ID总数降低（转化为更小的问题），从而得到问题的答案。所以，每四个数比较：若四个数都不相同，将前三个数设为水王，并删除这四个数，对应的目前水王出现次数均减1，且对结果无影响；若有相同的数，对应的目前水王出现次数加1，接着比较接下来的数，重复上述过程，一直到最后一个数，找到这三个水王。

三、源程序

//李俏,找水王续抽象程序
//2016.5.25

#include<iostream> 
using namespace std;

void FindWaterKing(int ID[], int num, int wkresult[3])
{
    int i;
    int ID_Impossible = -1;//定义一个不可能存在的ID
    int wknum[3];//水王出现的次数
    wknum[0] = wknum[1] = wknum[2] = 0;
    wkresult[0] = wkresult[1] = wkresult[2] = ID_Impossible;//水王的ID，初始化
    for (i = 0; i<num; i++)
    {
        if (ID[i] == wkresult[0])//水王1出现次数统计
        {
            wknum[0]++;
        }
        else if (ID[i] == wkresult[1])//水王2出现次数统计
        {
            wknum[1]++;
        }
        else if (ID[i] == wkresult[2])//水王3出现次数统计
        {
            wknum[2]++;
        }
        else if (wknum[0] == 0)//将前三个不同的数先存为水王
        {
            wknum[0] = 1;
            wkresult[0] = ID[i];
        }
        else if (wknum[1] == 0)//将前三个不同的数先存为水王
        {
            wknum[1] = 1;
            wkresult[1] = ID[i];
        }
        else if (wknum[2] == 0)//将前三个不同的数先存为水王
        {
            wknum[2] = 1;
            wkresult[2] = ID[i];
        }
        else//此时找到四个不同的数，删除，并且出现次数减1，但是次数不一定为0
        {
            wknum[0]--;
            wknum[1]--;
            wknum[2]--;
        }
    }
}

int main()
{
    int wkresult[3];//找出其中3个符合条件的ID（每个ID的总数分别占ID总数的1 / 4以上）
    int num, arr[1000];
    int i,j;

    cout << "请输入帖子的数量：";
    cin >> num;

    if (arr == NULL || num == 0)//数组为空
    {
        //exit(1);
        return 0;
    }

    cout << "请输入帖子ID：" << endl;
    for (i = 0; i < num; i++)
    {
        cin >> arr[i];
    }

    FindWaterKing(arr, num, wkresult);
    cout << "3个水王的ID分别是：";
    for (j = 0; j < 3; j++)
        cout << wkresult[j] << " ";
    cout << endl;

    return 0;
}

四、结果截图

五、心得体会

有了上次的经验，我没有晕，而是根据经验将四个数分为一组，但是对于程序还是有些没头绪，不过沿着上次的思路——设前三个不同的数为水王，通过比较，留下出现次数最多的三个数。上次的实验有好多不足，如没有考虑数组为空的情况、不能用void main()、应该将主要算法用函数封装起来等等。通过这次课堂练习，我能够举一反三的分析问题，这是一点进步，但是对于将语言转化为程序代码这一块儿，还是有点儿欠缺，希望以后的练习中可以有所进步。实现过程中，出现了不少问题，但是已经在查资料和调试下解决了。