第一部分 实验内容 1．实验目标 （1）熟悉使用回溯法求解问题的基本思路。 （2）掌握回溯算法的程序实现方法。 （3）理解回溯算法的特点。 2. 实验任务 （1）从所给定的题目中选择一题，使用回溯法求解之。 （2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。 （3）在Windows环境下使用C/C++语言编程实现算法。 （4）记录运行结果，包括输入数据，问题解答及运行时间。 （5）分析算法最坏情况下时间复杂度和空间复杂度。 （6）谈谈实验后的感想，包括关于该问题或类似问题的

[例1]用递归函数求n! 分析： n!可以由下列公式表示： 1 n=0 n!= n*(n-1)! n>0 根据数学中的定义把求n! 定义为求n*(n-1)! ,其中求(n-1)! 仍采用求n! 的方法，需要定义一个求a！的过程或函数，逐级调用此过程或函数，即： (n-1)!= (n-1)*(n-2)! ; (n-2)!= (n-2)*(n-3)! ; …… 直到n=0时给出0!=1，才开始逐级返回并计算各值。 ①定义递归函数：fac(