排列组合问题证明
排列组合问题证明
有n个数在输入序列中,其中j个是不相同的.按顺序输出到输出序列,每次输出的时候都和输出序列中的每一个数字比较,如果遇到相同的数字,则把该数字从输出序列中删除,加入到输入序列的末端；如果比较之后,没有相同的数字,则把该数字加入输出序列的末端.请问,最多比较多少次?(N-1)*(N-1)- (J-1)(J-2)/2.请证明.
补充说明:
一开始,
输入序列：1,2,3,3,2,2
输出序列：
比较次数：0
然后输入序列第一个数字,进输出序列.因为输出序列没有元素,所以不需要比较.
输入序列：2,3,3,2,2
输出序列：1
比较次数：0
然后第二个,第三个元素输出
输入序列：3,3,2,2
输出序列：1,2
比较次数：1
输入序列：3,2,2
输出序列：1,2,3
比较次数：3
然后第四个元素3输入,一个个和输出序列的元素进行比较之后,发现有3,则把原来的3从输出序列中删除,加入到输出序列的最后
输入序列：2,2,3
输出序列：1,2
比较次数：6
同样,第五个元素
输入序列：2,3,2
输出序列：1
比较次数：8
第六个元素
输入序列：3,2
输出序列：1,2
比较次数：9
第七个元素
输入序列：2
输出序列：1,2,3
比较次数：11
第八个元素
输入序列：2
输出序列：1,3
比较次数：13
第九个元素
输入序列：
输出序列：1,3,2
比较次数：15
既然是问最多比较多少次,那么就要按极端情况考虑.假设输出序列中已有j个元素,输入序列中有n-j个元素,极端情况就是这n-j个元素与输出序列中的第j个元素相同.因此,第一次比j次,第二次比j-1次,输入序列元素减1,输出序列...答案肯定没错。。。定理来着。。那就是条件不符合，否则怎么解释3个1在输入序列中的结果呢？什么叫条件不符合。三个1的话，n=3,j=1, (N-1)*(N-1)- (J-1)(J-2)/=4,最多交换4次。结果是只交换了2次，却是小于4次。。啊，如果是这样的话，(n-1)*(n-1)就好了，绝对是最多。答案不是还减了神马吗。。。不懂啊不懂。。。。那个答案在j=n的时候是n(n-1)/2，符合逻辑啊~~