C++ 演演算法設計：雞兔同籠問題的多種求解方法

問題：

今有雉兔同籠，上有三十五頭，下有九十四足，問雉兔各幾何？程式設計求雉兔各幾何。

解法1：人肉計算機
手工解方程，程式直接輸出答案，這是最短的程式，沒有之一。

#include <iostream>
using namespace std;
int main()
{
	cout << "chickens = 23" << endl;
	cout << "rabbits  = 12" << endl;
	return 0;
}

解法2：方程求解
當然，也可以讓計算機解方程，省去手工計算的工作量。

#include <iostream>
using namespace std;
int main()
{
	int m = 35;
	int n = 94;
	/*
		 x +  y = m
		 2x + 4y = n
	 */
	int x = (4 * m - n) / 2;
	int y = m - x;
	cout << "chickens = " << x << endl;
	cout << "rabbits  = " << y << endl;
	return 0;
}

解法3：暴力搜尋
再省點事，方程也不需要我們來變換，直接讓計算機逐個答案試探，反正計算機計算速度快，只要我們少動腦筋就行。

#include <iostream>
using namespace std;

int main()
{
	for (int x = 0; x <= 35; ++x)
	{
		for (int y = 0; y <= 35; ++y)
		{
			if (x + y == 35 && x * 2 + y * 4 == 94)
			{
				cout << "chickens = " << x << endl;
				cout << "rabbits  = " << y << endl;
				return 0;
			}
		}
	}
	cout << "unsolvable!" << endl;
	return 0;
}

解法4：啟發式搜尋
其實上面的程式中，y不用迴圈，因為 y=35-x，這樣只需要 x 迴圈 36 次就能把答案找出來，速度比上面提高 36 倍。儘管計算機速度很快，我們還是儘可能減少不必要的搜尋工作。

#include <iostream>
using namespace std;
int main()
{
	for (int x = 0; x <= 35; ++x)
	{
		int y = 35 - x;
		if (x * 2 + y * 4 == 94)
		{
			cout << "chickens = " << x << endl;
			cout << "rabbits  = " << y << endl;
			return 0;
		}
	}
	cout << "unsolvable!" << endl;
	return 0;
}

解法5：隨機求解
如果你對求x，y沒思路，可以分析一下它們的取值範圍，然後在取值範圍內隨機取值，然後檢驗一下這組隨機值是否為符合答案要求，如果符合的話，問題就搞定了。

別看不起隨機求解，很多複雜演演算法都用到了這種技巧，用的好的話，能解決很多無法用公式求解的難題。正所謂亂拳打死師傅啊！

#include <iostream>
using namespace std;
int main()
{
	while (true)
	{
		int x = rand() % 36;
		int y = rand() % 36;
		if (x + y == 35 && 2 * x + 4 * y == 94)
		{
			cout << "chickens = " << x << endl;
			cout << "rabbits  = " << y << endl;
			return 0;
		}
	}
	return 0;
}

解法6：燒腦筋求解方法
我覺得不炫耀一下技巧，顯得太 low 了，用遞迴方法給出一段程式碼，慢慢燒腦筋去吧！

#include <iostream>
using namespace std;
int chickens(int m, int n)
{
	return 4 * m <= n ? 0 : 1 + chickens(m - 1, n - 2);
}
int main()
{
	cout << "chickens = " << chickens(35, 94) << endl;
	cout << "rabbits  = " << 35 - chickens(35, 94) << endl;
	return 0;
}

還可以利用 lambda表示式進一步化簡，但對於初學者，意義不大了，有興趣自己搞一下。