1、用蛮力法求解 折点 1题
给定n个整数表示一个商店连续n天的销售量。如果某天之前销售量在增长,而后一天销售量减少,则称这一天为折点,反过来如果之前销售量减少而后一天销售量增长,也称这一天为折点。其他的天都不是折点。如下图中,第3天和第6天是折点。
2、用蛮力法求解 股票波动 2题
小明正在利用股票的波动程度来研究股票。小明拿到了一只股票每天收盘时的价格,他想知道,这只股票连续几天的最大波动值是多少,即在这几天中某天收盘价格与前一天收盘价格之差的绝对值最大是多少。
3、用分治法求解 中间数 3题
在一个整数序列a1, a2, …,an中,如果存在某个数,大于它的整数数量等于小于它的整数数量,则称其为中间数。在一个序列中,可能存在多个下标不相同的中间数,这些中间数的值是相同的。
4、求解逆序数问题 4题
给定一个整数数组a[n],若i<j,a[i]>a[j],则<a[i],a[j]>称为一个逆序对。
例如:数组(3,1,4,5,2)的逆序对有<3,1>,<3,2>,<4,2>,<5,2>,其逆序对的个数称为逆序数,
如数组(3,1,4,5,2)的逆序数为4.
请用分治法设计一个程序解决之并分析其时间复杂度
5、链表逆转 5题
对于一个不带头结点的单链表L,设计一个递归算法逆置所有结点。
编写完整的程序并进行测试,分析其时间复杂度。
6、最大公约数 6题
设计一个递归算法求二个正整数x,y的最大公约数(gcd),并转换为非递归算法。
kuai