1.4.1 循环设计_算法设计与分析-QQ阅读女频仙侠网

上QQ阅读APP看书，第一时间看更新

1.4.1 循环设计

1. 自顶向下与自底向上的设计思维

自顶向下的设计（Top-Down Design）思维是指将复杂的大问题分解为相对简单的小问题，找出每个问题的关键所在，然后以定性、定量的方式精确地去描述问题和解决问题。其核心本质是“分解”。如在二分查找中，使用关键字与有序集合中的中间元素进行比较，若关键字比中间元素小，则在上半区中搜索，若关键字比中间元素大，则在下半区中搜索，若是等于则结束。它通过对解空间进行不断划分，来缩小搜索的范围，最终得到所要的结果。很多迭代算法中都采用了这种设计思维。

自底向上的设计（Down-Top Design）思维是指先找出某个问题的子问题或若干特殊问题，以定性、定量的方式去描述和解决这些子问题，然后逐步合并子问题的解，最后得到大问题的解。其核心本质是“合并”。如冒泡排序：有一组数列{13, 8, 6, 1, 2, 3, 4}，按从小到大的顺序进行排列，从第一个元素开始，逐个与后一个元素比较，当比后一个元素大时，与之交换，进行6次（n-1次）比较和交换（即一趟排序）后，最大的一个元素被排到了数列的最后，找到了组成问题答题的一部分。这里待排序元素有7个，那么进行6趟排序即可解决整个问题，如图1-9所示。

图1-9　冒泡排序算法第一趟排序

在进行循环设计，尤其是问题比较复杂、感觉“无从下手”时，上述两种设计思维是经常被使用的。说它们是循环设计的思维，是因为它不一定会体现在算法的最终实现上，可能在问题分析阶段时使用，也可能在算法设计与实现甚至程序测试时使用。

2. 挖掘内在规律构建计算模型

循环设计的第二个技巧是挖掘问题的内在规律，进行抽象并构建计算模型，该模型即前面提到的“不变式”。

【例1-3】设计算法，输出一个n×n的三角矩阵，它具有图1-10（a）所示的规律。

图1-10　特殊三角矩阵

问题分析

在矩阵运算中，通常是按照行或列优先的方式来进行的，即外层循环控制行，内层循环控制每一行中的每个列元素，如下所示。

既然矩阵的访问是通过行、列控制的，那么，在设计特殊矩阵的算法时，要充分利用这种规律，找到它与数据变化之间的运算关系。不难看出，图1-10（a）所示的矩阵是按斜线递增的三角矩阵。用变量L表示斜行号，矩阵的行、列号仍用i、j表示。按斜行访问矩阵，用L和j可以唯一确定一个元素的位置，且随着L和j的递增，其元素值呈整数连续递增，如图1-10（b）所示。通过示例可知，用k=k+1可以实现矩阵元素连续取值。只要找到L、i、j之间的关系，用L和j取代i，即建立“新”三角矩阵的元素访问顺序（斜行）与原三角矩阵的访问顺序的映射关系，就能完成任务。实际上，这一过程就是把一个连续整数序列{1，2，3，4，…，n}映射到矩阵上的对应位置。现通过穷举每一斜行的元素访问位置，找出L、i、j之间的关系。

由此可以看出，若下标起始值为0，则斜行的每个元素的访问位置与原始访问位置的对应关系为：

通过这个公式来处理对应关系，即任意给定一个斜行上的元素，便可以在原矩阵上找到相应的位置。另外，注意每一斜行上的元素个数会随着斜行号的增加而减少。

计算模型

按斜行号与列号递增给每个元素赋值。模型包含两部分：位置转换（式1-9、式1-10）和矩阵元素赋值（式1-11）。若设i为矩阵行，j为矩阵列，L为斜行，k为每一斜行上每一列元素的值，则两种矩阵访问方式之间的映射关系可通过下列公式来获得。

算法设计与描述

（1）设有矩阵a[n][n]，若给定第L_m（代表变量L的值）斜行第j_k（代表变量j的值）列位置，则对应矩阵a上的位置为。如第1（L₁）斜行第1（j₁）列位置，对应矩阵a上的位置为a[2][1]。

（2）设L为斜行计数值，j为斜行上列计数值，k为每一斜行上每一列元素的值，其初始值为1。

（3）算法如图1-11所示。

输入：矩阵行列值n。

输出：斜行元素值为连续整数的三角矩阵。

图1-11　三角矩阵输出流程图

算法分析

依据算法设计，算法的主体运算部分为两重循环，且内层循环j受外层循环控制，即j<n-L，则可以得到算法的主体语句执行次数为：

其中，L代表斜行，j代表列。

算法实现

void main()
{    //输入，按映射位置赋值
      int L,i, j, a[100][100], n, k=1;
      printf(" 请输入n 值：");
      scanf("%d",&n);
      for (L=0; L < n; L=L+1)
           for (j=0; j < n - L; j=j+1)
                a[L+j][j]=k++;
      //输出
       for (i=0; i< n; i=i+1)
       {
              for (j=0; j<=i; j=j+1)
                     printf("%5d",a[i][j]);
              printf("\n");
      }
}