算法设计与分析
实验一:模拟与穷举
掌握模拟与穷举的算法,并对其复杂度进行分析。
陶陶家的院子里有一棵苹果树,每到秋天树上就会结出$n$个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。
现在已知$n$个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度,请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果,苹果就会掉下来。
输入样例
第一行为以空格分隔的苹果高度,第二行为陶陶的身高。
100 200 150 140 129 134 167 198 200 111
110
输出样例
5
一个数组中的数互不相同,求其中和为0的数对的个数。
输入样例1
1 -1 -3
输出样例1
1
输入样例2
1 -1 2 3 4 -3
输出样例2
2
请写出题目的思路、代码,并进行时间复杂度分析。
用户输入两个年份$m$、$n$,程序输出$[m,n]$年间一共有多少天。请包含m和n年的天数。
1) 算法的时间复杂度如何?
2) 如果用户输入的是$x$个年份对$m$、$n$,程序应该如何修改?时间复杂度如何?
3) 可以优化吗?