Python & C++:鸡兔同笼,方程与枚举哪个更好?

Python & C++ 系列：

学Python的小盆友了解C++；学C++的小盆友了解Python

-典型编程题-

数数，下图有多少只鸡？多少只兔？有多少头？多少脚？列出它们的数量关系式：

10个头，26只脚：

7 + 3 =10；   7*2 + 3*4 = 26

--- 鸡 兔 同 笼 ---

导读：

问题描述

数学题及解法

     • 二元一次方程及其启示

编程题目（与数学题的不同点）

C++编程

 • 方程方法

              · 简单方法

             · 解的合理性判断

       • 枚举算法

             · 双重循环枚举

            · 单循环枚举

            · 无解时的输出提示

Python编程

• 方程方法

       • 枚举算法

              · 双重循环枚举

             · 单循环枚举

运行时间比较

数 学 题 目

鸡兔同笼，一千五百年前《孙子算经》中的经典趣题：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？

即：鸡兔同笼，35头，94足，鸡、兔各有多少？

 数 学 解 法

鸡兔同笼问题有多种解法，例如假设法（“抬腿法”）、方程法，等。

不失一般性，我们用方程解法。分析和求解过程如下：

设鸡x只，兔y只。

“头”的数量约束：

x + y = 35（1）

鸡是2只脚，兔是4只脚，所以，“脚”的数量约束：

2x + 4y = 94 （2）

解出：

x = (4*35 - 94) / 2 = 23  

y = 35 - x = 35 - 23  = 12 

验证

23 + 12 = 35，满足头的数量约束；

2*23 + 4*12 = 94，满足脚的数量约束。

 编 程 题 目

鸡兔同笼，有m个头，n只脚，编写程序，当输入m和n时，输出鸡和兔的数量。

样例输入

35 94

样例输出

23 12

思考：这种编程题与数学题的差别是什么？

  C++编程：方程方法

分析：

如果用x、y分别表示鸡和兔的数量，则有二元一次方程组：

解出：

x = (4m - n ) / 2

y = m - x

根据输入的m、n，计算出x和y，然后输出。

C++方程方法：

程序运行示例：

示例1

示例2

但是，如果输入头的数量m为20，脚的数量n为94，则有：

示例3

程序运行结果：鸡的数量是-7，兔的数量是27。

这当然是不合理的。显然，对于20个头，即使全部是兔子，最多也只能有80只脚！但已知条件给了94只脚！

出现“不合理”解的原因是，上面解方程仅仅是按“等量关系”求解，没有给出其它约束条件。

解决方案：进行合理性判断。例如，如果脚的数量是奇数或者解出的鸡兔数量为负值，都应判为“无解”。

C++方程方法+解的合理性判断

运行示例：

  C++编程： 枚举算法

假设可以全部是兔或鸡，即x和y可以是0。

实现方法1：双重循环枚举

运行示例：

示例1

当输入头的数量m为20，脚的数量n为94时，没有输出，即无解：

示例2

上面不会像解方程那样出现鸡的数量为-7、兔的数量为27的结果，原因是枚举范围是从0到m（头的数）。

其它运行示例：

示例3

示例4

示例5

实现方法2：单重循环枚举

如果没有解时要输出“无解”，可以加上变量标志：

实现方法3：单循环枚举+无解输出提示

运行示例：

示例1

示例2

示例3

  Python编程

Python方程方法

运行示例：

示例1

示例2

示例3

Python双重循环枚举

示例1

示例2

Python单循环枚举

运行示例，同上，（略）。

  方程和枚举，哪个更好？

这是一个算法评价问题。这里不便展开。单单说一下时间。

简单点说，方程的方法是直接计算，而枚举是一个数一个数地进行验证，所以，当数量很大即枚举的范围很大时，枚举将比直接计算花费更多的时间。

为了简便，下面对程序的运行时间做一个大体比较（大体看一下数量级的差别）：

为避免数据输入时间带来的影响，内置数据，值是: m = 100000，n = 300000。先编译运行后，再次直接运行。

使用上面的方程方法，C++程序的运行时间0.01X秒，而双循环枚举的程序运行时间是18.9X秒。每次运行的时间有些差别，但并不影响数量级。

C++方程方法的运行结果：

C++双重循环枚举的运行结果：

虽然上面的时间比较并不精确，但可以从数量级上体现两种方法（算法）耗时的差别。