作业帮 > 数学 > 作业

如果能确定对并证明就更好了

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/07/13 18:28:20
如果能确定对并证明就更好了
猜想-逆序数的个数
最近看到一题:
形如2 3 8 6 1这样的数列(数字可重复)中含5个逆序数
分别是 8-6 6-1 8-1 3-1 2-1
所谓逆序数就是数列中的第i个数字大于第j个数字(但i
1)两个数比较只能出现升序或逆序,而两个数比较恰好有m(m-1)/2个.所以有n个连续升序列(互不包含),则数列有m(m-1)/2-n个逆序数
2)在排序中,排列成...jk... (1)
经过j,k对换变成 ...kj... (2)
这里“...”表示那些不动的数.显然,在(1)中如j,k与其他的数构成逆序,则在排列(2)中仍然构成逆序;如不构成逆序则在(2)中也不构成逆序;不同的只是j,k的次序.如果原来j,k组成逆序,那么经过对换,逆序数就减少一个;如果原来j,k部组成逆序,那么经过对换,逆序数就增加一个.
你通过这个思路想问题就行了~~
所以 你第二个想法是对的.