实验目的：

●理解基本的算法思想；

●理解常用算法程序的设计思路；

●了解程序算法在实际问题中的应用；

●掌握穷举、递推、迭代和递归算法的基本结构。

必做题：

【实验11-1】使用穷举法求解：现有面值为1元、2元和5元的钞票（假设每种钞票的数量都足够多），从这些钞票中取出30张使其总面值为100元，并且每种面额的钞票至少要有一张。求有多少种取法，并输出每种取法中各种面额钞票的张数。程序保存为Experiment11_1.java。

提示：1元的张数y1为1～30张；2元的张数y2为1～30张；5元的张数y5=30-y2-y1。满足题目的条件为y1+2*y2+5*y5==100。

【实验11-2】使用递推法求解：输出一数列的前n项。该数列的第1，2，3项为1，以后的各项是其前3项的和。即1，1，1，3，5，9，17，31，…。请计算并显示出该数列的前30项。程序保存为Experiment11_2.java。

提示：递推方法是n4=n3+n2+n1。

选做题：

【实验11-3】使用递归方法求解实验11-2。程序保存为Experiment11_3.java。

提示：参考以下实现递归的方法。

【实验11-4】使用牛顿迭代法求解方程：x³-x²-x-1=0。要求计算精度达到10^-10。程序保存为Experiment11_4.java。

提示：牛顿迭代公式是x=x0-f（x0）/′f（x0），本题有如下公式。

主要代码提示：(www.daowen.com)

【实验11-5】编写程序，计算π的近似值。分别计算出前100，10000，1000000项时π的值。程序保存为Experiment11_5.java。π≈4（1/1-1/3+1/5-1/7+1/9-…）。

提示：

1.递推关系：前一项1/i，后一项有1/（i+2）。

2.正负符号变化，可以设定变量n=1，在循环时使用n=-n产生+1和-1的变化。

实验要点：完成本实验时，请注意以下几个问题。

1.注意分析问题，选择合适的算法。

2.穷举法是将所有的可能都进行枚举，找出与条件相符的结果。

3.递推法是在需要若干步骤完成的推算中，找出相邻两个步骤之间的关系，进行递推。

4.递归法是设计一个方法，将求解规模n分解为小于n的规模，通过自我调用完成计算。

5.如果牛顿迭代法计算无法收敛，可以适当修改x的初值。

总结思考：

1.写出实验11-1，实验11-2的程序设计思路。

2.什么是递推法？应用递推法应该注意什么？

3.什么是递归法？应用递归法应该注意什么？