文章

1

粉丝

407

获赞

2

访问

14.6k

头像
翻煎饼
P1116
发布于2020年3月25日 15:13
阅读数 14.6k

题中所谓“翻煎饼”的方法,就是:将铲子上方的煎饼次序颠倒。

将上述过程模拟为对一个大小为n的数组排序(升序),次数最少就要求:每次将当前数组中尚未排序的最大的数,通过颠倒数组部分元素次序的方法,移至该部分元素的最靠后位置。

以n=5,原始次序为:5、4、2、3、1为例:

第一轮:判断下标为4的元素不是前(4+1)个元素中最大的元素,因此找到最大的元素——5,下标是0,可以直接翻转,得到:1、3、2、4、5。(1次翻转)

第二轮:判断下标为4的元素是前(4+1)个元素中最大的元素,下标为3的元素是前(3+1)个元素中最大的元素,但下标为2的元素不是前(2+1)个元素中最大的元素,因此找到最大的元素——3,下标是1!=0,因此将前(1+1)个元素翻转,得到:3、1、2、4、5,然后再将前(2+1)个元素翻转,得到:2、1、3、4、5。(2次翻转)

第三轮:判断下标为1的元素不是前(1+1)个元素中最大的元素,因此找到最大的元素——2,下标为0,可以直接翻转,得到:1、2、3、4、5。(1次翻转)

因此至少要经过4次翻转。

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发