专题九 其他常用算法 1．(2019·4月浙江省选考)小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将数组a中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理。算法的VB程序段如下，但加框处代码有错，请改正。 ′待排序数据存储在数组a中(a(1)～ a(n))，要求升序排列 For i ＝ 1 To (n － 1) 2 For j ＝ 1 To n － i * 2 If Then′(1) t ＝ a(j): a(j) ＝ a(j ＋ 2): a(j ＋ 2) ＝ t End If Next j Next i For i ＝ 1 To n 2 j ＝ 2 * i － 1 If a(j) > a(j ＋ 1) Then t ＝ a(j): a(j) ＝ a(j ＋ 1): a(j ＋ 1) ＝ t Next i For i ＝ Step 2′(2) t ＝ a(i): j ＝ i － 1 Do While t < a(j) a(j ＋ 1) ＝ a(j): j ＝ j － 1 Loop a(j ＋ 1) ＝ t Next i 解析 插入排序也是经常要考到的问题。先是分别对奇数位和偶数位进行排序，排序后再使偶数位大于前面的元素，最后进行插入排序，只需要对奇数位进行插入排序即可。仅奇数位插入排序，i从1时会导致出现a(0)下标越界，所以i从3开始，即第二空答案为3 To n。 答案 (1)a(j)>a(j＋2) (2)3 To n 2．(2018·11月浙江选考)某种数据加密方法描述如下(加密前后的数值都是0～255的整数)： ?以m个数据为一段，将n个待加密数据依次分割成若干个数据段。剩余数据(个数小于m)为一个独立数据段。 ?数据段加密规则： 数据个数等于m的数据段，先进行值变换，再进行位置变换，得到加密数据段。 数据个数小于m的数据段，只进行值变换，直接得到加密数据段。 ?依次合并加密数据段，即为最后的加密数据。 值变换：用值变换密钥数组x(元素个数为m，值为0～255的整数)，将待加密数据段中的数据进行值变换，方法如下： 值变换后第i个元素＝(待加密数据段第i个元素＋x(i))Mod 256，其中i＝1，2，…，m 位置变换：用位置变换密钥数组y(元素个数为m，值为1～m的不重复整数)，将上述值变换后的m个元素进行段内位置变换，方法如下： 加密后数据段第y(i)个元素＝值变换后第i个元素，其中i＝1，2，…，m 例如，n＝5，m＝3的数据加密过程如下： (1)已知m＝3，数组x与数组y中的数据如下表所示。则待加密数据段“155，1，250”加密后的数据段为_____(填数据，用逗号分隔)。 x(1) x(2) x(3) 10 20 30 y(1) y(2) y(3) 3 1 2 (2)小张根据上述加密算法，设计了一个对应的解密程序，其VB代码如下，请在划线处填入合适的代码(解密与加密使用相同的密钥数据)。 Private Sub Command1_Click( ) Const n＝100 Const m＝6 Dim i As Integer，j As Integer Dim a(1 To n) As Integer，b(1 To n) As Integer Dim x(1 To m) As Integer，y(1 To m) As Integer ′读取值变换与位置变换的密钥数据，分别保存在数组x与y中，代码略。 ′读取待解密数据，保存在数组a中，代码略。 ′下面进行位置变换：位置变换后数据保存到数组b中 For i＝1 To ____①____ For j＝1 To m ____②____ Next j Next i For i＝(n m)*m＋1 To n b(i)＝a(i) Next i ′下面进行值变换：值变换后数据仍保存到数组b中 j＝1 For i＝1 To n b(i)＝____③____ j＝j＋1 If j＞m Then j＝1 Next i ′输出解密后数据，代码略。 End Sub 解析 数据构成环是本题考核的其中一个问题。155，1，250值变换后变成165，21，24，位置变换后变成21，24，165。加密时，先进行值变换，再进行位置变换，解密时应先位置变换，再进行值变换。进行位置变换时，变量i表示共有多少整数段，也可以理解为多少行，易知完整的 m 个数据段的个数为n m个．变量j表示每段中每列的位置。当i＝1 时，完成第 1 段数据变换，即 b(j) ＝ a(y(j))，当i＝2 时，完成第 2 段数据变换，即 b( m＋ j) ＝ a( m＋ y(j))，当i＝3 时， ... ...
