找水王

问题：

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

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

解题思想

条件为  在一个数组str中，存在着水王、及其他用户。其中水王超过了50%。
问题为  找到水王。
问题简化为：在str数组中，存在着0-9数字，其中一个数字的个数超过了50%，找到这个数字。
设计思想：1、先构建一个有若干个数字的数组，其中水王数字超过50%。2、将相邻数字匹配，相同则留下，不同则删去。3、遍历一遍即可找到水王数字。

 

#include <iostream>
#include <ctime>
#include <string>
using namespace std;
void main()
{
    //构造数组str
    srand((unsigned)time(0));
    string str = "";
    int Numstr = 1000;   //定义数组长度
    int num=0;    //记录水王数字个数
    int Shuiwang=rand()%10;  //随机定义水王数字
    while (Numstr!=0)
    {
        if(rand()%10 <= 5) //  加水王数字
        {
            str+=Shuiwang+48;
            num++;
        }
        else             //否则 加水王或者其他数字    
        {
            str+=rand()%10+48;
        }
        Numstr--;
    }
    cout<<"含水王的数组："<<str<<endl;
    cout<<"水王数字的个数："<<num<<endl;
    //相邻数字 匹配  相同则复制到str1中  
    string str1 = "";
    for(int i=0;i<str.length();i=i+2)
    {
        if(str[i]==str[i+1])
        {
            str1+=str[i];
        }
    }
    cout<<str1<<endl;     //此时str1中  绝大部分都是水王数字
    //其中任取若干 相同则是水王
    //此时取3个
    while(1)
    {
        int a=rand()%str1.length();
        int b=rand()%str1.length();
        int c=rand()%str1.length();
        if(str1[a]==str1[b]&&str1[a]==str1[c])
        {
            cout<<"水王是："<<str1[a]<<endl;
            break;
        }
    }
}

结果截图：

另外，因为水王个数已经超过了1/2，从中随机找三个，如果三个一样即为水王。原因有下：

1、用户的个数会是个大数字，且每个用户的发帖个数与1/2的水王发帖个数相差甚多。

2、论坛的发帖个数会是个大数字。

3、假设有11个用户，水王占最少1/2，其他发帖平均为最多  1/20。三个都是水王的概率为1/2 * 1/2 * 1/2 为1/8。其他平均概率为 1/20 * 1/20  * 1/20 为1/8000。

由上即可断定水王。

代码如下：

//条件为  在一个数组str中，存在着水王、及其他用户。其中水王超过了50%。
//问题为  找到水王。
//问题简化为：在str数组中，存在着0-9数字，其中一个数字的个数超过了50%，找到这个数字。
//设计思想：1、先构建一个有若干个数字的数组，其中水王数字超过50%。2、将相邻数字匹配，相同则留下，不同则删去。3、遍历一遍即可找到水王数字。
#include <iostream>
#include <ctime>
#include <string>
using namespace std;
string STR()
{
    //构造数组str
    srand((unsigned)time(0));
    int f=1;
    while(f)
    {
        string str = "";
        int Numstr = 1000;   //定义数组长度
        int num=0;    //记录水王数字个数
        int Shuiwang=rand()%10;  //随机定义水王数字
        while (Numstr!=0)
        {
            if(rand()%2 == 1) //  加水王数字
            {
                str+=Shuiwang+48;
                num++;
            }
            else             //否则 加水王或者其他数字    
            {
                str+=rand()%10+48;
            }
            Numstr--;
        }
        if(num>500)
        {
            cout<<"含水王的数组："<<str<<endl;
            cout<<"水王数字的个数："<<num<<endl;
            return str;
        }
    }
}
void main()
{
    string str=STR();
                //其中任取若干 相同则是水王
    //此时取3个
    while(1)
    {
        int a=rand()%str1.length();
        int b=rand()%str1.length();
        int c=rand()%str1.length();
        if(str1[a]==str1[b]&&str1[a]==str1[c])
        {
            cout<<"水王是："<<str1[a]<<endl;
            break;
        }
    }*/

    while(1)
    {
        int a=rand()%str.length();
        int b=rand()%str.length();
        int c=rand()%str.length();
        if(str[a]==str[b]&&str[a]==str[c])
        {
            cout<<"水王是："<<str[a]<<"   "<<str[b]<<" "<<str[c]<<endl;
            break;
        }
    }
}

结果如图：