编造幻方程序习题
一.试确定下面程序段中各语句的执行次数。
开始
循环 i以1为步长，从1到n，执行
循环 j以1为步长，从1到i，执行
循环 k以1为步长，从1到j，执行
x←x+1
｛子算法结束｝
2用外延法(由巴谢提出)构造奇阶幻方，以n=5为例。首先按图(a)的方式作外延，将数1,2,3…,25，按对角线向上的方向，依次填到小方格中去。然后将外延部分移到正方形对面的小方格中，便得到了图(b)的5阶幻方。
试用外延法编写奇阶幻方的程序，并对所编程序作算法分析。
由于我们最关心的是计算时间的数量级，因此，在对循环程序进行算法分析时，只要估计循环语句的计算时间就行了。
对于由n次循环构成的程序，一般是求出一次循环所需要的时间，即每循环一次，循环体中各语句执行的总的次数，进而求出n次循环所需要的时间。
例 幻方向问题 给定一个n×n格的正方形，将1到n2的自然数填写到n2个小方格中，使正方形的每一行、每一列以及两条对角线上的数之和都相等。
这个古老的趣味问题，曾有许多人研究过，提出了一些解法。这里仅介绍由H·Coxeter提出的一种构造幻方的方法。其规则是：首先在正方形最上面一行的正中间的小方格内填写1，然后到它的左上方的小格内填写下一个数(注意：我们认为正方形的同一行或同一行的头尾是相连的)。如果走到某个小方格，而该格已填了数，那末就改走到原方格的下面一个方格。
设n=5,构造幻方如下：在正方形最上一行中间填1。在它的左上方填2，这时出正方形外，由于行列首尾相连，故将2填在该列的最下边一格。2的左上方填3。3的左上方在正方形外，同理将4填在该行的最右边一格。4的左上方填5。5的左上方已有数，就改在5的正下方填6。……。如此继续下去，直到正方形的各格填满为止。构造的5阶幻方如下所示。
|
15 |
8 |
1 |
24 |
17 |
|
16 |
14 |
7 |
5 |
23 |
|
22 |
20 |
13 |
6 |
4 |
|
3 |
21 |
19 |
12 |
10 |
|
9 |
2 |
25 |
18 |
11 |
在按Coxeter规则编写程序之前，我们还要考虑一些具体问题。
首先，在计算内如何表示这个正方形以及它的每个方格?我们假设用二维数组square(n-1,n-1)来表示正方形。每个小方格用它在正方形中的位置(i,j)来表示，其中0≤i,j≤n-1。
其次，如何处理走到正方形外面的情况?当然可以用条件语句或情况语句来处理。不过达里用的是另一种方法，它能很好地体现正方形的行、列是首尾相连的。假设用(i) mod n,表示i被n除所得的余数(i和n是正整数)，于是在方格(i,j)中填了数后，下一次就应该走到((i-1) mod n,(j-1) mod n)处，而不必去判定是否走出正方形了。
最后，要考虑如何处理走到的正方形小格是否已填了数。因所填的数都是正的，故初始将每小格填上0。以后用小格中的数是否为0，来判断该格是否已填了数。
现将构造幻方的算法描述如下：
算法112 构造幻方(square,n)
1 循环i以1为步长，从0到n-1，执行
2 循环 j以1为步长，从0到n-1,执行
square(i,j)←0
3 square(0,(n-1)/2)←1
4 i←0,j←(n-1)/2
5 循环 key 以1为步长，从2到n2，执行
6 (k,1)←(i-1) mod n, (j-1)mod n)
7 若 square(k,1)=0
8 则(i,j)←(k,1)
9 否则i←(i+1)mod n
10 square(i,j)←key
｛算法结束｝
现在来进行算法分析。算法11.2有两个循环。行1～2是一个循环。每外循环一次内循环做n次。现外循环做了n次，所以行1～2共执行n2次。这部分的计算时间为O(n2)。另一个循环是行5～10的循环。每循环一次，循环体中的每个语句各执行一次，共四次，循环n2-1次，所以这个循环的计算时间是4(n2-1)次，即O(n2)。综上所述，构造幻方的算法总的计算时间是O(n2)。