?前言

讀完這篇博客你可以收獲什么？

①巧妙的遞歸。

②磨煉邏輯推導能力。

③鍛煉將人腦思考過程轉化為計算機語言的能力。

④如何在時間復雜度為 O(n!) 內生成下排列組合數。

話不多說說，偵探們我們這就開始推理。???♂?

???作者概況:? 就讀南京郵電大學努力學習的大一小伙

???聯系方式：2879377052（QQ小號）? ? ? ? ? ? ?

???資源推薦：C語言從入門到進階

???今日書籍分享：??《深入理解計算機系統》? ?? ? 三十天有效

目錄

案件一：誰是兇手？

案件二：誰打碎了花瓶

案件三：確定比賽名次

四、后記

?案件一：誰是兇手？

日本某地發生了一件謀殺案，警察通過排查確定殺人兇手必為4個嫌疑犯的一個。

以下為4個嫌疑犯的供詞:

A說：不是我。

B說：是C。

C說：是D。

D說：C在胡說

已知3個人說了真話，1個人說的是假話。

現在請根據這些信息，寫一個程序來確定到底誰是兇手。

【思路】

①對于計算機而言，最好的推理辦法就是枚舉法，因為只要答案唯一，我們就一定可以得出真相。 所以我們要做的就是枚舉所有的情況。

②再判斷所枚舉的情況是否滿足三個人說真話，三個人說假話的條件

③我們怎么實現判斷說真話的數量呢？很簡單，根據邏輯判斷符，為真則表達式的值為1，為假表達式的值為0，所以我們只要使得最終各個表達式的值相加為3即可得出真相。

【辦案】

int main(){	char killer;	for (killer = "A"; killer <= "D"; killer++)	{		int cnt = 0;		if (killer != "A")			cnt++;		if (killer == "C")			cnt++;		if (killer == "D")			cnt++;		if (killer != "D")			cnt++;		if (cnt == 3)		{			printf("killer = %c", killer); 			break;		}	}	return 0;}

【破案了】

案件二：誰打碎了花瓶

家里有A,B,C,D四個孩子，其中一個孩子把花瓶打碎了。

A說：我沒有打破花瓶。

B說：是我打破的。

C說：不是A打破的。

D說：不是B打破的。

已知，打破花瓶的孩子一定在撒謊，但是其他人不確定。那么，是誰打破了花瓶？

【思路】同案件二的分析，基本思路是枚舉法，所給的條件是打破花瓶的孩子一定在撒謊。但這題其實還有點小技巧，因為沒打破花瓶的人說的話可真可假，所以他們說的話本身沒有意義。

【辦案】

int main(){	char killer = 0;	for (killer = "A"; killer <= "D"; killer++)	{		int ans[4] = { 1,1,1,1 };//默認都說真話		ans[killer - "A"] = 0;//兇手說假話		switch (killer)		{		case "A":			if (ans[killer - "A"] == (killer != "A"))//相等說明沒有矛盾，根據答案唯一可知誰是兇手			{				printf("killer = %c", killer);				goto over;			}			break;		case "B":			if (ans[killer - "A"] == (killer == "B"))			{				printf("killer = %c", killer);				goto over;			}			break;		case "C":			if (ans[killer - "A"] == (killer != "A"))			{				printf("killer = %c", killer);				goto over;			}			break;		case "D":			if (ans[killer - "A"] == (killer != "B"))			{				printf("killer = %c", killer);				goto over;			}			break;		}	}over:	return 0;}

?【破案了】

?

案件三：確定比賽名次

前兩道案件都是開胃菜，用腦子空想都能想出來。但下面這個案件就要復雜的多了

5位運動員參加了10米臺跳水比賽，有人讓他們預測比賽結果：

A選手說：B第二，我第三；

B選手說：我第二，E第四；

C選手說：我第一，D第二；

D選手說：C最后，我第三；

E選手說：我第四，A第一；

比賽結束后，每位選手都說對了一半，請編程確定比賽的名次。

?【思路】雖然題目復雜了很多，但我們依然可以延續案件一的枚舉思想：管他這么多，枚舉就完事了。只要能保證條件——只說對一般即可。

【注意點】枚舉過程中需要注意的一個問題是，名次不能重復，所以在每次枚舉的時候我們首先要保證名次沒有重復，否則continue。

【辦案】

int main(){	int f[6] = {0};	int a = 0, b = 0, c = 0, d = 0, e = 0;	for (a = 1; a <= 5; a++)	{		f[a] = 1;		for (b = 1; b <= 5; b++)        {			if (f[b])				continue;			f[b] = 1;			for (c = 1; c <= 5; c++)			{				if (f[c])					continue;				f[c] = 1;				for(d = 1; d <= 5; d++)				{					if (f[d])						continue;					f[d] = 1;					for (e = 1; e <= 5; e++)					{						if (f[e])							continue;						if ((b == 2) + (a == 3) == 1 && //B第二，我第三							(b == 2) + (e == 4) == 1 && //我第二，E第四							(c == 1) + (d == 2) == 1 && //我第一，D第二							(c == 5) + (d == 3) == 1 && //C最后，我第三							(e == 4) + (a == 1) == 1) //我第四，A第一						{							printf("a = %d, b = %d, c = %d, d = %d, e= %d",a,b,c,d,e);							goto over;//跳出多重循環用goto最好						}						f[e] = 0;						break;					}					f[d] = 0;				}				f[c] = 0;			}			f[b] = 0;		}		f[a] = 0;	}over:	return 0;}

【破案了】

?案子雖然是結了，但上面的代碼寫的也太矬了，怎么能體現出優秀程序員的深厚功底呢？我們來試著改進一下。

【改進①】

上面判斷是否重復的過程實際是哈希表思想的運用，即數組下標與元素一一映射，不太會，看看這篇博客【跟著英雄學算法第⑤天】計數法——附Leetcode刷題題解（C語言實現）。

但是，我們注意到判斷是否重復只有兩種情況，用01即可一反映，沒必要用一個數組去存儲。因此我們可以聯想二進制，用一個數的二進制某一位為0還是1反映是否重復。這里運用到哈希中的位圖。將原來需要一個數組的空間壓縮到只需要一個int即可。

（我們這里封裝一個函數來實現，每次判斷時調用函數即可）

int check_data(int*p){	int tmp = 0;	for (int i = 0; i < 5; i++)	{		tmp |= 1 << (p[i] - 1);	}	return tmp == 0B11111;        //tmp每次或上一位1，p[i]如果是1~5都有，則1<<1到1<<5都或上的結果將會是00111110，如果有并列，則一定會至少卻其中一個1，結果就不會是00111110，所以可以判斷tmp最終的結果是不是這個數字來判斷有沒有重復。}

?【改進②】

上面循環的代碼看起來很冗長，但其實本質上有很多的代碼都是重復的，因此我們可以使用遞歸思想來減少代碼。

int check_data(int*p){	int tmp = 0;	for (int i = 0; i < 5; i++)	{		tmp |= 1 << (p[i] - 1);	}	return tmp == 0B11111;}void diveRank(int* p, int n){	if (n >= 5)	{		if (!check_data(p))			return;		if ((p[1] == 2) + (p[0] == 3) == 1 && 			(p[1] == 2) + (p[4] == 4) == 1 && 			(p[2] == 1) + (p[3] == 2) == 1 && 			(p[2] == 5) + (p[3] == 3) == 1 && 			(p[4] == 4) + (p[0] == 1) == 1)   		{			for (int i = 0; i < 5; i++)			{				printf("%d ", p[i]);			}			putchar("/n");		}		return;	}	for (p[n] = 1; p[n] <= 5; p[n]++)	{		diveRank(p,n + 1);	}}int main(){	int p[5] = {0};	diveRank(p, 0);	return 0;}

【理解】

遞歸時一層一層理解。首先生成p[0]，p[0]有1~5五種取法，對于每一種取法p[1]也有5種取法，依次類推，實現【辦案】中的循環效果。

【究極改進】

遞歸雖然使得代碼行數看起來更少，但是時間復雜度仍然是O(n^n)，那如何降低到O(n!)呢？我們可以進一步優化遍歷方式，每次直接生成1~5的全排列數

先上代碼，可能有點難理解。

void swapArgs(int* a, int* b) //交換函數{	int tmp;	tmp = *a;	*a = *b;	*b = tmp;}void diveRank(int* p, int n){	if (n >= 5) //此時的n也是用來控制循環層數的。	{		if ((p[1] == 2) + (p[0] == 3) == 1 && //B第二，我第三			(p[1] == 2) + (p[4] == 4) == 1 && //我第二，E第四			(p[2] == 1) + (p[3] == 2) == 1 && //我第一，D第二			(p[2] == 5) + (p[3] == 3) == 1 && //C最后，我第三			(p[4] == 4) + (p[0] == 1) == 1)   //我第四，A第一			//由于此時是執行的全排列，所以查重也省了。		{			for (int i = 0; i < 5; i++)			{				printf("%d ", p[i]);			}			putchar("/n");		}		return;	}	int i;	for (i = n; i < 5; i++) //這個遞歸方式就完成了對1~5的全排列，方法是從后向前不停的執行交換。可以參考改進二和原代碼，將這個遞歸程序寫回成循環后，可以更好的理解。	{		swapArgs(p + i, p + n);		diveRank(p, n + 1);		swapArgs(p + i, p + n);	}}int main(){	int p[5] = { 1, 2, 3, 4, 5 }; //當然由于是全排列，所以初值必須給好。	diveRank(p, 0);	return 0;}

【理解】

?在核心代碼處我分別打印交換時的i，n的值，第一次交換后第二次的序列，以及每次 n >= 5時進入判斷語句參與判斷的序列。

?【分析】

我們首先來分析如何生成組合數。

給我們兩個數字1 2，顯然組合只有兩種情況 ：1 2 和 2 1；

給我們三個數字1 2 3，顯然組合有六種情況：1 2 3 ，1 3 2，2 1 3，2 3 1， 3 1 2， 3 2 1

給我們四個數字1 2 3 4，組合情況怎么看呢：

當我們確定第一個數字為1 ，后面三個數字的排列方式不是和 1 2 3模式相同嗎，依次類推，就產生了我們的遞推思想。

在這里n控制著循環的層數。

（1）從n = 0到n = 4，我們一口氣進入了第五層循環，由于 i = n = 4 相當于給我們五個數字，確定前四個數字，排列的方式顯然是惟一的為1 2 3 4 5。

（2）當從第四層循環回到第三層循環時，i = n = 3，，相當于先確定前面三個數字，那么 4 5互換產生了新的排列方式

（3）最后分析第三層循環回到第二層循環時，i = n = 2，相當于確定前面的兩個數字，那么 3 4 5之間是可以互換的。而3 4 5之間的互換與（2）中的互換方式是一致的

相信講到這里大家理解了互換的模式。?

【問】為什么要執行這兩條效果相反的語句呢？

【答】每次從循環中出來時排列都會被還原為 1 2 3 4 5，這樣就不會對下一次的遞歸產生影響，所以說每一次的序列肯定都是獨一無二的，因為都是從一個爐子里以不同的方式捏出來的。

?

?四、后記

? ? ? ? 有同學肯定會說，寫完這段代碼游戲早就結束了，你這么一說，好像是誒，但學習到知識才是我們的初心（強行解釋），難道不是嗎？

?