??? 題目：

??? 三人行設計了一個灌水論壇。信息學院的學生都喜歡在上面交流灌水，傳說在論壇上有一個“水王”，他不但喜歡發帖，還會回復其他ID發的每個帖子。坊間風聞該“水王”發帖數目超過了帖子數目的一半。如果你有一張當前論壇的帖子（包括回帖）列表，其中帖子的作者的ID也在其中，你能快速的找到這個傳說中的水王嗎？

??? 設計思想：

??? 通過對帖子列表進行遍歷，統計水王帖子的數目是最簡單的一種查找水王的方式，但是這種算法時間復雜度比較高。

??? 采用優化的算法來解決這道問題，可以通過兩兩比較的方式來查找水王。如果當下正在比較的兩個ID不同，則將其刪除，（不論水王的ID是否在這兩個之中），剩下的列表中，“水王”ID出現的次數仍然超過剩余總數的一半。通過不斷的重復這個過程，列表中的記錄數目就可以逐漸減少，從而在整體上降低算法的時間復雜度。

??? 程序概要設計：

??? 我的程序中首先假設列表中有十個用戶ID，用戶的ID號分別用0-9十個數字字符來代替，利用隨機函數，生成N條記錄，即將用戶的ID號保存在一個長度為N的一維數組中。程序的起始同樣用隨機數生成了一個自定義的“水王”，在后續的程序中通過不重復隨機替換的方式，確保了一維數組中的自定義“水王”ID號在一半以上。查找水王的核心程序利用上述思想完成，程序的最后加了一個判斷，通過這個判斷可以清楚地知道自己的找水王程序是否得到了正確的結果。

??? 程序詳細設計見源代碼。

??? 源代碼如下：

//現有一張灌水論壇的帖子列表，“水王”發帖的數目超過了帖子數目的一半，找出水王ID //05-19,2016,Hailin Song#include<iostream> #include<stdlib.h> #include<time.h> using namespace std;#define N 100int main() {srand((int)time(NULL)); //定義時間種子int InitShuiWang = 0 + rand() % 10; //假設帖子列表中有10個ID號，分別用0-9這十個數字字符代替，自定義“水王”的IDcout << "自定義的“水王”ID為：";cout << InitShuiWang << endl; //輸出自定義的“水王”ID，同時測試“找水王”程序的結果是否正確cout << endl;int Tiezi[N]; //假設帖子列表中有N條記錄int location[N / 2 + 1];for (int i = 0; i < N; i++){Tiezi[i] = 0 + rand() % 10;}for (int i = 0; i < (N/2+1); i++) //循環執行(N/2+1)次，確保帖子列表中有一半以上為“水王”的ID{location[i] = 0 + rand() % N; //確定帖子列表中隨機替換的位置for (int j = 0; j < i; j++){if (location[i] == location[j]) //確保隨機替換的位置不會發生重復{location[i] = 0 + rand() % N;j = -1;}}Tiezi[location[i]] = InitShuiWang; //用“水王”的ID替換隨機產生的用戶的ID}cout << "帖子列表的ID如下所示：" << endl;for (int i = 0; i < N; i++){cout << Tiezi[i]<<" ";if (i % 10 == 9){cout << endl;}}cout << endl;//找水王程序的核心代碼，基本思想為：通過比較，每次刪除兩個不同的ID（不論是否包括水王），在剩下的列表中水王的ID出現次數仍在一半以上int SelectShuiWang; //通過程序找出的“水王”的IDint count=0; //用count記錄“水王”在帖子列表中出現的次數for (int i = 0; i < N; i++){if (0 == count) //如果count為零，則表示當下還未找到真正的“水王”，或“水王”目前出現的次數小于等于其他ID用戶出現的次數{SelectShuiWang = Tiezi[i];count = 1;}else{if (SelectShuiWang == Tiezi[i]){count++;}else{count--;}}}cout << "找水王程序找出的“水王”ID為：" << SelectShuiWang << endl;if (InitShuiWang == SelectShuiWang) //判斷找水王程序是否運行正確，是否能夠找出正確的“水王”ID{cout << "程序運行結果正確！" << endl;}else{cout << "程序運行結果錯誤！" << endl;}cout << endl;return 0; }

??? 程序運行結果截圖如下所示：

???

??? 個人總結：

??? 找水王算法和前段時間寫的動態規劃算法一樣，都是非常經典，非常優化的算法。其實這兩個算法之間有一些想通之處，都采用了一種轉化的方式來把問題簡化。當我們采用傳統的思想思考問題時，雖然實現起來非常簡單，但是那樣的算法使得計算機需要做很多重復的工作。以本道題為例，優化的算法抓住了簡化問題的一個最基本的點，那就是當刪除兩個不同的ID號時，無論水王的ID號在不在這兩個之間，剩下的ID號列表中，水王的ID號仍然占據著一半以上。因此，這樣就可以把列表中的ID號數量逐漸減少，從而提升程序的執行效率。程序就是這樣，采用不同的思想以及不同的算法，有時甚至是幾條不同的語句就能大大改善程序的性能，要想做到這一點，還需要從日后的學習中不斷地積累。

轉載于:https://www.cnblogs.com/hulidanxiang/p/5510148.html

總結

以上是生活随笔為你收集整理的找水王01的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。