課堂練習-找水王

課堂練習-找水王

•三人行設計了一個灌水論壇。資訊學院的學生都喜歡在上面交流灌水，傳說在論壇上有一個“水王”，他不但喜歡發帖，還會回複其他ID發的每個文章。坊間風聞該“水王”發帖數目超過了文章數目的一半。

要求:

•如果你有一張目前論壇的文章（包括回帖）清單，其中文章的作者的ID也在其中，你能快速的找到這個傳說中的水王嗎？

思路：

題目可以簡化為在一維數組中找ID超過一半的ID，例如array[]={123,456,123,452,123};中“123”就為所求水王。要求能夠快速找到水王，也就意味着能在時間和空間上具有一定的優化。是以可以采用消除法來求得所需水王。

消除法：首先使用 a,b 來分别記錄ID 出現的數量和ID名.

1.在周遊數組的比較array[i]和array[i-1]即比較相鄰項，如果兩項不等則a-1，相等則a+1.

2.當通路array[i]且a=0時，a+1且b=ID.

3.周遊完數組時b就為所求ID.

代碼:

/**
*@Mr.缪 
*缪金敏 
*20132984 
**/
#include<iostream>
#include<string>
using namespace std;
int main()
{
    int number=0; //用于記入ID數量
    string array[]={"wang123","xiaomin","dkm","wang123","wang123","dkm","wang123"};  //現有的文章名單清單
    string ID=array[0]; //用于記入ID 
    for(int i=0;i<sizeof(array)/sizeof(array[0]);i++){
        if(number==0)
        {
            ID=array[i];
            number++;
        }else
        {
            if(ID==array[i]){
                number++;
            }
            else{
                number--;
            }
        }
    } 
    if(number==0)//判斷是否有水王 
    {
        cout<<"無水王！"; 
    }
    else{
        cout<<"水王為："<<ID;
        cout<<endl;
    }
    return 0;
}       

實驗截圖:

個人總結:

在這次的作業中我一共出現2個問題,在使用循環時計算數組長度使用了length方法，但C/C++并沒有該方法，是以我最後用了sizeof方法，在使用ID變量時，因為我最開始是使用NULL給ID 初始化的是以在後來的ID指派中便出現了問題，最後我把ID初始化為數組的第一個字元串。