C++经典问题算法分析

1、C+C+2013-10- 1 - 1 -一、百钱买百鸡问题（枚举算法）算法分析：1、对百钱买百鸡问题的所有结果进行逐一统计验证（枚举验证。2、公鸡最多只能买 20 只，母鸡最多只能买 33 只，小鸡最多只能买 300 只。3、用 for 循环进行逐一验证4、对小鸡的费用应用 x/3 代替 x*(1/3)，因为 1/3 在整型变量下的值为 0。5、需保证小鸡的数量是 3 的倍数，即 x%3=0。源代码：图 1-1执行结果：C+C+2013-10图 1-2二、填写运算符问题（枚举算法）算法分析：1、5 个数字需要填入 4 个运算符。2、每两个数字之间有 4 种运算符可以选择。3、当运算符中填入除号

2、时，右边的被除数不能为 0.4、乘除的优先级大于加减的优先级。5、可以用循环的方法逐一填入各种运算符。- 2 -源代码：- 2 -C+C+2013-10- - PAGE 11 -图 2-1图 2-1三、汉诺塔问题（递归算法）算法分析：1、汉诺塔问题可以运用递归算法解决。2、递归是函数本身调用直接或者间接调用自己的方法。3、在汉诺塔问题中需要的步骤数是 2n-1。4、汉诺塔问题步骤解析：1（n-1）321n32（n-1）131n3（1）h（，2）, (2)上是（n-1，2,1,3）源代码：图 3-1执行结果：图 3-2形象示例：ABC图 3-3故事缘由：3ABCA6464AC B63动到 B 座

3、，自己再把最后一个圆盘移动到 C 座，那就简单了。所以他找了另一B 62 个圆盘移动到A63C64每个和尚所做的事是一样的，这就是说解决汉诺塔问题有一种简单而高效地方 3ABC。如果圆盘的数量是奇数是，就按顺时针排列成AC。开始时按顺时1A 上，则把它移动到B 座。若圆盘在B 座，则把它移动到CC 座，则把它移动到 A 座。接着，把另外两座上可以移动的圆盘移动到新的座3移动方向是 A-C、A-B、C-B、A-C、B-A、B-C、A-C。其实这也是汉诺塔问题的非递归算法。四、阶乘问题（递归算法）算法分析：1、阶乘（factorial）是基斯顿卡曼于 1808 年发明的运算符号。2、阶乘可用自身调

4、用自身的递归调用方法解决。源代码：图 4-1执行结果：图 4-2五、水仙花数问题算法分析：1、所谓水仙花数，就是一个三位数，其各位数字立方和等于该数本身。例如 153 就是一个水仙花数。2、关于求一个三位数的各个位数的问题。百位数可以直接用该数100型数字，即百位数。同理，十位数可以用先除1010103、关于立方的计算，可以直接三个数相乘，也可以调用cmath 库函数进行求解。源代码 1：图 5-1执行结果 1：5-25-3源代码 2：图 6-1执行结果 2：图 6-2六、最大公约数与最小公倍数问题算法分析：1、计算两个数的最大公约数比较简单的方法是从两个数较小的那个数字中开始依次递减，得到的

5、这两个数中第一个公因子即为所求的最大公约数。2、计算两个数的最小公约数比较简单的方法是从两个数中较大的那个数字开始一次加 1，得到的第一个公倍数就是两数的最小公倍数。3、如果iaba%i=0b%i=0。所以在算法优化中只需要 i 从 mi（a，b）1i 是不是 a 和 b 的公因数，这样得到的第一个公因数就是其最大公约数。4、最小公倍数的求解与 3 一致。5、跳出一重循环可以在循环体判断条件中添加 break 语句。源代码：图 7-1执行结果：图 7-2七、哥德巴赫猜想问题算法分析：1、所谓的哥德巴赫猜想是指每一个大于 2 的偶数都可以表示成两个素数之和。我国数学家陈景润曾经作出重要的贡献。2

6、、不可能对所有偶数进行举例（是无穷的。3、判断一个偶数a 是不是可以表示成两个素数的和是本算法的核C+C+2013-10aa/2= a/2+(a-a/2a/2形式。所以在这 a/2 种形式中只要有一种满足两数皆是素数时即可证明哥德巴赫猜想的正确性。算法：验证哥德巴赫猜想的正确性输入：一个数 ii ？Repeat：If i 是素数 and a-i 是素数Then 设置标志，跳出循环Endif Ia/2Else a 不满足哥德巴赫猜想End loop End- 12 - 12 -C+C+2013-10- - PAGE 45 -图8-1图8-2八、完全数问题算法分析：1、完全数是满足所有的真因子（除

7、自身外的约数）的和等于它本身。例如 6 是完全数，即 6=1+2+3。2、判断完全数，需要找出数的所有约数，约数是所求数能被除尽的所有数。所以只要找出所有约数即可。3、完全数的性质：（1）能写成连续自然数之和。例如 6=1+2+3。（2）全部因数的倒数和为 2。例如 1+1/2+3/1+1/6=2。628=13+33。228 = 22 23+24。68除 6 以外的完全数，把它的各个位数相加，直到变成个169191。数学家欧几里得推算出来的完全数获得公式：如果2p-1 是质数时，称梅森素数。图 9-1执行结果：图 9-2九、素数问题算法分析：1、素数又称质数，是指除了 1 及其本身之外没有任何

8、约数的数。2、比 1 大但还不是质数的称为合数。3、0 和 1 既不是素数也不是合数。源代码 1：图 10-1执行结果 1：图 10-2源代码 2：图 12-1执行结果 2：图 12-2十、一元二次方程问题算法分析：1、一元二次方程寻找解的方法可以用公式法。2、用判别式判断解集的情况。3、用 if else 语句实现其分支判断。源代码：图 11-1执行结果：11-211-3十一、学生管理系统（结构体编程）算法分析：1、学生管理系统需要利用结构体对学生的数据进行输入和存储。2、本题主要是用于考擦对结构体的熟练程度。3、需要用排序对学生的成绩进行排序。本例子利用冒泡排序法进行排序。源代码：图 13

9、-1执行结果：图 13-2十二、冒泡排序问题算法分析：1、所谓冒泡排序法，就是利用比较相邻的两个数字的大小并对其进行大小的排序。2、对一组数据进行冒泡排序，可以利用二重循环进行比较。一重循环用来决定所要两两比较的次数，二重循环用来进行两两之间的比较。如果是升序排序，那么在两两比较的时候把大的数字放在小的数字后面，如果是降序排序，与升序排序相反。源代码 1：图 14-1执行结果 1：图 14-2源代码 2：图 15-1执行结果 2：图 15-2图 15-2十三、选择排序问题算法分析：1、选择排序算法是排序的经典算法之一，其运行效率与冒泡排序相当。2、选择排序的算法思路：n第二趟，最小值的标记位置

10、往下一个位置移动。重复进行上述（1）-（3）的操作。图 16-1图 16-1执行结果：图 16-2十四、直接插入排序问题算法分析：1、直接插入排序是一种最直接的插入排序方法，能够将第 n 个记录插入到前面 n-1 个已排好的原始序列记录中。2nn 个的数据mn源代码：图 17-1图 17-2十五、树形选择排序问题算法分析：1、树形选择排序也称为锦标赛排序。2、树形选择排序的算法思路：n在 n/2小者。重复上述动作，知道选出最小关键字的记录为止。3、树形排序的解决方法：我们可以用一棵有n 个结点的树来选出的最小关键字记录的结点就是这棵树的根结点。当输出最小关键字以后，为了选出次小关键字，可以将设

11、置结点即最小关键字所对应的叶子结点的关键字值设为正无穷，然后再进行上述过程，直至所有的记录全部输出为止。十六、平方根问题（迭代算法）：1、求平方根的迭代公式：x1=1/2(x0+a/x0)。2、也可以直接调用 cmath 函数库进行求解。源代码 1：图 18-1执行结果 1：18-218-3源代码 2：图 19-1执行结果 2：19-219-3十七、创建链表问题算法分析：1、链表是一种不同于数组的的新的数据存储结构。2、链表包含了头结点、头指针、尾结点、尾指针。链表只需要一个变量，即头指针即可确定一个链表。3、定义一个链表可以使用结构体进行定义。源代码：图 20-1十八、八皇后问题（试探算法）

12、算法分析：1、八皇后问题是一个古老而著名的问题，是典型的试探算法的例子。所谓的八皇后问题，是由191850工解决：在 8*8 格的国际象棋棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后不能处于同一行、同一列或同一斜线上，问总共有多少种解决方法。十九、鸡兔同笼问题、鸡兔同笼问题概述3594问笼子中各有几只鸡、几只兔子。2、鸡兔同笼问题可借用一元二次方程思想进行求解。3、一只鸡、一只兔子各有一个头、一只鸡有两只脚、一只兔子有四只脚。所以总数是 35。源代码：21-121-221-3二十、十数排序问题（面向对象编程）算法分析：1、用类的方法对十个数据进行编程表示。源代码：图 23-1二十一、模

13、拟简单计算器问题 源 代 码 ： #includeiostream.h #includemath.h #includestdlib.h static double t1=0;/*/*基类定义为一个计算器类 calculator*/class calculator private:char k3; public:double k1,k2,result;calculator(double x,double y,char z)k1=x;k2=y;k3=z;/*基类构造函数初始化 calculator 成员数据*/double operators(double a1,double a2,char a3

14、);/*/ class A:virtual public calculator/*派生类 re 接口,用于对基类运算的结果进行再操作*/ private :public:char k5; double k6,t;void recalculate(double k)/*派生类构造函数对首次的结果进行录入*/t=k;void regaindata()/*再次操作的数据录入工作*/coutk5;coutk6;/*进行再次计算*/void recalculating()operators(t,k6,k5);/*调用基类成员函数进行计算操作*/;/*/double calculator:operator

15、s (double a1,double a2,char a3)/*基类成员函数对运算符进行检验并运算，若出现错误则标记 0 */switch(a3) case +:result=k1+k2; returnresult;break;case -:result=k1-k2; returnresult;break;case *: result=k1*k2; return result;break;case /:result=k1/k2; returnresult;break;default:cout运算符输入错误！endl;return 0;/*/*是否进行结果再操作的判断函数 redo()*/ void redo(double r)couta4;double r1; char r2;/*用于记录新的操作数和运算符*/if(a4=Y | a4=y)coutr1;coutr2;calculator obj(t1,r1,r2);coutt1r2 t1=obj.operators(t1,r1,r2); elsecout已经退出计算器endl;r1exit(0);/*/ int main()/* 主函数接口 */double a1,a2; char a3;c