C++ 算法设计:鸡兔同笼问题的多种求解方法

C++ 算法设计:鸡兔同笼问题的多种求解方法

问题:

今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何?编程求雉兔各几何。

解法1:人肉计算机

手工解方程,程序直接输出答案,这是最短的程序,没有之一。

#include

using namespace std;

int main()

{

cout << "chickens = 23" << endl;

cout << "rabbits = 12" << endl;

return 0;

}

解法2:方程求解

当然,也可以让计算机解方程,省去手工计算的工作量。

#include

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

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

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

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

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表达式进一步化简,但对于初学者,意义不大了,有兴趣自己搞一下。

相关文章

🪶
伏地魔为什么没有鼻子
线上365bet正网

伏地魔为什么没有鼻子

07-31 👀 3432
🪶
dnf幻影之灵价格(dnf幻影之灵售价一览)
🪶
手机丢失以后,需要马上做的5件事
s365app下载

手机丢失以后,需要马上做的5件事

08-20 👀 7210