?前言

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

①巧妙的遞歸。

②磨煉邏輯推導(dǎo)能力。

③鍛煉將人腦思考過程轉(zhuǎn)化為計(jì)算機(jī)語言的能力。

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

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

???作者概況:? 就讀南京郵電大學(xué)努力學(xué)習(xí)的大一小伙

???聯(lián)系方式：2879377052（QQ小號）? ? ? ? ? ? ?

???資源推薦：C語言從入門到進(jìn)階

???今日書籍分享：??《深入理解計(jì)算機(jī)系統(tǒng)》? ?? ? 三十天有效

目錄

案件一：誰是兇手？

案件二：誰打碎了花瓶

案件三：確定比賽名次

四、后記

?案件一：誰是兇手？

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

以下為4個(gè)嫌疑犯的供詞:

A說：不是我。

B說：是C。

C說：是D。

D說：C在胡說

已知3個(gè)人說了真話，1個(gè)人說的是假話。

現(xiàn)在請根據(jù)這些信息，寫一個(gè)程序來確定到底誰是兇手。

【思路】

①對于計(jì)算機(jī)而言，最好的推理辦法就是枚舉法，因?yàn)橹灰鸢肝ㄒ?，我們就一定可以得出真相?所以我們要做的就是枚舉所有的情況。

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

③我們怎么實(shí)現(xiàn)判斷說真話的數(shù)量呢？很簡單，根據(jù)邏輯判斷符，為真則表達(dá)式的值為1，為假表達(dá)式的值為0，所以我們只要使得最終各個(gè)表達(dá)式的值相加為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四個(gè)孩子，其中一個(gè)孩子把花瓶打碎了。

A說：我沒有打破花瓶。

B說：是我打破的。

C說：不是A打破的。

D說：不是B打破的。

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

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

【辦案】

int main(){	char killer = 0;	for (killer = "A"; killer <= "D"; killer++)	{		int ans[4] = { 1,1,1,1 };//默認(rèn)都說真話		ans[killer - "A"] = 0;//兇手說假話		switch (killer)		{		case "A":			if (ans[killer - "A"] == (killer != "A"))//相等說明沒有矛盾，根據(jù)答案唯一可知誰是兇手			{				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;}

?【破案了】

?

案件三：確定比賽名次

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

5位運(yùn)動(dòng)員參加了10米臺跳水比賽，有人讓他們預(yù)測比賽結(jié)果：

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

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

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

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

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

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

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

【注意點(diǎn)】枚舉過程中需要注意的一個(gè)問題是，名次不能重復(fù)，所以在每次枚舉的時(shí)候我們首先要保證名次沒有重復(fù)，否則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;//跳出多重循環(huán)用goto最好						}						f[e] = 0;						break;					}					f[d] = 0;				}				f[c] = 0;			}			f[b] = 0;		}		f[a] = 0;	}over:	return 0;}

【破案了】

?案子雖然是結(jié)了，但上面的代碼寫的也太矬了，怎么能體現(xiàn)出優(yōu)秀程序員的深厚功底呢？我們來試著改進(jìn)一下。

【改進(jìn)①】

上面判斷是否重復(fù)的過程實(shí)際是哈希表思想的運(yùn)用，即數(shù)組下標(biāo)與元素一一映射，不太會(huì)，看看這篇博客【跟著英雄學(xué)算法第⑤天】計(jì)數(shù)法——附Leetcode刷題題解（C語言實(shí)現(xiàn)）。

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

（我們這里封裝一個(gè)函數(shù)來實(shí)現(xiàn)，每次判斷時(shí)調(diào)用函數(shù)即可）

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都或上的結(jié)果將會(huì)是00111110，如果有并列，則一定會(huì)至少卻其中一個(gè)1，結(jié)果就不會(huì)是00111110，所以可以判斷tmp最終的結(jié)果是不是這個(gè)數(shù)字來判斷有沒有重復(fù)。}

?【改進(jìn)②】

上面循環(huán)的代碼看起來很冗長，但其實(shí)本質(zhì)上有很多的代碼都是重復(fù)的，因此我們可以使用遞歸思想來減少代碼。

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;}

【理解】

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

【究極改進(jìn)】

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

先上代碼，可能有點(diǎn)難理解。

void swapArgs(int* a, int* b) //交換函數(shù){	int tmp;	tmp = *a;	*a = *b;	*b = tmp;}void diveRank(int* p, int n){	if (n >= 5) //此時(shí)的n也是用來控制循環(huán)層數(shù)的。	{		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第一			//由于此時(shí)是執(zhí)行的全排列，所以查重也省了。		{			for (int i = 0; i < 5; i++)			{				printf("%d ", p[i]);			}			putchar("/n");		}		return;	}	int i;	for (i = n; i < 5; i++) //這個(gè)遞歸方式就完成了對1~5的全排列，方法是從后向前不停的執(zhí)行交換?？梢詤⒖几倪M(jìn)二和原代碼，將這個(gè)遞歸程序?qū)懟爻裳h(huán)后，可以更好的理解。	{		swapArgs(p + i, p + n);		diveRank(p, n + 1);		swapArgs(p + i, p + n);	}}int main(){	int p[5] = { 1, 2, 3, 4, 5 }; //當(dāng)然由于是全排列，所以初值必須給好。	diveRank(p, 0);	return 0;}

【理解】

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

?【分析】

我們首先來分析如何生成組合數(shù)。

給我們兩個(gè)數(shù)字1 2，顯然組合只有兩種情況 ：1 2 和 2 1；

給我們?nèi)齻€(gè)數(shù)字1 2 3，顯然組合有六種情況：1 2 3 ，1 3 2，2 1 3，2 3 1， 3 1 2， 3 2 1

給我們四個(gè)數(shù)字1 2 3 4，組合情況怎么看呢：

當(dāng)我們確定第一個(gè)數(shù)字為1 ，后面三個(gè)數(shù)字的排列方式不是和 1 2 3模式相同嗎，依次類推，就產(chǎn)生了我們的遞推思想。

在這里n控制著循環(huán)的層數(shù)。

（1）從n = 0到n = 4，我們一口氣進(jìn)入了第五層循環(huán)，由于 i = n = 4 相當(dāng)于給我們五個(gè)數(shù)字，確定前四個(gè)數(shù)字，排列的方式顯然是惟一的為1 2 3 4 5。

（2）當(dāng)從第四層循環(huán)回到第三層循環(huán)時(shí)，i = n = 3，，相當(dāng)于先確定前面三個(gè)數(shù)字，那么 4 5互換產(chǎn)生了新的排列方式

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

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

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

【答】每次從循環(huán)中出來時(shí)排列都會(huì)被還原為 1 2 3 4 5，這樣就不會(huì)對下一次的遞歸產(chǎn)生影響，所以說每一次的序列肯定都是獨(dú)一無二的，因?yàn)槎际菑囊粋€(gè)爐子里以不同的方式捏出來的。

?

?四、后記

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

?