实验一:模拟与穷举

算法设计与分析

实验一:模拟与穷举

1. 实验目的

掌握模拟与穷举的算法,并对其复杂度进行分析。

2. 实验内容

(1) 陶陶摘苹果

陶陶家的院子里有一棵苹果树,每到秋天树上就会结出$n$个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。
现在已知$n$个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度,请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果,苹果就会掉下来。

输入样例
第一行为以空格分隔的苹果高度,第二行为陶陶的身高。

100 200 150 140 129 134 167 198 200 111
110

输出样例

5

(2) 和为0的数对

一个数组中的数互不相同,求其中和为0的数对的个数。

输入样例1

1 -1 -3

输出样例1

1

输入样例2

1 -1 2 3 4 -3

输出样例2

2

3. 实验要求

请写出题目的思路、代码,并进行时间复杂度分析。

4. 思考题

(1) 两年间的天数

用户输入两个年份$m$、$n$,程序输出$[m,n]$年间一共有多少天。请包含m和n年的天数。
1) 算法的时间复杂度如何?
2) 如果用户输入的是$x$个年份对$m$、$n$,程序应该如何修改?时间复杂度如何?
3) 可以优化吗?