C++经典问题算法分析

C++经典算法详解 半地沙子2013-10

一、百钱买百鸡问题（枚举算法）

★算法分析：1、对百钱买百鸡问题的所有结果进行逐一统计验证（枚举验证）。 2、公鸡最多只能买20只，母鸡最多只能买33只，小鸡最多只能

买300只。

3、用for循环进行逐一验证

4、对小鸡的费用应用x/3代替x*(1/3)，因为1/3在整型变量下的

值为0。

5、需保证小鸡的数量是3的倍数，即x%3==0。 ★源代码：

图1-1

★执行结果：

- 1 -

C++经典算法详解 半地沙子2013-10

图1-2

二、填写运算符问题（枚举算法）

★算法分析：1、5个数字需要填入4个运算符。

2、每两个数字之间有4种运算符可以选择。 3、当运算符中填入除号时，右边的被除数不能为0. 4、乘除的优先级大于加减的优先级。 5、可以用循环的方法逐一填入各种运算符。 ★源代码：

- 2 -

C++经典算法详解 半地沙子2013-10

图2-1

三、汉诺塔问题（递归算法）

★算法分析：1、汉诺塔问题可以运用递归算法解决。

2、递归是函数本身调用直接或者间接调用自己的方法。 3、在汉诺塔问题中需要的步骤数是2^n-1。 4、汉诺塔问题步骤解析：

（1）把1座上（n-1）个盘子借助3座移动到2座。 （2）把1座上的第n个盘子移动到3座。

（3）把2座上的（n-1）个盘子借助1座移动到3座。 （4）我们假设用h（n，a，b，c）表示把1座n个盘子借助2 座移动到3座。由此可得出结论：（1）上是h（n，1,3,2）, (2)上是（n-1，2,1,3）

- 3 -

C++经典算法详解 半地沙子2013-10

★源代码：

图3-1

★执行结果：

图3-2

★形象示例：

- 4 -

C++经典算法详解 半地沙子2013-10

ABC

图3-3

★故事缘由：

据说古代有一个梵塔，塔内有3个座A、B、C。A座上有64个圆盘，盘子大小不等，大的在下，小的在上。有一个和尚想把这64个盘子从A座移动到C座，但每次只能移动一个圆盘，并在移动过程中始终保持大盘在下，小盘在上。在移动过程中只能利用B座。现在需要写出移动的步骤。这就是汉诺塔问题。

当时这个和尚觉得很难，于是他想，要是有一个人能把前面的63个圆盘移动到B座，自己再把最后一个圆盘移动到C座，那就简单了。所以他找了另一个和尚来做这件事。但是另一个和尚也觉得很难，于是又找来了第三个和尚把B座上的前62个圆盘移动到A座上，自己再把第63个盘子移动到C座。一次类推，解决汉诺塔问题，一共有64个和尚参与了这项题目。即是如此，不难看出，每个和尚所做的事是一样的，这就是说解决汉诺塔问题有一种简单而高效地方法，那就是递归调用。所谓递归调用，就是函数本身直接或间接的调用自己的方法。递归算法，也是九大经典算法之一。

但是当时没有那么多和尚来完成这件事，确切的说，只能有他自己一个和尚来完成这件事，于是他想起了一位美国学者所发现的一种非常简单的方法。首先把3个座排列成品字形，如果圆盘的数字是偶数，就按顺时针方向依次排列成A、

- 5 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库C++经典问题算法分析在线全文阅读。