问答题 编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。

问答题 在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1（x），表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。 请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。

问答题 设数组A有n个元素，需要找出其中的最大最小值。 （1）请给出一个解决方法，并分析其复杂性。 （2）把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。