作业帮 > 数学 > 作业

逆序数的问题对于个数互补相等的整数数组(i1,i2,i3...in)n是不小于2的正整数,如果piq,则称ip与iq是该

来源:学生作业帮 编辑:百度作业网作业帮 分类:数学作业 时间:2024/07/15 21:49:23
逆序数的问题
对于个数互补相等的整数数组(i1,i2,i3...in)n是不小于2的正整数,如果piq,则称ip与iq是该数组的一个逆序,一个数组中所有逆序的个数称为该数组的逆序数,例如 数组(2,4,3,1)中有逆序“2,1" "4,3""4,1" "3,1" 其逆序数等于4.若各数互不相的的正整数组(a1,a2,a3,a4,a5,a6)的逆序数是2,则(a6,a5,a4,a3,a2,a1)的逆序数是
答案13
怎么会13呢
我怎么都没想明白啊
逆序数的问题对于个数互补相等的整数数组(i1,i2,i3...in)n是不小于2的正整数,如果piq,则称ip与iq是该
有个巧妙的方法:
因为逆序和顺序是相对的,所以不管p和q(p≠q)的大小,数组ip,iq的顺序数和逆序数之和总是1,即任取2个数的顺序和逆序和总为1,所以(a1,a2,a3,a4,a5,a6)的逆序数是2,则顺序数应为C(2,6)-2=15-2=13,而(a1,a2,a3,a4,a5,a6)的顺序数恰好是序列(a6,a5,a4,a3,a2,a1)的逆序数(即aa),所以是13