高位数“火柴棒问题”的思考与解决
作者吴飞(本文为原创，转载和引用请注明江苏省镇江第一中学吴飞，并联系作者qq406457邮箱sinowufei@)
（江苏省镇江第一中学，江苏 镇江 212000）
摘要： 关键词：函数；递归；动态规划；算法
中图分类号：G434 文献标识码：B
教科版高中信息技术教材必修1《数据与计算》第2单元第4节中有一个有趣的小例子。有6根火柴棒，要列出所有能摆出的自然数有多少种（要求火柴棒正好用完）。火柴组成的数字如图所示。
图1 火柴数字
教材给出的办法是[1]：先找出6根火柴棒能摆放的最大数111；然后从0到111依次判断这些数是否恰巧需要6根火柴棒，如果正好是6根，则计数器加1.。
那么怎样计算一个数需要多少根火柴棒呢？课本上也给出了方案：实现方法是将这个数除以10取余，求得个位数；然后将这个个位数需要的火柴棒数累加；接着将这个数除以10取整，去掉个位数；重复以上步骤直到这个数为0。
问题提出：
此方法无扩展性，枚举的方法无法解决高位数火柴棒问题。本文在此基础上做了三个层次的深度思考：第一层次分解问题，学习了函数并扩展了教材中程序的可用性；第二层次强化了算法的思维方式和问题的递归解决方法；第三层次引出了动态规划，解决了10000根以上火柴棒摆出多少种自然数的问题。其中每个层次都将发现问题，引出下个层次的解决办法。
一、思考一与解决
课本上只说了6根火柴棒，那么n=7根、9根、15根、20根呢？我们如果知道最大值，那么只需要从0到最大值，一一枚举尝试即可。
所以，我们可以把问题分解成：
1求最大值：分偶数和奇数考虑。
2主程序：从0到最大值一一枚举，看是否符合要求。
3 枚举时“复用”功能的算法：某数需要多少根火柴棒。
4“复用”功能的定义与调用：函数。
1、求最大值
偶数根的最大值是n//2个1；奇数根高位是7，用掉“7”的3根后同偶数，代码如下：
n=int(input(“请输入多少根火柴棒，n=”)) # n根火柴棒
if n%2= =0: #n为偶数,最大值是n//2个1
maxNum=int(“1”(n//2))
else: #n为奇数，最大值的首位必定是7，用掉“7”的3根火柴棒后同偶数
maxNum=int(str(7)+“1”((n-3)//2))
2、n根火柴棒的主程序
主程序就是从0到最大值来一一尝试枚举，如果恰好用n根，则计数加一。以下为n根火柴棒的主程序：
count=0
for i in range(maxNum+1):
if i需要的火柴棒数（小问题3）= =n: #如果i需要的火柴棒数等于现有火柴棒数
count+=1
print(“你可以拼出的数字：”,i,“计数：”,count)
3、某数需要多少根火柴棒
计算自然数num需要多少根火柴棒，可以分别计算num中各个数位需要多少根火柴，然后将各数位对应的火柴棒根数进行累加。
如何获得num各数位的值？将num除以10取余，求得个位数；然后将num除以10取整，去掉个位数。重复步骤直到num为0。显然可用while循环。
根据以上分析，对每一个自然数进行火柴棒个数的统计需要重复使用，因此可以设计函数优化代码。
4、函数——代码的复用
数字num需要多少根火柴棒的函数：
def match_num(num): #求数字num需要多少根火柴棒
f=[6,2,5,5,4,5,6,3,7,6] # 0-9的数字分别需要多少根小棒
if num==0: # 火柴棒总数变量赋初值
total=f[0]
else:
total=0
while (num>0):
x=num % 10 # 取num除以10的余数，即num的个位数
total=total+f[x] # 所需火柴棒数累加
num=num//10 #num整除10，即去掉num的个位数
return total #返回需要多少根火柴棒数
到此，我们可以将以上四个小问题的解决组合起来，形成完整的程序。还可以把最大值部分也改写成函数，可以实际运行6、9、15、20根火柴棒的情况。从中可以发现问题：运行时间越来越长；20根火柴棒将运行约40分钟；30根将难以得到结果。那么如何解决这个新问题呢？
二、思考二与解决
在思考一解决的过程中，我们发现了问题。此时，我们应该去思考我们解决这个问题的办法——算法。算法是解决问题的办法。课本上的解决办法是一一枚举尝试，程序将运行最大值（maxNum）次，20根就达到了11亿次。这个问题有没有好的算法解决呢？
乍一看似乎没有好的办法，但笔者进行了深入的思考，最终从数学问题中获得了灵感。该问题与数学中的走台阶问题有某种共通之处。
走台阶问题描述：
一个人上台阶，台阶有n级，他可以一次上1级，可以一次上2级，也可以一次上3级，问上这个n级的台阶一共有多少种上法。
根据题目可知，要想上到n级台阶最后一次抉择有三种可能的情况：（1）距n级台阶一个台阶（2）距n级台阶两个台阶（3）距n级台阶三个台阶。我们假设f（n）为上到n级台阶的方法数量，而我们又可以知道当n=1时，有一种方法即f（1）=1； n=2时，有两种方法即f（2）=2； n=3时，有四种方法即f（3）=4。那么以此为基础就可以得到f（n）=f（n-1）+f（n-2）+f（n-3）递归公式。
本文中如何转化成上台阶问题呢？
图2 数字与所用火柴棒
仔细观察上图2，可以发现任何一个数字用的火柴棒有2到7根，类似于台阶可以走2步到7步；其中5步和6步还各有三种走法。那么这个问题就可以转化为一个递归问题：n根火柴棒，每次拿掉2到7根，其中5和6各有三种拿法。问有多少种拿完火柴棒的办法？
于是我们可以设计如下递归公式：f（n）=f(n-2)+f(n-3)+f(n-4)+3f(n-5)+3f(n-6)+f(n-7)。终止条件是n=2时，f（n）=1；n=3时，f（n）=1；n=4时，f（n）=2；n=5时，f（n）=5；n=6时，f（n）=7；n=7时，f（n）=12；n=1时，f（1）=0。这里有个关键点，就是自然数中无“01”，而递归时前面有数字，则可以有“01”这种情况。所以，主程序中应减去0开头的数字。于是可以写出如下程序：
Def sumKind(n): #递归法求n根火柴棒可以拼成多少种数字
if n= =1: return 0
elif n= =2: return 1
elif n= =3: return 1
elif n= =4: return 2
elif n= =5: return 5
elif n= =6: return 7
elif n= =7: return 12
else:return
sumKind(n-2)+sumKind(n-3)+sumKind(n-4)+3sumKind(n-5)+3sumKind(n-6)+sumKind(n-7)
#以下为主程序
n=int(input(“请输入多少根火柴棒，n=”)) # n根火柴棒
print(sumKind(n)-sumKind(n-6))
运行的结果是：20,30根火柴棒可以瞬间得出结果；40根需要约2秒；50根将运行约3分钟；60根将难以得出结果。如何解决这个新问题呢？
三、思考三与解决
在本层次中，我们将用动态规划来解决50、1000、10000根火柴棒的问题。
其实，当用递归改写程序后，我们就已经可以想到用动态规划来进一步优化程序。动态规划。
我们可以用列表sumKind=[0,0,1,1,2,5,7,12]记录递归程序的终止条件，列表myArr=[0,0,1,1,1,3,3,1]保存是一种情况还是三种情况，并用空间换时间，把运算的中间结果保存在列表中，减少重复计算。这样我们可以在毫秒级得出10000根以上火柴棒这样的天文数字结果。可以写出如下程序：
n=int(input(“请输入多少根火柴棒，n=”)) # n根火柴棒
myArr=[0,0,1,1,1,3,3,1]
sumKind=[0,0,1,1,2,5,7,12]
for i in range(8,n+1):
sumKind[i%8]=0
for j in range(2,8):
sumKind[i%8]+=(myArr[j]*sumKind[(i-j)%8])
print(sumKind[n%8]-sumKind[(n-6)%8])
四、结束语
教材中的例子，我们通过思考分解问题，解决问题，在解决中不断发现新问题，可以激发学生的学习兴趣，促进学生计算思维的发展，便于学生理解函数、递归和动规等抽象概念。
参考文献：
[1]信息技术必修1数据与计算[M].教育科学出版社,.
