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

《数据结构（Java语言版）实验指导书-递归实验.docx》由会员分享，可在线阅读，更多相关《数据结构（Java语言版）实验指导书-递归实验.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归实验答案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 = s

2、olve2(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 (

3、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: %dnrsolvel(n);solve2(n);solve3(n);solve

4、4(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 0 ? x : -x;)public static boolean place (int i,int ) /测试(i/j)位置能否摆放皇后if (i = 1) return true;int k = 1;while (k 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的皇后