【对算法期中卷子的解析和反思】

一、程序阅读并回答问题（共30分）

1. #include<cstdio>
2. #include<cstring>
3. #include<iostream>
4. using namespace std;
5. char chess[10][10];
6. int sign[10];
7. int n, k, ans;
8. void dfs(int x, int k)
9. {
10.   if (k == 0){
11. ans++;
12. return;
13.     }
14.    if (x+k-1 > n)
15. return;
16.   for (int i = x; i <= n; i++)
17.       for (int j = 1; j <= n; j++)
18.   if (!sign[j] && chess[i][j] == '#'){
19. sign[j] = 1;
20. dfs(i + 1, k - 1);
21. sign[j] = 0;
22. }
23.  }
24. int main()
25. {
26.     while (cin >> n >> k){
27. memset(chess, 0, sizeof(chess));
28. memset(sign, 0, sizeof(sign));
29. if (n == -1 || k == -1)
30. break;
31.        for (int i = 1; i <= n; i++)
32. for (int j = 1; j <= n; j++)
33. cin >> chess[i][j];
34. ans = 0;
35. dfs(1, k);
36. cout << ans << endl;
37.      }
38.    return 0;
39.  }

设程序的输入如下，请写出程序执行到35行时变量chess的值。（3分）

4 4

...#

..#.

.#..

#...

-1 -1

这里的坑点就是chess[][]的范围是[0-9][0-9]，很多人没考虑多余的部分

chess[1][1]~Chess[1][4]的值分别为“.”，“.”，“.”，“#”。

chess[2][1]~Chess[2][4]的值分别为“.”，“.”，“#”，“.”。

chess[3][1]~Chess[3][4]的值分别为“.”，“#”，“.”，“.”。

chess[4][1]~chess[4][4]的值分别为“#”，“.”，“.”，“.”。

其余值为0。

分析函数dfs(.)的时间复杂度，写出分析求解过程。（12分）

这个时间复杂度也是，跟之前的答案出来的还不一样，逆天

以前这个，纯纯数学公式推出来的，啥初始条件都是浮云

你想想，右边是组合数，我们可以理解为n列中选K列，再粗略的n行选、n-1行选......左边也该是个阶乘来着......无语

现在这个

若采用问题（1）中的输入，分析该程序的求解过程。（15分）

这个跟老师之前出的类似题写的真不一样，服了。

我觉得我这个写的是对的

二、算法分析题 (共40分)

某班级的同学正在玩一个游戏。他们在某个时刻把一个物品摆放到跑道的某个位置，设跑道的长度为10米且是笔直的。游戏前他们会把每个物品的价格，物品出现的时间和位置告诉给玩游戏的同学。假设玩游戏的同学刚开始时站在跑道的某个位置，他每秒跑的距离不超过1米。当然他可以不跑，也可以朝前或者朝后跑。他每跑到一个位置便可以快速的拾取该物品，然后以同样的速度跑到下一个位置。请问，他最多能够获得的物品的总价格是多少？

输入：

输入数据的第一行包含两个正整数n(0<n<100)和m(0<=m<=10)，其中n表示待摆放的物品的个数，m表示刚开始时玩游戏同学所在的位置；在接下来的n行中，每行有3个整数x, t(0<T< 100000)和p，表示在第t秒会在x位置上摆放一个价值为p的物品。同一时刻可能在同一位置摆放多个物品。

输出：

玩游戏的同学最多能够拾取的物品的总价格是多少？

样例输入：

  4 4

  2 1 1

  3 2 5

  5 3 1

  6 2 3

样例输出：

  5  

要求：

请写出采用穷举法求解该问题的伪代码，并画出样例输入时的解空间树。（10分）

我们的算法的起点都不一样，真不知道这咋整

请写出采用动态规划算法求解上述问题的伪代码，并用样例输入对其进行验证，写出求解过程。（20分）

也是算法不一样

【拾取问题】-CSDN博客

好吧，老师写的比我好，我需要递归，他不用，但是这个有点颠覆我的思维，我没看懂

行号	执行次数	i	j	dp[i][j]	mValue
6	1	0	1	0	0
6	2	0	2	0	0
6	3	0	3	0	0
6	5	1	2	0	0
4	15	4	3	5	0
10	1	-	-	-	5

我也可以给这个表格，但是定义都不一样，咋能指望一模一样

表3 动态规划求解结果(dp[i][j])

（j,i）	0	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	5	0	0	3	0	0	0	0
3	0	0	5	5	5	4	3	3	0	0	0

分析（1）中算法的时间复杂度，写出分析求解过程。（10分）

没看懂咋分析的

题（1）为三叉树，深度为lTime+1,因此T(0)=3T(1),T（lTime）=O(1),其时间复杂度为O(3lTime)。

三、算法设计及实现(共30分)

有一个2*n大小的矩形地板，用2*2和2*1大小的瓷砖方块来填满它。求一共有多少种不同的放法？如下所示：

输入：

    输入包含若干行，每一行包含一个整数n（0<=n<=250）,表示矩形地板的长度。

输出：

    对于每一行的输出，输出一行整数，表示矩形地板的不同的摆放方法。

样例输入：

2

8

12

100

200

样例输出：

  3

171

2731

845100400152152934331135470251

1071292029505993517027974728227441735014801995855195223534251

要求：

当n=2时，画出不同的摆放方法。（5分）

三种，略

假设长度为n时摆放两种砖块的不同摆放方法有f(n)种。如果前面两块摆放2*2的砖块，则剩余的n-2块砖块摆放两种不同砖块的摆放方法有多少种？（5分）

这里竟然是把f[n]当作函数，估计是老师像让我们用动态规划做，所以提示，答案是f[n-2]

假设长度为n时摆放两种砖块的不同摆放方法有f(n)种。如果前面1块摆放2*1的砖块，则剩余的n-1块砖块摆放两种不同的砖块总共有多少种不同的摆放方法？（5分）

f[n-1]

按题目要求编写完整程序，并简要说明算法求解思想。（15分）

【地板拼接问题】-CSDN博客

该算法的求解思想：

假设地板长度为n，有f[n]种放置2*1和2*2砖块的方法。假设某一块放2*2，则有方法数f[n-2]；假设某一块竖着放2*1，则有方法数f[n-1]；假设某一块横着放2*1，则有方法数f[n-2]，因此得出转移方程f[n] = 2 * f[n-2] + f[n-1]

于是将求解dp[n]的问题，转化为求解dp[n-1]和dp[n-2]的问题，从而不断分解为简单的子问题，直到分解为最小子问题dp[0]=1,dp[1]=1。