Question

在 n×n 的方格中进行跳棋游戏．规定每跳一步只能向左，或向右，或向上，不能向下，且一次连续行走的路径中不能重复经过同一小方格．设f（n）表示从左下角“○”位置开始，连续跳到右上角“☆”位置结束的所有不同路径的条数．如图，给出了n=3 时的一条路径．则f（3）=________；f（n）=________．

Answer 1

9    n^n-1
分析：本题看似难以入手，只要以每一个方格向上跳为切入点问题就变得明朗化，从下一行的一个方格到达上一行，共有n条路径，总共需要n-1次行跳跃．
解答：由给出的3×3方格看出，要从左下角“○”位置开始，连续跳到右上角“☆”位置，需要先从第一行跳到第二行，共有3种跳法，跳到第二行的每一个方格内要完成到达右上角“☆”位置，又可以看作从该方格有几种到达第三行的方法，所以该题只需思考向上走就行了，从第一行到第二行有3种跳法，从第二行到第三行也有3种跳法，故
f（3）=3²=9．由此可推得 n×n 的方格中从左下角“○”位置开始，连续跳到右上角“☆”位置的方法种数是n-1个n的乘积．即f（n）=n^n-1．
故答案分别为9；n^n-1．
点评：本题考查了简单的合情推理，考查了数学转化思想方法，解答该题的关键是把问题转化为如何向上走，此题是中档题．