数据结构（Java语言版）实验指导书-递归实验.docx

递归实验答案public class 实验 5_1 static int dp = new int 100;public static int solvel (int n)/解法1(if (n = 1) return 1;if (n = 2) return 2;return solvel(n - 1) + solvel(n - 2);public static int solve2 (int n)/解法 2(if (dpn != 0) return dpn;if (n = 1) dpl = 1；return dp1;)if (n = 2) dp 2 =2;return dp2;)dpn = solve2(n - 1) + solve2(n - 2); return dpn;)public static int solve3 (int n)/解法 3(dpl = 1;dp 2 = 2;for (int i = 3; i <= n; i + + )dpi = dpi - 1 + dpi - 2; return dpn;public static int solve4 (int n)/解法 4(int a=1;/对应 f (n-2)int b=2;/对应 f (nl)int c=0;/对应 f (n)if (n = 1) return 1;if (n = 2) return 2;for (int i = 3; i <= n; i+) c = a + b;a = b;b = c;)return c;public static void main(String args) int n = 10;System.out.printf("n n=%dnHr n);System. out .printf ( n解法 1: %dnn,System, out .printf ("解法 2 : %dnn,System, out .printf (" 解法 3 : %dnH,System.out.printf (H角转去 4: %dn"rsolvel(n);solve2(n);solve3(n);solve4(n);public class 实验 5_2 static int N= 21;static int q = new intN;static int n;/n为存放实际皇后个数static int ent= 0;/累计解个数public static void dispasolution ()/输出 n 皇后问题的一个解(System. out .print f ("第( 个解：”, +cnt);for (int i = 1; i <= n; i+)System.out.printf(" (%d,%d)", i, qi);System.out.printin();)public static int abs (int x)return x > 0 ? x : -x;)public static boolean place (int i,int ') /测试(i/j)位置能否摆放皇后if (i = 1) return true;int k = 1;while (k < i)(if (qk = j) | (abs(qk/第一个皇后总是可以放置/k=l是已放置了皇后的行j) = abs(i - k)return false;k+;)return true;public static void queen(int i) (if (i > n)di spasolution();/放置1i的皇后/所有皇后放置结束else for (int j = 1; j <= n; j+)/在第i行上试探每一个列jif (place j ) )/在第i行上找到一个合适位置(i, j)qi = j; queen (i + 1);)public static void main(String args) n = 6;System, out .printf (nn %d 皇后问题解：n", n);queen (1) ;/放置1n的皇后