-
- 加为好友
- 发送私信
- 在线聊天
dlyme- 等级:
- 可用分等级：
- 总技术专家分：
- 总技术专家分排名：
-
|
| 发表于：2008-04-10 10:41:441楼 得分:0 |
假设n个元素a(1) <a(2) <…… <a(n)，
最开始的序列一定是从a(1)a(2)……a(n)这个最小序列开始的(一定注意这一点，否则不能保证算法的正确性)，
到最后一个序列也是最大的a(n)a(n-1)……a(2)a(1)结束。
按照你说的算法执行过程，任取中间两个相邻序列S[i]和S[i+1]
需要证明两点才能保证这个过程是升序排列同时有没有遗漏：
1.后面这个序列大于前面的相邻序列，即S[i+1]>S[i]；
2.后面的这个序列S[i+1]是“刚刚好大于”S[i]的序列。换句话说，S[i+1]是所有大于S[i]的序列中最小的那个。
关于命题1：
和整数类似，我们把序列看成从左往右由高位到低位，高位上被换上了一个更大的数字，显然新序列更大一些。
关于命题2：
假设还存在一个序列S[k]使得S[i] <S[k] <S[i+1]，由于S[i]和S[i+1]中的1～j-1位完全相同，
所以S[k]的前1～j-1位必定也是和S[i]中相同的，只需研究j～n这些低位数字就可以比较出三个序列的大小。
将S[i]中的第j位数字记作a[i,j]，S[i+1]中的第j位数字记作a[i+1,j]，S[k]中的第j位数字记作a[k,j],
由于1～j-1位完全相同，且S[i] <S[k] <S[i+1]，显然有a[i,j] <=a[k,j] <=a[i+1,j]。
又因为a[i+1,j]是“J+1到N中最小的大于Aj的元素”，那显然只能有a[k,j]=a[i+1,j]。
于是比较S[k]与S[i+1]两个序列大小的问题，又转换成比较j+1～n这些低位数字的大小问题。
S[k]与S[i+1]前1～j位都相同，由于S[i+1]后面的元素全都升序排列，所以只能有S[i+1] <=S[k]。
这就得出了矛盾，因而前面的假设不可能成立，命题得证。 | | |
修改
删除
举报
引用
回复
| |
