找水王

一.设计思路

　　1.由于题设中给出条件“水王”的发贴数超过列表中总发贴数的一半（即最少比一半多一个）；

　　2.假设“水王”的发贴数恰好是总发贴数的一半多一个，而“水王”的贴子是均匀分布在贴子列表中的，即每两个相邻的贴子中总有一个“水王”的贴子；

　　　　a.如果贴子总数为奇数，且每两个相邻贴子中总是“水王”的贴子在前（在后亦然），则最后必然剩下一个“水王”的贴子；

　　　　b.如果贴子总数为偶数，且每两个相邻贴子中总是“水王”的贴子在前（在后亦然），则最后必然剩下两个“水王”的贴子。

　　3.如果“水王”的发贴数更多时，则两个相邻贴子都是“水王”的概率更高；

　　4.根据以上的分析，可以用一个函数按序号依次将贴子列表中的每两个相邻贴子的ID比较，如果相同，则保留一个ID号存放于一个一维数组中；如果不相同，

则跳过，进行下面两个相邻贴子ID号的比较；

　　5.如果所得一维数组中只有一个元素，则该ID号即为“水王”的ID号；如果所得一维数组中超过一个元素，则将该一维数组递归调用比较函数，直到一维数组中只有一个元素。

二.代码实现

#include<iostream>
#include<fstream>
#include<string>
#define N 100
using namespace std;

string findM(string str[],int num)
{
    string real;    //记录查找到的水王ID号
    string next[N];    //按序号将ID号两两比较，若相同，则将该ID号保留一个存放于next[N]中；若不相同，则跳过
    int i;
    int length=0;    //记录每次生成的数组next的长度
    for (i = 0; i < num; i+=2)
    {
        if ((str[i] == str[i + 1]&&i+1<num)||i+1==num)
        {
            next[length] = str[i];
            length++;
        }
    }
    //当数组next中只有一个元素时，该元素即为所找水王
    if (length == 1)
    {
        real = next[0];
    }
    else if (length == 0)
    {
        real = "" ;
    }
    else
    {
        real=findM(next, length);
    }
    return real;
}

int main()
{
    //ifstream file("myfile.txt");
    ifstream file;
    file.open("myfile.txt");
    if (!file)
    {
        cout << "文件不存在！" << endl;
    }
    else
    {
        int num[N];    //存放序号
        string str[N];    //存放各序号对应的ID号
        string gfind;    //获得的水王的ID号
        int n = 0;    //存放发帖表行数
        while (file >> num[n] >> str[n])
        {
            n++;
        }
        if (n > 0)
        {
            cout << "发帖表信息：" << endl;
            cout << "序号	贴主ID号" << endl;
            for (int i = 0; i < n; i++)
            {
                cout << num[i] << "	" << str[i] << endl;
            }
            cout << "
";
            gfind = findM(str, n);
            if (gfind == "")
            {
                cout << "此列表中不存在这样的水王（发贴数超过总贴子数的1/2）！" << endl;
            }
            else
            {
                cout << "水王是：";
                cout << gfind << endl;
            }
        }
        else
        {
            cout << "文件为空！" << endl;
        }
    }
    file.close();
    return 0;
}

三.实验截图

1.测试数据一

2.测试数据二

3.空文件测试

4.错误列表（无水王）测试

四.个人总结

　　本次实验刚开始想了挺长时间，都没有想出什么思路，后来通过老师的提示才有了思路，程序写完之后才发现，其实难度也确实不大。