找水王01

    題目：

    三人行設計了一個灌水論壇。資訊學院的學生都喜歡在上面交流灌水，傳說在論壇上有一個“水王”，他不但喜歡發帖，還會回複其他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 100

int main()
{
	srand((int)time(NULL));               //定義時間種子

	int InitShuiWang = 0 + rand() % 10;   //假設文章清單中有10個ID号，分别用0-9這十個數字字元代替，自定義“水王”的ID
	cout << "自定義的“水王”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;                //通過程式找出的“水王”的ID
	int 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号數量逐漸減少，進而提升程式的執行效率。程式就是這樣，采用不同的思想以及不同的算法，有時甚至是幾條不同的語句就能大大改善程式的性能，要想做到這一點，還需要從日後的學習中不斷地積累。