传球游戏

题目描述:

游戏规则如下：有 n 位同学，编号分别为 0 ~ n-1，依次站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时，拿着球的同学可以把球传给自己左右的两个同学中的任意一个，但不能传给自己，当老师再次吹哨子时，传球停止。

请输入传球人数:4
请输入传球次数:4
传球方案为:
0-->1-->2-->3-->0
0-->1-->2-->1-->0
0-->1-->0-->1-->0
0-->1-->0-->3-->0
0-->3-->0-->1-->0
0-->3-->0-->3-->0
0-->3-->2-->3-->0
0-->3-->2-->1-->0
共有方案数: 8

统计有多少种不同的传球方法可以使得从 0 号同学出发，传了 m 次球以后，又回到 0 号同学手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学 0 号、 1 号、 2 号，从 0 号开始传球传了 3 次回到 0 号手里的方式有 0 -> 1 -> 2 -> 0 和 0 -> 2 -> 1 -> 0，共 2 种。按上述要求，编写 程序，功能如下：输入人数 n 及输入传球次数 m，输出总的方案数。

输入格式:

共两行。

第一行一个整数，n。

第二行一个整数，m。

输出格式:

第一行输出传球方案的提示。

接下来若干行，每行一个传递球的方案。

最后一行输出方案总数。

数据范围:

\( 2  \le n, m \le 1000 \)

样例输入:

4
4

样例输出:

Passing plan:
0-->1-->2-->3-->0
0-->1-->2-->1-->0
0-->1-->0-->1-->0
0-->1-->0-->3-->0
0-->3-->0-->1-->0
0-->3-->0-->3-->0
0-->3-->2-->3-->0
0-->3-->2-->1-->0
Total number of passing ball: 8

提示:

请完善下列程序：

def route( p ):
    flag = False
    if q[p] == 0:
        s ="0"
        i = p
        while pre[i] != -1:
            s = ________________ + "-->" + s   #填空1
            i = pre[i]
        print( s )
        flag = True
    return flag
n = int( input( ) )
m = int( input( ) )
print( "Passing plan:" )
pre = [0] * 2 ** ( m + 1 )
q = [0]*2**(m+1)
head = tail = 0
pre[0] = -1
q[tail] = 0
tail += 1
i = 0; sum = 0
while i < m:
    for j in range( 2**i ):
        q[tail] = ( q[ head ] + 1 ) % n
        __________________________________   #填空2
        pre[ tail] = head
        pre[ tail + 1 ] = head
        if i == m-1:
            if route( tail ): sum += 1
            if route( tail + 1 ): sum += 1
        tail = tail+2
        ________________________    #填空3
        pre[tail] = head
    i += 1
print( "Total number of passing ball: %d" % sum )

时间限制: 1000ms
空间限制: 256MB

---

来源: 2022年12月浙里卷T16