100个python算法超详细讲解：填表格

1．问题描述
将1、2、3、4、5和6填入下表中，要求每一列右边的数字比左边
的数字大且每一行下面的数字比上面的数字大。编程求出共有几种填
写方法？

2．问题分析
根据题目要求可知，数字1必然位于表中第一行第一列的单元格
中，而数字6则必然位于表中第二行第三列的单元格中，其他几个数字
则按照题目要求使用试探法来分别找到合适的位置。
3．算法分析
根据前面的分析，在实现时可以定义一个一维数组a[6]。数组元素
a[0]～a[2]位于表格中的第一行，数组元素a[3]～a[5]位于表格中的第二
行。具体如表12.1所示。

显然，a[0]=1，a[5]=6。又根据题意可知：
1）a[1]应该大于a[0]，则a[1]的取值从a[0]+1开始试探，最大不会
超过5。
2）a[2]应该大于a[1]，则a[2]的取值从a[1]+1开始试探，最大不会
超过5。
3）a[3]位于表格中的第二行第一列，则它应该大于a[0]，因此a[3]
的取值从a[0]+1开始试探，最大不会超过5。
4）a[4]位于表格中的第二行第二列，则它应该大于左侧的a[3]和第
一行中的a[1]，因此当a[1]>a[3]时，a[4]初值为a[1]+1，即从a[1]+1开始
试探，最大不会超过5；当a[1] 开始试探，最大不会超过5。
4．确定程序框架
（1）确定循环结构
在main()函数中构建一个四重循环，在该四重循环中对a[1]~a[4]的
取值进行试探。每重循环的循环变量初始值以及循环条件在算法分析
中已经讨论过。
循环结构如下：

a[1] = a[0] + 1
while a[1] <= 5: # a[1]必须大于a[0]
a[2] = a[1] + 1
while a[2] <= 5: # a[2]必须大于a[1]
a[3] = a[0] + 1
while a[3] <= 5: # 第二行的a[3]必须大于a[0]
# 第二行的a[4]必须大于左侧的a[3]和上边的a[1]
if a[1] > a[3]:
a[4] = a[1] + 1
else:
a[4] = a[3] + 1
while a[4] <= 5:
# 判断是否满足题意，如果满足则打印结果

 上面的代码中加粗的部分使用了条件表达式来保证a[4]必须同时大
于左侧的a[3]和上面一行中的a[1]。
（2）判断取值
定义函数judge()来判断a[1]～a[4]的取值是否符合题意，代码如
下：

判断 的取值
# 判断a[1]～a[4]的取值
def judge(b):
for i in range(1, 4):
l = i + 1
while l < 5:
if (b[l] == b[i]):
# 判断a[1]~ a[4]的取值是否有重复，若有重复则返回False
return False
l += 1
return True # 若a[1]~ a[4]的取值各不相同，则返回True

程序的流程图如图12.11所示。

5．完整的程序
根据上面的分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 填2行3列的表格
# 判断a[1]～a[4]的取值
def judge(b):
for i in range(1, 4):
l = i + 1
while l < 5:
if (b[l] == b[i]):
# 判断a[1]～a[4]的取值是否有重复，若有重复则返回False
return False
l += 1
return True # 若a[1]～a[4]的取值各不相同，则返回True
if __name__ == \'__main__\':
count = 1 # 计数器
a = [1, 2, 3, 4, 5, 6] # 初始化列表
print(\"满足条件的结果为:\")
a[1] = a[0] + 1
while a[1] <= 5: # a[1]必须大于a[0]
a[2] = a[1] + 1
while a[2] <= 5: # a[2]必须大于a[1]
a[3] = a[0] + 1
while a[3] <= 5: # 第二行的a[3]必须大于a[0]
# 第二行的a[4]必须大于左侧的a[3]和上边的a[1]
if a[1] > a[3]:
a[4] = a[1] + 1
else:
a[4] = a[3] + 1
while a[4] <= 5:
if judge(a): # 如果满足题意，则打印结果
print(\"结果%d:\" % count)
count += 1
print(a[:3])
print(a[3:])
print()
a[4] += 1
a[3] += 1
a[2] += 1
a[1] += 1

 6．运行结果
在PyCharm下运行程序，结果如图12.12所示。由运行结果可知，
满足条件的结果共有5组，即有5种符合题意的填表方法。